Due: Tuesday, Feb. 17, at the start of class.
Problem 9.2-1 (page 189) (RANDOMIZED-SELECT is on page 186.) Hint: What are the requirements on p, r and i, for the initial call (by somebody else)? Write them down. Are the requirements necessarily met in the recursive calls?)
Problem 9.3-8 (page 193) (Hint: What if you find the median of each array. That breaks each array in half. Can you eliminate half of each array from consideration for the median of the combined arrays?)
Problem 9.3-9 (page 193) (This should be very easy. But do not try to solve it by ad-hoc means, the way you might have before studying this chapter.)