CS 136 Assignment 5

Due Wednesday, Oct. 17 at 11:59 am sharp. Late submissions will receive half marks if submitted before Dec. 3 at 11:59 AM sharp.

Hand Marking: This assignment will include 20 marks for handmarking documentation and style in your C code only.

Assignment 5 Problem 1. 20 Marks (15 Marmoset; 5 Hand Marked). File: order.c

This problem consists of five parts: A5P1a through A5P1e. For each part you will submit a distinct solution named order.c to Marmoset.

Read this reference on order notation. Note how the proofs proceed by starting with inequalities and maintaining them.

Recall the definition of big-Oh:

f(n) is in O(g(n)) if and only if there exist positive constants c and n₀ such that f(n) ≤ c*g(n) for all n ≥n₀.

Suppose that f(n) IS NOT IN O(g(n)). Then given any positive constants c and n₀, you will be able to find an n ≥ n₀ such that f(n) > c*g(n). We call such an n an O-violation at (c,n₀)
If f(n) is in O(g(n)) then there will exists constants c and n₀ such that there is no O-violations at (c,n₀). Just look at the definition of big-Oh. In this case we call (c,n₀) O-witnesses.

In this problem we will compute O-violations and O-witnesses for specific functions.

For each pair of definitions of f(n) and g(n) given below, labeled A1P1a through A1P1e, you must write a C module which declares the following functions:

// Function findviolation: //Consumes ints c ≥ 1 and n0 ≥ 0, //Produces an int n such that n ≥ n0 and f(n)>c*g(n). // I.e., n is an O-violation at (c,n0) for f and g.// If no such O-violation exists at (c,n0), findviolation should produce -1. int findviolation(int c, int n0);
- For example, if f(n)=11*n and g(n)=n² then findviolation(2,3) could return 3, since 11*3>2*3². (It could also return 4 or 5, but no other integers). For these same functions findviolation(2,6) should return -1 (no violations) since 11*n ≤ 2*n² for all n ≥ 6.
// findwitnessc() and findwitnessn0() produce c > 0 and n0 ≥ 0 respectively // such that for all n ≥ n0 and we have f(n) ≤ c*g(n). // Both should produce -1 if such c and n0 do NOT exist. int findwitnessc(void); int findwitnessn0(void);
- For example, if f(n)=11*n and g(n)=n², then findwitnessc() could return 2 and findwitnessn0() could return 6, since we have 11*n ≤ 2*n² for all n ≥ 6.

Notes:

You will write a different implementation of findviolation, findwitnessc, and findwitnessn0 for each part of the question (A4P1a – A4P1e).
In the comments at the top of your code for each function you must provide a derivation that either f(n) ∈ O(g(n)) or that f(n) ∉ O(g(n)). For examples, please see the solution for f(n) = 11*n, g(n) = n² and the solution for f(n)=n²,g(n)=n.
If f(n) ∈ O(g(n)), then findwitnessc() and findwitnessn0() should produce non-negative values, and findviolation(findwitnessc(), findwitnessn0()) should produce -1. Note that findviolation should produce an O-violation for other inputs if an O-violation exists for those inputs.
If f(n) ∉ O(g(n)), then findwitnessc() and findwitnessn0() should both produce -1, and findviolation should always produce an O-violation.
A header file for the required functions is provided in order.h.
Technology permitting, you may request a review of one release test submission on Marmoset by sending an email to the course account with the subject "A5P1a Review Request" or "A5P1c Review Request", etc. The review will be solely relating to the comment-proofs above the functions and will detail your probable mark for that part of the question. The request must be made from your UWaterloo email account before noon on Monday. The review will be sent by email to your UWaterloo email in response. After the deadline, your best release test only will be hand-marked, and comments returned through MarkUs.

Solve the problem for the following pairs of functions f(n) and g(n):

f(n)=n, g(n)=2*n
f(n)=2*n+1, g(n)=n/10000
f(n)=n, g(n)=100*floor(n/10)
f(n)=n, g(n)=sqrt(n)
f(n)=2ⁿ, g(n)=2^n-1

Problems 2 through 7

