Data Structures - Assignment no. 6, June 6, 2007

Remarks:

• Please write your exercises in pen, or in clearly visible pencil. Please write very clearly.

• For every question where you are required to write pseudo-code, also explain your solution in words.

1. Manually run the quicksort algorithm on the array (16,3,89,13,9,45,5,17,4,90,14,10,46,6,30). Assume that at every step the pivot that is chosen is the median element.

2. In this question we discuss a model called the “extended comparison model”, which is like the comparison model, except that you are allowed 5 types of questions: (i) “a = b?”, (ii) “a < b?”, (iii) “a > b?”, (iv) “a < b + 100?”, (v) “a > b + 100?”. Prove a lower bound of Ω(n log n) for sorting an array of size n in the extended comparison model.

3. (a) You are given two arrays, A and B, each of size n. Give an algorithm that returns an array C of size n, such that C[i] is equal to the number of elements of A that are less or equal to B[i]. The algorithm should run in time O(n log n). Describe the algorithm and explain why the running time is O(n log n). You do not have to give pseudo-code.

(b) Prove a lower bound of Ω(n log n) for this problem in the comparison model. \underline{Hint:} You can prove this lower bound directly. However, it is easier to give a reduction. To do this, you should: (i) Prove that if you can solve this problem in time f(n) then you can sort an array of size n in time O(f(n) + n); (ii) Deduce from this that if you can solve this problem in time f(n) then f(n) = Ω(n log n).

4. (a) You are given an array of size n, which contains log n distinct elements, each of them occurring exactly \frac{n}{log n} times. Give an algorithm that sorts this array in time O(n log log n). Describe the algorithm and explain why the running time is O(n log log n). You do not have to give pseudo-code.

(b) Prove a lower bound of Ω(n log log n) in the comparison model for this problem. \underline{Hint:} Work like the lower bound that you have seen in class. First prove that there must be at least (n!)/ ((n/ log n)!)^{log n} leaves in the comparison tree. Then use Stirling’s approximation of n! to prove that the depth of the tree is Ω(n log log n). When using Stirling’s approximation, it is enough to use that:

n! = Θ (\sqrt{n} (\frac{n}{e})^{n})

You can use this approximation without proving it.