## 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