For the rest of this assignment you will implement components of a C program that implement and use an abstract data type ilist that behaves like a Scheme list of integers. You may not use recursion or arrays in any of your solutions. The elementary operations on ilist are as follows:

   // Abstract data type ilist
   
   // ilist is defined as follows
   
   // ilist iempty()   
   //    returns an empty ilist
   
   // int iempty_huh(ilist il) 
   //    returns 1 (true) if il is empty
   //    returns 0 (false) if il is not empty
   
   // ilist icons(int in, ilist il)
   //    produces a new ilist where in is the first element
   //    and il is the rest
   
   // int ifirst(ilist il)
   //    returns the first element in il
   //    il must not be empty
   
   // ilist irest(ilist il)
   //    returns il except for the first element
   //    il must not be empty

   // void idelete(ilist il)
   //    frees the storage for ilist
   //    all further references to il become invalid
   //    NOTE: every ilist created by icons must eventually
   //          be freed (exactly once) by being a member of 
   //          an ilist that is consumed by delete

You are given a straightforward implementation of ilist as well as a user interface in files ilist.h, ilist.c and ilistui.c.

Note: Marmoset uses a different implementation. IF YOU MAKE ANY ASSUMPTIONS ABOUT THE IMPLEMENTATION OTHER THAN THOSE STATED ABOVE, YOUR PROGRAM WILL FAIL.

Assignment 5 Problem 2. 10 marks. File: backward.c

Write a C program file backward.c that defines main which reads a sequence of integers, uses an ilist to store them, and prints them backwards. You may not use malloc for this problem. For example, if the input file contains

   10
   20
   30

your program should output

   30
   20
   10

Standard input contains an arbitrary number of lines, each containing an integer between 0 an 2^31-1. The sequence you are to read consists of all of these integers, in order. Your output must contain one number per line and nothing else, with no spaces anywhere and a newline at the end of each line.

Recall that scanf returns an integer which is the number of items read -- a smaller number indicates that there are no more items to be read. In the interaction window, you indicate the end of input by typing Control-D. When using a test input file like backwards.in.1, the system automatically detects the end of the file. For example, see example.c

Assignment 5 Problem 3. 10 marks. File: forward.c

Write a C program file forward.c that defines main which reads a sequence of integers, then prints the length of the sequence, followed by the sequence itself. You may not use malloc for this problem.

Your implementation must use O(n) time and O(n) space where n is the length of the input.

For example, if the input contains

   10
   20
   30

your program should output

Standard input contains an arbitrary number of lines, each containing an integer between 0 and 2^31-1. The sequence you are to read consists of all of these integers, in order. Your output must contain one number per line and nothing else, with no spaces anywhere and a newline at the end of each line.

Assignment 5 Problem 4. 10 marks. File: ilist.c

Assume that the following specification is added to ilist.h:

   int ilength(ilist il);
   // computes the number of elements in il

Add a suitable implementation to ilist.c. You should not modify the definition of ilist or any of the other functions provided by ilist.h.

Assignment 5 Problem 5. 10 marks. File: ilist.c

Modify ilist.c (but not ilist.h) as necessary to implement the operations defined so as to meet the following running time constraints:

running time of iempty() is O(1)
running time of iempty_huh(il) is O(1)
running time of icons(in,il) is O(1) assuming running time of malloc(s) is O(s)
running time of ifirst(il) is O(1)
running time of irest(il) is O(1)
running time of ilength(il) is O(1)
running time of idelete(il) is O(n) where n is the number of elements in il.

Assignment 5 Problem 6. 10 marks. File: ilist.c

Assume that the following specification is added to ilist.h:

  ilist iappend(ilist il1, ilist il2);
  //     builds a new list with the elements
  //     of il1 followed by the elements of il2

Add the corresponding implementation to ilist.c. The running time of iappend(il1,il2) should be O(n) where n is the total number of elements in il1 and il2 combined.

Assignment 5 Problem 7. 10 marks. File: ilist.rkt

Implement problem 5 in Racket. Your implementation should provide functions iempty, iempty?, icons, ifirst, irest, ilength, and iappend that satisfy the definitions and running times given above. There is no need to implement idelete, as it has no purpose in Racket. Recursion is permitted.

Assignment 5 Problem 8. Bonus. 3 Marks. File: ilist.c

Modify ilist.c so that the running time of iappend(il1,il2) is O(m) where m is the number of elements in il1. You must preserve all other running times. For this question, you are allowed to have ilists that share memory in the heap and you will need to modify the idelete function. Programs like the following must run without error:

#include "ilist.h"

int main(){
  ilist a = icons(1,icons(2,iempty()));
  ilist b = icons(3,icons(4,empty()));
  ilist c = iappend(a,b);
  idelete(c);                        // deleting c should not affect a or b
  ilist d = iappend(a,b);
  idelete(b);                        // deleting b should not affect d or a
  ilist e = iappend(a,d);
  idelete(d);                        // These last three calls to idelete 
  idelete(e);                        // can be in any order
  idelete(a);                        //
  return 0;
}