Randomized Algorithms (Spring 2010)/Problem Set 1

Problem 1

[MR]-1.1

Suppose that you are given a coin for which the probability of HEADS, say [math]\displaystyle{ p }[/math], is unknown. How can you use this coin to generate unbiased (i.e., [math]\displaystyle{ \Pr[\mathrm{HEADS}]=\Pr[\mathrm{TAILS}]=1/2 }[/math]) coin-flips? Give a scheme for which the expected number of flips of the biased coin for extracting one unbiased coin-flip is no more than [math]\displaystyle{ \frac{1}{p(1-p)} }[/math].

(Hint: Consider two consecutive flips of the biased coin.)

Problem 2

The original Karger's algorithm returns a min-cut with probability [math]\displaystyle{ \ge\frac{2}{n(n-1)} }[/math] after [math]\displaystyle{ n-2 }[/math] 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 [math]\displaystyle{ n }[/math] vertices, first contract the graph down to [math]\displaystyle{ k }[/math] vertices using Karger's algorithm. Make [math]\displaystyle{ \ell }[/math] copies of the graph with [math]\displaystyle{ k }[/math] vertices, and now run Karger's algorithm independently on these [math]\displaystyle{ \ell }[/math] copies. Return the smallest returned cut of these [math]\displaystyle{ \ell }[/math] instances.

• What is the total number of contractions?
• What is the probability of finding a min-cut?
• Try to optimize the probability of success with respect to the constraint of using no more than [math]\displaystyle{ 2n }[/math] contractions.

Problem 3

Recall the following definitions:

Definition 2: The class NP consists of all decision problems [math]\displaystyle{ f }[/math] that have a polynomial time deterministic algorithm [math]\displaystyle{ V }[/math] such that for any input [math]\displaystyle{ x }[/math], [math]\displaystyle{ f(x)=1 }[/math] if and only if [math]\displaystyle{ \exists y }[/math], [math]\displaystyle{ V(x,y)=1 }[/math], where the size of [math]\displaystyle{ y }[/math] is within polynomial of the size of [math]\displaystyle{ x }[/math].

Definition 4: The class ZPP consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in expected polynomial time for any input such that for any input [math]\displaystyle{ x }[/math], [math]\displaystyle{ A(x)=f(x) }[/math].

Definition 5: The class RP consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in worst-case polynomial time such that for any input [math]\displaystyle{ x }[/math], if [math]\displaystyle{ f(x)=1 }[/math], then [math]\displaystyle{ \Pr[A(x)=1]\ge 1-1/2 }[/math]; if [math]\displaystyle{ f(x)=0 }[/math], then [math]\displaystyle{ \Pr[A(x)=0]=1 }[/math].

Prove that ZPP[math]\displaystyle{ \subseteq }[/math]NP and RP[math]\displaystyle{ \subseteq }[/math]NP.

(Hint: Notice that a randomized algorithm [math]\displaystyle{ A }[/math] on input [math]\displaystyle{ x }[/math] can be represented as a deterministic algorithm [math]\displaystyle{ D }[/math] with two input: [math]\displaystyle{ x }[/math] and a sequence [math]\displaystyle{ s }[/math] of random bits.)

Problem 4

A parallel computer consists of [math]\displaystyle{ n }[/math] processors and [math]\displaystyle{ n }[/math] 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 during a step. There are two schemes for dealing with conflicted memory requests:

1. Upon receiving more than one requests, a memory module does not answer any request.
2. 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 [math]\displaystyle{ \left(1-\frac{1}{n}\right)^n\approx\frac{1}{e} }[/math].)