随机算法 (Spring 2013)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
Line 12: Line 12:
==Problem 3==
==Problem 3==
The original Karger's algorithm returns a min-cut with probability <math>\ge\frac{2}{n(n-1)}</math> after <math>n-2</math> contractions.
The original Karger's algorithm returns a min-cut with probability <math>\ge\frac{2}{n(n-1)}</math> after <math>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>n</math> vertices, first contract the graph down to <math>k</math> vertices using Karger's algorithm. Make <math>\ell</math> copies of the graph with <math>k</math> vertices, and now run Karger's algorithm independently on these <math>\ell</math> copies. Return the smallest returned cut of these <math>\ell</math> instances.  
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>n</math> vertices, first contract the graph down to <math>k</math> vertices using Karger's algorithm. Make <math>\ell</math> copies of the graph with <math>k</math> vertices, and now run Karger's algorithm independently on each of these <math>\ell</math> copies. Return the smallest returned cut of these <math>\ell</math> instances.  
* What is the total number of contractions?
* What is the total number of contractions?
* What is the probability of finding a min-cut?
* What is the probability of finding a min-cut?
* Try to optimize the probability of success subject to the constraint of using no more than <math>2n</math> contractions.
* Try to optimize the probability of success subject to the constraint of using no more than <math>2n</math> contractions.

Revision as of 12:46, 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?

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 optimize the probability of success subject to the constraint of using no more than [math]\displaystyle{ 2n }[/math] contractions.