随机算法 (Spring 2013)/Problem Set 1: Difference between revisions
imported>Etone |
imported>Etone |
||
| Line 18: | Line 18: | ||
* What is the probability of finding a min-cut? | * What is the probability of finding a min-cut? | ||
* Try to find the optimal values of <math>k</math> and <math>\ell</math> which maximizes the probability of success subject to the constraint of using no more than <math>2n</math> contractions. | * Try to find the optimal values of <math>k</math> and <math>\ell</math> which maximizes the probability of success subject to the constraint of using no more than <math>2n</math> contractions. | ||
== Problem 3== | |||
For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected graph <math>G(V,E)</math>is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>. | |||
Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices and <math>m</math> edges. | |||
Revision as of 13:03, 11 March 2013
Problem 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].
Problem 2
We start with [math]\displaystyle{ n }[/math] people, each with 2 hands. None of these hands hold each other.
At each round, we uniformly pick 2 free hands and let them hold together.
- After how many rounds, there are no free hands left?
- What is the expected number of cycles made by people holding hands with each other (one person with left hand holding right hand is also counted as a cycle), when there are no free hands left?
(Hint: Consider how to count the number of cycles using indicator random variables.)
Problem 3
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 each of 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 find the optimal values of [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math] which maximizes the probability of success subject to the constraint of using no more than [math]\displaystyle{ 2n }[/math] contractions.
Problem 3
For any [math]\displaystyle{ \alpha\ge 1 }[/math], a cut [math]\displaystyle{ C }[/math] in an undirected graph [math]\displaystyle{ G(V,E) }[/math]is called an [math]\displaystyle{ \alpha }[/math]-min-cut if [math]\displaystyle{ |C|\le\alpha|C^*| }[/math] where [math]\displaystyle{ C^* }[/math] is a min-cut in [math]\displaystyle{ G }[/math].
Give an analysis to lower bound the probability that a single iteration of Karger's Random Contraction algorithm returns an [math]\displaystyle{ \alpha }[/math]-min-cut in a graph [math]\displaystyle{ G(V,E) }[/math] of [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges.