Description
Question 1. (20 marks)
Let p2, . . . , pn be real numbers in [0, 1], to be specified later. Consider the following randomized algorithm:
1 x = 1
2 for i = 2 to n
3 With probability pi
, x = i; otherwise x is unchanged.
4 return x
a. 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.
b. 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 flipped, 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.
a. Describe the algorithm in clear and concise English, and prove that it outputs 0 with probability 1/2
and 1 with probability 1/2.
b. 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 = {1, . . . , n}. We are given as input a sequence of edges e1, . . . , em, where for each 1 ≤ i ≤ m,
ei = (j, k) for some j, k ∈ V , j 6= k. For each 0 ≤ i ≤ m, define the undirected graph Gi = (V, Ei)
where E0 = ∅, and for i ≥ 1, Ei = {e1, . . . , ei}. 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
