CS 497 -- Randomized Algorithms

Sariel Har-Peled

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 homework.

  1. Given a random-source that returns a real number between $[0,1]$, devise an algorithm to compute a random permutation of the numbers $1, \ldots, n$ in expected linear time. (You an assume that you have the floor/ceiling function).

  2. (Based on MR 3.4). Consider the following experiment that proceeds in a sequence of rounds. For the first round, we have $n$ balls, which are thrown independently and uniformly at random into $n$ bins. After round $i$, for $i \ge 1$, we discard every ball that fell into a bin by itself in round $i$. The remaining balls are retained for round $i+1$, in which they are again thrown independently and uniformly at random into the $n$ bins.
    Suppose that in some round we have $k=\varepsilon n$ 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 $O(\log\log n)$ rounds.
    Convert the previous part into a true proof that with probability $1-o(1)$, we discard all balls within $O(\log\log n)$ rounds. Hint: call a round good if the number of balls retained is not much more than expected. Show that with probability $1-o(1)$, we get enough good rounds to finish.

  3. MR 4.14. Show that the Quicksort algorithm of Chapter 1 runs in $O(n\log n)$ time with high probability.

  4. Consider a collection of $n$ random variables $X_i$ drawn independently from the geometric distribution with mean 2 - that is, $X_i$ is the number of flips of an unbiased coin up to and including the first heads. Let $X=\sum X_i$. Use two different methods to derive bounds on the probability that $X > (1+\delta)(2n)$ for any fixed $\delta$. Figure out how to reduce to the Chernoff bound we already know for sums of independent Poisson variables.

  5. MR Exercise 4.2. Consider the transpose permutation: writing $i$ as the concatenation of two $n/2$-bit strings $a_i$ and $b_i$, we want to route $a_ib_i$ to $b_ia_i$. Show the bit fixing strategy takes $\Omega(\sqrt{N/n})$ steps on this permutation.

  6. 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^{\Omega(n)}$ steps to route. An inequality that might be helpful:

\left(\frac{n}{k}\right)^k \le {n \choose k} \le

  7. Consider a tournament on $n$ 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 $n$, there is a possible set of outcomes such that no ranking agrees with more than $51\%$ of the games.

Sariel Har-Peled 2001-02-06
Home Bookmarks Papers Blog