All problem / exercise numbers are from the 3nd edition of Introduction to Algorithms (the 1st and 2nd editions are different!) Note the difference between problems and exercises!
1. Special Cases of Select:
(a) Give an algorithm to find the second smallest element in a list of n elements in at most n + |lg n| - 2 comparisons. Note: Your algorithm can use no more than n + |lg n| - 2 total comparisons in the worst case. Hint: Find the smallest element, too.
(b) Give an algorithm to find the 3rd smallest element in a list, using the smallest number of worst-case comparisons. Exactly how many comparisons does your algorithm take in the worst case? Hint: Use your solution to part a - you will need to find the smallest and second-smallest element as well!
2. Exercise 9.3-6 quantiles
The kth quantiles of an n-element set ar the k -1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the k-th quantiles of a set. Elements within each quantitle can be listed in any order.
3. Exercise 9.3-8 Finding the median of two lists of numbers
Let X[1 . . . n] and Y [1 . . . n] be two arrays, each containing n elemetns already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y .
4. Does inserting and then immmediately deleting a unique element from a Binary Search Tree always leave the same tree? Does inserting and then immediatley deleting a unique element from a Red/Black tree always leave the same tree?
5. Exercise 14.3-6 (MIN-GAP) Show how to extend a red-black tree to support the operation MIN-GAP, which gives the magnitude of the difference of the two closest numbers in the tree. For example, if Q = {1, 5, 9, 15, 18, 22} then MIN-GAP(Q) returns 18-15 = 3 since 15 and 18 are the two closest numbers in Q.