随机算法 (Fall 2015)/Problem Set 2: Difference between revisions
imported>Etone No edit summary |
imported>Etone No edit summary |
||
Line 6: | Line 6: | ||
* Use the above bound to estimate the number of distinct <math>\alpha</math>-min cuts in <math>G</math>. | * Use the above bound to estimate the number of distinct <math>\alpha</math>-min cuts in <math>G</math>. | ||
== Problem 2 | == Problem 2== | ||
Consider the Min-Cut problem in edge-weighted graphs. Describe how you would generalize Karger's contraction algorithm to this case. What is the running time and success probability of your algorithm. | Consider the Min-Cut problem in edge-weighted graphs. Describe how you would generalize Karger's contraction algorithm to this case. What is the running time and success probability of your algorithm. | ||
Line 15: | Line 15: | ||
# Compute <math>\mathbf{Var}[Y]</math>. | # Compute <math>\mathbf{Var}[Y]</math>. | ||
# Using Chebyshev's inequality, prove a bound on <math>\Pr[|Y-\mathbf{E}[Y]|\ge n]</math>. | # Using Chebyshev's inequality, prove a bound on <math>\Pr[|Y-\mathbf{E}[Y]|\ge n]</math>. | ||
==Problem 4== | |||
Suggest a scheme for "four point" sampling |
Revision as of 03:37, 6 November 2015
Problem 1
For any [math]\displaystyle{ \alpha\ge 1 }[/math], a cut [math]\displaystyle{ C }[/math] in an undirected (multi)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 a lower bound to 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.
- Use the above bound to estimate the number of distinct [math]\displaystyle{ \alpha }[/math]-min cuts in [math]\displaystyle{ G }[/math].
Problem 2
Consider the Min-Cut problem in edge-weighted graphs. Describe how you would generalize Karger's contraction algorithm to this case. What is the running time and success probability of your algorithm.
Problem 3
Suppose that we flip a fair coin [math]\displaystyle{ n }[/math] times to obtain [math]\displaystyle{ n }[/math] random bits. Consider all [math]\displaystyle{ m={n\choose 2} }[/math] pairs of these bits in some order. Let [math]\displaystyle{ Y_i }[/math] be the exclusive-or of the [math]\displaystyle{ i }[/math]th pair of bits, and let [math]\displaystyle{ Y=\sum_{i=1}^m Y_i }[/math] be the number of [math]\displaystyle{ Y_i }[/math] that equal 1.
- Show that the [math]\displaystyle{ Y_i }[/math] are NOT mutually independent.
- Show that the [math]\displaystyle{ Y_i }[/math] satisfy the property [math]\displaystyle{ \mathbf{E}[Y_iY_j]=\mathbf{E}[Y_i]\mathbf{E}[Y_j] }[/math].
- Compute [math]\displaystyle{ \mathbf{Var}[Y] }[/math].
- Using Chebyshev's inequality, prove a bound on [math]\displaystyle{ \Pr[|Y-\mathbf{E}[Y]|\ge n] }[/math].
Problem 4
Suggest a scheme for "four point" sampling