CS 497 -- Randomized Algorithms
Homework 2, Due 2/20
Collaboration on solving homeworks is strongly encouraged.
However, each person must independently write up their
own solution. You must list all collaborators on your
- Given a random-source that returns a real number
between , devise an algorithm to compute a random
permutation of the numbers in expected
linear time. (You an assume that you have the
- (Based on MR 3.4). Consider the following
experiment that proceeds in a sequence of rounds.
For the first round, we have balls, which are thrown
independently and uniformly at random into bins.
After round , for , we discard every ball
that fell into a bin by itself in round . The
remaining balls are retained for round , in which
they are again thrown independently and uniformly at
random into the bins.
- Suppose that in some round we have
balls. How many balls should you
expect to have in the next round?
- Assuming that everything proceeded according
to expectation, prove that we would discard all the
balls within rounds.
- Convert the previous part into a true proof
that with probability , we discard all balls
within rounds. Hint: call a
round good if the number of balls retained is
not much more than expected. Show that with
probability , we get enough good rounds to
- MR 4.14. Show that the Quicksort algorithm of
Chapter 1 runs in time with high probability.
- Consider a collection of random variables
drawn independently from the geometric distribution
with mean 2 - that is, is the number of flips of an
unbiased coin up to and including the first heads. Let
. Use two different methods to derive bounds
on the probability that
for any fixed
. Figure out how to reduce to the Chernoff bound
we already know for sums of independent Poisson variables.
- MR Exercise 4.2. Consider the transpose
permutation: writing as the concatenation of two
-bit strings and , we want to route
to . Show the bit fixing strategy takes
steps on this permutation.
- 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 steps to route. An inequality that
might be helpful:
- Consider a tournament on teams, in which
each pair of teams plays against each other once and a
winner is always declared. Suppose we try to rank the
teams in some total order based on the outcome of the
tournament. Say that a game agrees with the ranking
we have chosen if the team we ranked better won. Prove
that for sufficiently large , there is a possible set
of outcomes such that no ranking agrees with more than
of the games.