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 Θ(n2) 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.