1. Do problem 7-4. For part c, re-write the pseudo-code and give a reasonable arguement that your change does not affect the running time; you should not need to revise the analysis.

2. In class we described an implementation of randomized selection which begins by shuffling the input items into a random permutation. This style of randomization is discussed in Section 5.3 in the book. Read this section; you can ignore the analysis of PERMUTE-BY-SORTING. Then do exercise 5.3-4.

3. Do problem 5.2-4. Are the events corresponding to the indicator variables that you use independent?

4. Do Problem 5-1, part a only.
Hint: Consider the event e_n,k that after n increment operations the counter has value k. Then try to express P[e_n+1,k] as a function of Pr[e_n,k] and Pr[e_n,k-1].