COS 226 Exercises on Quicksort and Mergesort

NAME:

LOGIN:

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. 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.