COS 226 PROBLEM SET 2


1. [Exercise 7.2] Show how the file 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 is partitioned, using both Program 7.2 and the minor modifications suggested in the text.






2. [Exercise 7.7] Write a program to compute the exact value of C_N, and compare the exact value with the approximation 2N ln N for N = 1000, 10000, and 100000.







3. [Exercise 8.10] Draw divide-and-conquer trees for N = 24 and 39.







4. [Exercise 8.26] Draw trees that summarize the merges that Program 8.5 performs, for N = 24 and 39.







5. [Exercise 11.63] Estimate the running time of the program described in Exercise 11.62, as a function of N and M, for large N. Assume that N and M are both powers of 2.







Due: in precept on February 16 or 17.

Do your work on this page (use the back if you must)