**CS212: Data
Structures and Algorithms**

**Homework 7**

**Problem 1.** Show how in-place Quicksort would sort the
following list of numbers: 8 3 1 9 6 2 4 5. First, show the swaps that would take place if the last
element were chosen as the pivot. Then show the list after the two recursive calls.

** **

**Problem 2.** Explain why QuickSort is still O(n lg n)
expected time, even when it uses InsertionSort repeatedly to sort sub-lists of
15 or fewer items. Recall that InsertionSort is an Θ(n^{2}) algorithm.

**Problem 3.** What is a randomized algorithm? Explain
why we might prefer an expected runtime of Θ(n log n) for a randomized
algorithm to an average-case runtime of Θ(n log n) for a deterministic
algorithm. (For example, why would we prefer Randomized QuickSort to
Deterministic (non-randomized) QuickSort? – But don’t limit your answer to
QuickSort.)

** **

**Problem 4.** Show how a modified radix-2 (i.e.,
bitwise) Radix Sort would sort the following list of numbers: 0100 0010 1011
1101 1010 0101 0110 1110. The modified version of Radix sort should sort the
numbers by the two most significant bits using normal Radix sort and then
finish up with a pass of Insertion sort. Show the list after each pass of radix sort and
after the Insertion sort pass. How many swaps did the Insertion sort pass have
to make?

**Problem 5.** Show how an Odd-Even Merge
could be used to sort the numbers 8 3 12 9 16 1 14 2 13 7 4 11 6 5 10
15 in parallel. You may assume you have an oracle that can sort and
merge lists of size 8; you don't have to show the details for those
parts of the algorithm. Just show the contents of the array after the
recursive sort calls, merge calls, and cleanup phase.
What steps can take place in parallel?

**Problem 6.** C-4.14.