Description

Format: Please start each problem on a new page.
Where to submit: On Gradescope, please mark the pages for each question
1 Problem 1 (24 points)
Recall that when using the QuickSort algorithm to sort an array A of length n, we picked an element x ∈ A which we called the pivot and split the array A into two arrays AS,AL such that ∀y ∈ AS,y ≤ x and ∀y ∈ AL,y > x.
We will say that a pivot from an array A provides t|n − t separation if t elements in A are smaller than or equal to the pivot, and n − t elements are strictly larger than the pivot.
Suppose Bob knows a secret way to find a good pivot with separation in constant time. But at the same time Alice knows her own secret technique, which provides separation , her technique also works in constant time.
Recall that in the QuickSort algorithm, as per Section 7.1 in CLRS, the PARTITION subroutine picks a pivot x from A by simply picking the first element in the array. Alice and Bob’s subroutines are subroutines for picking the pivot x in the PARTITION subroutine for QuickSort.
Alice and Bob applied their secret techniques as subroutines in the QuickSort algorithm to pick pivots. Whose algorithm works asymptotically faster? Or are the runtimes asymptotically the same? Prove your statement.
1
2 Problem 2 (13 points)
Resolve the asymptotic complexity of the following recurrences, i.e., solve them and give your answer in Big-Θ notation. Use Master theorem, if applicable. In all examples assume that T(1) = 1. To simplify your analysis, you can assume that n = ak for some a,k.
Your final answer should be as simple as possible, i.e., it should not contain any sums, recurrences, etc.
1.
2.
3.
4.
5.
3 Problem 3 (13 points)
Let A and B be two sorted arrays of n elements each. We can easily find the median element in A – it is just the element in the middle – and similarly we can easily find the median element in B. (Let us define the median of 2k elements as the element that is greater than k−1 elements and less than k elements.) However, suppose we want to find the median element overall – i.e., the nth smallest in the union of A and B.
As usual, prove correctness and the runtime of your algorithm.
2