1. Much of the information used to compute the median-of-median-of-?ve is thrown away. Show how the number of comparisons can be reduced by more careful use of the information.
2. Complete the analysis of the sampling algorithm described at the end of Section 10.2.3, and explain how the values of δ and s are chosen.
3. Show how the recursive multiplication algorithm computes XY, where X = 1234 and Y = 4321. Include all recursive computations.
4. Show how to multiply two complex numbers X = a + bi and Y = c + di using only three multiplications.
5. a. Show that XLYR + XRYL = (XL + XR)(YL + YR) - XLYL - XRYR
b. This gives an O(N1.59) algorithm to multiply N-bit numbers. Compare this method to the solution in the text.