CSE 2331 Homework 6
Please do not write on the question sheet. You must show all work to receive
any credit.
1. Let xs = [11, 5, 24, 13, 6, 2, 9, 14, 4, 7, 8].
(a) Draw the execution of r ← Partition(xs, 0, 10, 9).
(b) What is r?
2. We saw in class that deterministic and randomized Quicksort both
have O(n2) worst-case time.
(a) What causes the worst-case behavior?
(b) Why does randomizing the pivot help? Hint: Think about the
analysis of randomized Quicksort.
3. Suppose we are given a procedure, PickPivot, that takes an array
as input and is guaranteed to return an element that is a k-th order
statistic for some 1
4
n ≤ k ≤ 3
4
n on arrays of size n in worst-case linear-
time.
(a) Give pseudocode demonstrating how PickPivot can be used to
improve Quicksort and perform worst case analysis of its run-
ning time assuming distinct values in the input array.
(b) Give pseudocode demonstrating how PickPivot can be used to
find the (lower) median and perform worst case analysis of its
running time assuming distinct values in the input array.
(c) What, if anything, changes in your analysis if PickPivot’s guar-
antee only holds asymptotically?
4. Suppose we are given a worst-case linear-time (lower) median-finding
procedure, HappyMedian. In other words, perhaps your answer to
3b. Give a worst-case linear-time algorithm to find the k-th order
statistic. Show your analysis.