CSCI 3110 Assignment 2 Due Thursday May 20 at 11am    submit a2.txt
This assignment is to be done individually and submitted electronically.
The solution must be a text file a2.txt.

0) Answer questions 3-4 parts a and b from page 59 of the 2/e of CLRS:
"Let f(n) and g(n) be asymptotically positive functions. Prove or disprove
 each of the following conjectures:
 a)  f(n) = O( g(n) ) implies  g(n) = O( f(n) )
 b)  f(n) + g(n) = Theta( min(f(n), g(n)) )
"

1) Consider http://www.cs.dal.ca/~sedgwick/MergeSort.java . What is the
recurrence formula for this program and what is the solution of the recurrence.
What advantages does this program have over the one on p29 2/e?
 (Here we mean the Merge-Sort program in the 2/e and the slides.
  Apparently the 3/e has a O(n) sort on page 29.)
There is one disadvantage. There is a 1 mark bonus if you identify it
and another mark if you suggest how that disadvantage could be eliminated.

2) Do problems 4-1 a,b,g:
"Give asymptotic upper and lower bounds for T(n) in each of the following
 recurences. Assume that T(n) is constant for n < 3. Make your bounds as 
 tight as possible.
 a) T(n) = 2 T(n/2) + n^3  
 b) T(n) = T(9n/10) + n   
 g) T(n) = T(n-1) + n
"
3) Do problem 4-2 Finding the missing integer:
"An array A[1..n] contains all the integers from 0 to n except one. It would 
 be easy to determine the missing integer in O(n) time by using an auxiliary
 array B[0..n] to record which numbers appear in A. In this problem, however,
 we can not access an entire integer in A in a single operation. The elements
 of A are represented in binary, and the only operation we can use to access
 them is 'fetch the j'th bit of A[i]," which takes constant time.

 Show that if the only way to access information in array A is by this single-
 bit operation we can still determine the missing integer in O(n) time. Any
 entire integer outside of A is still accessible in a single operation.
"
Suppose A[] = {3,4,1,6,2,0}. We are not given this but have instead
 C[6][3] = {{0,1,1},{1,0,0},{0,0,1},{1,1,0},{0,1,0},{0,0,0}} .
In general the number of columns is lg n and C has n lg n entries.
We want to determine the missing number by examining only O(n) entries.
 Hint n + n/2 + n/4 + ... ~= 2n = O(n).
This missing number in this example is 5 or {1,0,1}.

The numbers 0..6 include 4 even and 3 odd numbers. Looking at the n
bits in the last column of C we find 4 even and 2 odd so this missing
number must be odd (last bit 1). The odd numbers present are in rows 1,3.

The reference to array B is interesting. In theory, sorting
methods are order Omega(n lg n). If we had A and were allowed B whose
size matches the range m of possible values in A, then 
we could sort A in O(n+m) time as follows:
   int B[m] = {0};  // array of m 0 values                      m
   for(i=0; i < n; i++) B[ A[i] ]++; // B[] = {1,1,1,1,1,0,1};  n
   for(i=0; i < m; i++)                                         m
     for( j=B[i]; j > 0; j--) )                                n+m
       printf("%d ", i);                                        n
So we have to rule out B[ A[i] ] to prove that sorting is n lg(n).
The nested for loops suggest something worse than linear but is
misleading in this case. The printf is executed exactly n times.
In this question m = n.