1. (M-U 3.8) Suppose that algorithm A chooses a single random number in the range from 1 to n and then performs a computation that, if all choices are equally likely, takes expected time O(n^2). What can you say about the worst-case time for algorithm A? Hint: use Markov's inequality. 2. (M-U 3.21) Let p be a random permutation of n items, with all permutations equally likely. (a) What is the probability that item i is mapped to itself by permutation p? Use your answer to compute E[X] where X is the number of items that are mapped to themselves. (b) What is the probability that both members of an ordered pair (i,j) are mapped to themselves by the permutation? (It will depend on whether i=j.) Relate X^2 (where X is the same as the previous part) to the number of ordered pairs that are mapped to themselves, and use your answer to compute Var[X]. 3. (a) Suppose that you generate two n-bit binary strings at random (e.g. by flipping a coin n times). Use Chernoff bounds to estimate the probability p that the two strings differ in at least n/4 positions. (b) Suppose that you generate K different strings, and let X be the number of pairs of strings that differ in fewer than n/4 positions. Use your answer to part (a) to estimate the maximum number K you can choose for which E[X] < 1. (You can conclude from your answer to 3(b) that there exists a set of K different binary strings, all differing by at least n/4 positions, and with a little more care the same method can be used to show it is possible in n-dimensional Euclidean space for K non-overlapping unit spheres to all touch a single central unit sphere. For instance, in 3d, 12 spheres centered on the vertices of a regular icosahedron can all touch a central sphere of the same size without touching each other, but it's not possible for 13 spheres to do this.)