随机算法 (Fall 2015)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
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==
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 ==
==Problem 2 ==
Suppose that we flip a fair coin <math>n</math> times to obtain <math>n</math> random bits. Consider all <math>m={n\choose 2}</math> pairs of these bits in some order. Let <math>Y_i</math> be the exclusive-or of the <math>i</math>th pair of bits, and let <math>Y=\sum_{i=1}^m Y_i</math> be the number of <math>Y_i</math> that equal 1.
Suppose that we flip a fair coin <math>n</math> times to obtain <math>n</math> random bits. Consider all <math>m={n\choose 2}</math> pairs of these bits in some order. Let <math>Y_i</math> be the exclusive-or of the <math>i</math>th pair of bits, and let <math>Y=\sum_{i=1}^m Y_i</math> be the number of <math>Y_i</math> that equal 1.
# Show that the <math>Y_i</math> are '''NOT''' mutually independent.
# Show that the <math>Y_i</math> are '''NOT''' mutually independent.
Line 16: Line 14:
# 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==
==Problem 3==
Show that the maximum load when <math>n</math> balls are hashed into <math>n</math> bins using a hash function chosen from a 2-universal family of hash functions is at most <math>O(\sqrt{n})</math> with probability at least 0.99. Generalize this argument to <math>k</math>-universal hash functions.
Show that the maximum load when <math>n</math> balls are hashed into <math>n</math> bins using a hash function chosen from a 2-universal family of hash functions is at most <math>O(\sqrt{n})</math> with probability at least 0.99. Generalize this argument to <math>k</math>-universal hash functions.


Hint: Perhaps the only information we can use about a 2-universal hash function is the number of collisions. What does it become for <math>k</math>-universal hashing?
Hint: Perhaps the only information we can use about a 2-universal hash function is the number of collisions. What does it become for <math>k</math>-universal hashing?

Revision as of 03:33, 13 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

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.

  1. Show that the [math]\displaystyle{ Y_i }[/math] are NOT mutually independent.
  2. 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].
  3. Compute [math]\displaystyle{ \mathbf{Var}[Y] }[/math].
  4. Using Chebyshev's inequality, prove a bound on [math]\displaystyle{ \Pr[|Y-\mathbf{E}[Y]|\ge n] }[/math].

Problem 3

Show that the maximum load when [math]\displaystyle{ n }[/math] balls are hashed into [math]\displaystyle{ n }[/math] bins using a hash function chosen from a 2-universal family of hash functions is at most [math]\displaystyle{ O(\sqrt{n}) }[/math] with probability at least 0.99. Generalize this argument to [math]\displaystyle{ k }[/math]-universal hash functions.

Hint: Perhaps the only information we can use about a 2-universal hash function is the number of collisions. What does it become for [math]\displaystyle{ k }[/math]-universal hashing?