Unformatted text preview:

� � � � � � � �� � � �� � 6.856 — Randomized Algorithms David Karger Handout #7, September 25, 2002 — Homework 4, Due 10/2 1. (a) Based on MR Exercise 4.2. Consider the transpose permutation: writing i as the concatenation of two n/2-bit strings ai and bi, we want to route aibi to biai. Show the bit fixing strategy takes Ω(√N) steps on this permutation. (b) MR 4.9. Consider the following variant of the bit fixing algorithm. Each packet randomly orders the bit positions in the label of its source and then corrects the mismatched bits in that order. Show that there is a permutation for which with high probability that algorithm uses 2Ω(n) steps to route. An inequality that might be helpful: n �k n en �k . k ≤ k ≤ k 2. Consider a collection of n random variables Xi drawn independently from the geometric that is, Xi is the number of flips of an unbiased coin up to and including the first occurrence of heads. Let X = Xi. Use two different methods to derive bounds on the probability that X > (1 + �)(2n) for any fixed �: (a) Figure out how to reduce this to a question involving just the sum of independent Poisson (i.e. indicator) variables, allowing you to apply the Chernoff bound we already know. (b) Use the method of the in-class Chernoff bound analysis to derive ab initio an upper bound for deviation of sums of geometric random variables. 3. The probabilistic method can also be used to prove lower bounds, basically by applying the method on behalf of the adversary. (a) Let Xi, i = 1, . . . , n, be unbiased independent 0/1 variables. Prove that for some positive constant c, distribution with mean 2 – Pr > c√n Xi − n/2 > 3/4 (b) Prove that there is an instance of the set balancing problem with n sets over a universe n elements such that no partition of the universe has bias smaller than Ω(√n). That is, every partition will split some set very unevenly. (See also problem 7 below.) 1 M. R. refers to this text:Motwani, Rajeez, and Prabhakar Raghavan. Randomized Algorithms. Cambridge: Cambridge University Press, 1995.� � 4. Consider the algorithm of the second lecture for finding a minimum cut in a graph. nUse it to prove that no graph has more than 2 minimum cuts. Hint: your answer should be very brief. 5. survey question (not optional) Was it worth taking time to prove the Chernoff bound in class, or would it have been just as useful simply to present the theorem and point to the textbook? 6. (optional) For every k there exists a large graph that has no clique of size k and no independent set of size k. Prove the largest bound you can on the number of vertices in such a graph (as a function of k). That is, exhibit the biggest graph you can that has neither the clique nor the independent set. 7. (optional) In class, we proved that any set-balancing problem on n sets from a universe of size n can be solved up to a “discrepancy” of O(√n ln n). Above, we proved that some instances require a discrepancy of Ω(√n). In fact it is the lower bound that is tight. Tighten our upper bound: give a proof that any set-balancing can be solved with an o(√n ln n) discrepancy.


View Full Document

MIT 6 856J - Homework

Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?