Question 1. (20 marks)
Let p2; : : : ; pn be real numbers in [0; 1], to be speci ed later. Consider the following randomized algorithm:
1 x = 1
for i = 2 to n
With probability pi, x = i; otherwise x is unchanged. 4 return x
Consider the value of x returned by the above procedure. Compute Pr[x = i] for each 1 i n, under the assumption that p2 = p3 = : : : = pn = 1=2. Give a precise mathematical derivation of these probabilities.
Give values for p2; : : : ; pn so that for any 1 i n, Pr[x = i] = 1=n, i.e. x is a uniform sample from 1; : : : ; n. Prove that, with the values of p2; : : : ; pn that you give, the probability of x = i is 1=n, as required.
Question 2. (20 marks) Assume you have a biased coin, which, when ipped, falls on Heads with probability p, and on Tails with probability 1 p. However, you do not know p. How can you use the coin to simulate an unbiased coin? Formally, you have access to a procedure FlipBiasedCoin(), which returns either 1 or 0 at random. FlipBiasedCoin() returns 1 with probability p, and 0 with probability 1 p, but you do not know p. Design an algorithm that, without making any other random choices except calling FlipBiasedCoin(), returns 1 with probability 1=2 and 0 with probability 1=2. Your algorithm should not use p. You can assume that each time you call FlipBiasedCoin(), the value it returns is independent of all other calls to it.
Describe the algorithm in clear and concise English, and prove that it outputs 0 with probability 1=2 and 1 with probability 1=2.
Analyze the expected running time of your algorithm. Note that while the algorithm itself does not use p, the expected running time should be expressed in terms of p.
Question 3. (20 marks)
Let V = f1; : : : ; ng. We are given as input a sequence of edges e1; : : : ; em, where for each 1 i m, ei = (j; k) for some j; k 2 V , j 6= k. For each 0 i m, de ne the undirected graph Gi = (V; Ei) where E0 = ;, and for i 1, Ei = fe1; : : : ; eig. Design an algorithm that outputs an array C[0 : : m], with C[i] equal to the number of nodes of the largest connected component of Gi (note that C[0] = 1). Your algorithm should run in time O(n + m log (n)).
Describe the algorithm in clear and concise English. Explain why it is correct and why it runs in the required time complexity.
2
