NAME:

PRECEPT:

COS 226 Exercises on Quicksort and Mergesort


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 Program 7.2. Then show how the same file is partitioned if we replace the condition (i >= j) by (i > j). Give the contents of the file and the values of i and j after partitioning is complete, in both cases.






2. [Exercise 7.7] Write a program to compute the exact value of C_N (C_N is defined under Property 7.2), and compare the exact value with the approximation 2N ln N for N = 1000, 10000, and 100000. Use double precision arithmetic.







3. [Exercise 8.10] Draw the divide-and-conquer tree for N = 24.







4. Solve the following recurrence for all positive integers N which are powers of 2: T(1) = 0, T(N) = T(N/2) + 1 if N >= 2. Prove your answer by mathematical induction.













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