We saw the heapsort family of algorithms (with its applications to priority queues) as explained in Chapter 6. We also looked at Quicksort and randomized Quicksort, both of which we analyzed (see quicksort.pdf for a write-up of the analysis). We began talking about the Selection problem (Sections 9.1, 9.2) and saw how to do randomized selection. It turns out that the proper analysis of the randomized selection problems uses a bit more mathematics than we want to use in this class, so we will skip it, but we will talk about how to do selection deterministically in linear time next class (Section 9.3 if you want to read ahead). We also had a quick glance at sorting in linear time (Sections 8.2 and 8.4.)
Next time we will talk about divide & conquer methods (9.3 and 33.4) and dynamic programming (parts of chapter 15).
Submission: you can submit the homework to me either by hardcopy in class or email it to me.
1. [Heapsort, 20pt] Perform heapsort on the array [16, 13, 3, 2, 5, 8, 7, 12, 9]. Show your work on the array (rather than drawing binary trees). Show the details of Build-Max-Heap and how heapsort finds the two largest elements (i.e. do not sort the whole array).
2. [Heapsort, 10pt] What is the running time of heapsort on the array [n, n-1, ..., 2, 1]?
3. [Quicksort, 30pt] Perform quicksort (as shown on page 146 of CLRS) on the array [9, 5, 2, 8, 4, 3, 1, 7]. Show the details of all the partitioning steps one by one.
4. [Stoogesort, 20pt] Do Exercise 7-3 parts a. and b. on page 161 of the book. Hint: To analyze the running time, use the three method we saw (also see Section 4.2). Draw the first two or three levels explicitly and do the summation carefully, that should show you the structure.
5. [Duplicates, 20pt] Write pseudocode for an algorithm that takes an array A as an input and returns the array with all duplicates removed (that is every element should occur at most once after your algorithm has run); the running time should be O(n log n). Your algorithm should also run in-place, that is you are not allowed to use a second array, but just the storage space that A offers you. Remember to adjust the length of A appropriately at the end of your algorithm (removing duplicates will make the array shorter). Note: you do not need to include code for anything we have already implemented, simply use it, if it comes in handy.
6. [Extra Credit] We saw that priority queues can be built using max-heaps. One of the operations we allowed was INCREASE-KEY(A, x, k). Why did we not have a DECREASE-KEY(A,x,k)?
7. [Extra Credit] Show how to find the second-largest element in an array using at most n + log n + O(1) comparisons.