Due: Wednesday, June 2. Please make your solutions clear and readable. Make your arguments so that at least you find them convincing.
Exercise 4-1(a,b,c,d,e), page 85.
Exercise 4-2, page 85. To make this a little more clear, suppose that you have a list of n binary numbers, and the only operation that you have for looking at those numbers is a function bit(i,j) that tells you the i-th bit of the j-th number. Assume that the numbers are indexed from 1 to n, and the bits are indexed from 0 (the lowest order bit) upward. For example, if A[3] holds binary number 11001, then bit(1,3) = 0, since the bit in position 1 (the next-to-rightmost bit) of this number is 0. Be sure to remember that this is the only way you have of getting information about the numbers. Your algorithm must make only O(n) calls to the bit function. Try a small example by hand.
Exercise 4-6, page 87(b,c).
Exercise 7-3, page 161. To demonstrate that stooge-sort is correct, think about the first, middle and last thirds of the result. For example, if a number should end up in the first third, does it? Follow it through the steps of the algorithm. Where will it move to? What if a number belongs in the last third? Will it go there? The middle third should be easy, once you know that the first and last thirds are done correctly. After you know about the thirds, all you need to show is that each third is sorted when the algorithm is done.
Exercise 9.3-9, page 193. (This should be very easy.)
Exercise 9-1, page 194. Only consider parts (a) and (c). Analyze each under that assumption that selection takes O(n) time and sorting takes O(n log(n)) time.