Randomized Algorithms (Spring 2010)/Problem Set 1
Contents
Problem 0 (10 points)
你的姓名，学号。
Problem 1 (10 points)
[MR]1.1
 Suppose that you are given a coin for which the probability of HEADS, say , is unknown. How can you use this coin to generate unbiased (i.e., ) coinflips? Give a scheme for which the expected number of flips of the biased coin for extracting one unbiased coinflip is no more than .
 (Hint: Consider two consecutive flips of the biased coin.)
 (Bonus problem) Devise an extension of the scheme that extracts the largest possible number of independent, unbiased coinflips from a given number of flips of the biased coin.
Problem 2 (10 points)
The original Karger's algorithm returns a mincut with probability after contractions. We have seen that by running the original Karger's algorithm for multiple times, the probability of success can be improved. Consider the following variation. Starting with a graph with vertices, first contract the graph down to vertices using Karger's algorithm. Make copies of the graph with vertices, and now run Karger's algorithm independently on these copies. Return the smallest returned cut of these instances.
 What is the total number of contractions?
 What is the probability of finding a mincut?
 Try to optimize the probability of success subject to the constraint of using no more than contractions.
Problem 3 (10 points)
Recall the following definitions:
Definition 2: The class NP consists of all decision problems that have a polynomial time deterministic algorithm such that for any input ,

Definition 4: The class ZPP consists of all decision problems that have a randomized algorithm running in expected polynomial time for any input such that for any input , . 
Definition 5: The class RP consists of all decision problems that have a randomized algorithm running in worstcase polynomial time such that for any input ,

Prove that ZPPNP and RPNP.
(Hint: Notice that a randomized algorithm on input can be represented as a deterministic algorithm with two inputs: and a sequence of random bits.)
Problem 4 (10 points)
A parallel computer consists of processors and memory modules. During a step, each processor sends a memory request to one of the memory modules, and each memory modul answer the request if it receives exactly one request. Note that a memory module may receive more than one requests. There are two schemes for dealing with conflicted memory requests:
 Upon receiving more than one requests, a memory module does not answer any request.
 Upon receiving more than one requests, a memory module answers one of the received requests.
Assuming that each processor sends a request to a memory module chosen uniformly and independently at random:
 (a) with the first scheme, what is the expected number of processors whose requests are answered?
 (b) with the second scheme, what is the expected number of processors whose requests are answered?
 (c) We upgrade the memory of the machine, so that a memory module that receives either one or two requests can answer its request(s); modules that receive more than two requests will answer two requests and discard the rest. What is the expected number of processors whose requests are answered?
(You may assume the approximation .)