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.