Homework 1

This homework covers the material from lectures 1 to 4.

Due date: May 28th.

PDF version of Homework 1.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

Remember that you are only required to turn in 5 out of the 6 exercises below.

Problem 1 - Union Find (20 points)

Consider the union-find problem, but with an additional operation DELETE($x$) that removes element $x$ from its current set and places it in a set by itself. Note that later union operations might apply to this new set. The goal of this question is to modify the solutions given in class so that a sequence of $m$ UNION, FIND and DELETE operations on $n$ elements takes $O(m \log^* n)$ time.

1. A first idea is to actually remove the tree node associated with $x$, and link its subtrees back to the root (if $x$ is the root, then pick a any child of $x$ of highest rank to be the new root). Show that this is a bad approach.

2. Give a solution using the idea of “delayed deletion,” where we do not actually remove the tree node of the element that should be deleted, and instead we just mark it dead. Then, when the number of dead nodes goes above half the total number of nodes we do a big cleanup and remove all the dead nodes.

Problem 2 - Splay Trees (20 points)

In this problem we will work out some splaying counterexamples;

1. Single rotations don’t work for splay trees. To show this, consider a degenerate $n$-node linked-list shaped binary tree where each node’s right child is empty. Suppose that the (only) leaf is splayed to the root by single rotations. Show the structure of the tree after this splay. Generalize this to argue that there is a sequence of $n/2$ splays that each take at least $n/2$ work.

2. Now from the same starting tree, show the final structure after splaying the leaf with (zig-zig) double rotations. Explain how this splay has made much more progress than single rotations in “improving” the tree.

3. Given the theorem about access time in splay trees, it is tempting to conjecture that splaying does not create trees in which it would take a long time to find an item. Show this conjecture is false by showing that for large enough $n$, it is possible to restructure any binary tree on $n$ nodes into any other binary tree on $n$ nodes by a sequence of splay requests. Conclude that it is possible to make a sequence of requests that cause the splay tree to achieve any desired shape.

Hint: start by showing how you can use splay operations to make a specified node into a leaf, then recurse.

Problem 3 - Concentration Inequalities (20 points)

In this problem, we are in the setting where given a set $S$ (which is not known to us), we only have access to $S$ by querying a random element from $S$ uniformly at random. Thus, if we want to sample $s$ elements from $S$, we will obtain a sequence of elements $a_1, \ldots, a_s \in S$ where each $a_k$ was drawn from $S$ uniformly at random. Thus it could be the case where $a_i = a_j$ for some $i \neq j$.

1. Show that given a set $S$ of $n$ numbers in $[0, 1]$ it is impossible to estimate the value of the median within $1.1$ multiplicative approximation factor with $o(n)$ samples.

Hint: to show an impossibility result you show two different sets of $n$ numbers that have very different medians but which generate, with high probability, identical samples of size $o(n)$.

2. Now calculate the number of samples needed (as a function of $t$) so that the following is true: with high probability, the median of the sample has at least $n/2 - t$ numbers from $S$ less than it and at least $n/2 - t$ numbers of $S$ more than it.

Problem 4 - Concentration Inequalities (20 points)

The simplest model for a random graph consists of $n$ vertices, and tossing a fair coin for each pair $\{i, j\}$ to decide whether this edge should be present in the graph. Call this model $G(n, 1/2)$. A triangle is a set of $3$ vertices with an edge between each pair.

1. What is the expected number of triangles?
2. What is the variance?
3. Show that the number of triangles is concentrated around the expectation and give an expression for the bound in the decay of probability.

Problem 5 - Balls and Bins (20 points)

Consider again the experiment in which we toss $m$ labeled balls at random into $n$ labeled bins, and let the random variable $X$ be the number of empty bins. We have seen that $\mathbb{E}[X] = n \cdot \left( 1 - \frac{1}{n} \right)^m$.

1. By writing $X = \sum_i X_i$ for suitable random variables $X_i$, show how to derive the following exact formula for the variance of $X$: $$ Var[ X ] = n \cdot \left( 1 - \frac{1}{n} \right)^m + n(n-1) \cdot \left( 1 - \frac{2}{n} \right)^m - n^2 \cdot \left( 1 - \frac{1}{n} \right)^{2m} $$

2. What is the asymptotic value (as $n \rightarrow \infty$) of $Var[ X ]$ in the cases $m = n$ and $m = n \ln(n)$?

3. When throwing $n$ balls into $n$ bins, what is the expected number of bins with exactly one ball? Compute an exact formula and its asymptotic approximation.

Problem 6 - Coupon Collector (20 points)

Let us consider the coupon collector problem: we toss $m = n \log n + cn$ balls into $n$ bins, where $c$ is a constant, and we are interested in the probability that there is no empty bin. We saw in class that $$ Pr[ \text{some bin is empty} ] \leq n \cdot \left( 1 - \frac{1}{n} \right)^m \sim n \cdot \dfrac{1}{e^{m/n}} = \dfrac{1}{e^c}. $$

Prove that $$ Pr[ \text{some bin is empty} ] = \Omega\left( \dfrac{1}{e^c} - \dfrac{1}{2e^{2c}} \right). $$

Hint: Inclusion-Exclusion.

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)

Problem 1 - Amortized Analysis - from CLRS chapter 17

A stack $S$ is a data structure that supports the following operations:

1. PUSH($S, x$) pushes object $x$ on the top of stack $S$
2. POP($S$) pops the top of the stack $S$ and returns the popped object. If one calls POP on an empty stack it returns an error.

We will now modify the stack structure to support the following operation:

3. MULTIPOP($S, k$) removes the $k$ top objects of stack $S$, popping the entire stack if the number of elements in $S$ is less than $k$.

First Question: what is the worst case performance per operation of a sequence of $n$ operations above? Here we want you to give an upper bound on the complexity of the operations PUSH, POP and MULTIPOP.

Second Question: what is the amortized cost of $n$ operations? Use the three methods of amortized analysis to obtain the same bound.

Problem 2 - Amortized Analysis (Potential Method) - from CLRS chapter 17

Design a data structure to support the following two operations for a dynamic multiset $S$ of integers, which allows duplicate values:

1. INSERT($S, x$) inserts $x$ into $S$
2. DELETE-LARGER-HALF($S$) deletes the largest $\lceil |S|/2 \rceil$ elements from $S$

Show how to implement this data structure so that any sequence of $m$ INSERT and DELETE-LARGER-HALF operations runs in $O(m)$ time. Your implementation should also include a way to output the elements of $S$ in $O(|S|)$ time.

Hint: to delete larger half, need to find the median.

Problem 3 - Probability

1. Consider the following probabilistic process:

• start with $ctr = 0$
• Repeat $n$ times: toss a fair coin, and if it comes up heads, make $ctr += 1$. Otherwise, make $ctr -= 1$.

If $X$ is the random variable defined as the value of our counter $ctr$ at the end of the process above:

• Compute $\mathbb{E}[X]$
• For even $n$, show that $\Pr[X = 0] \sim \sqrt{2/(\pi n)}$. What happens for odd $n$?

Problem 4 - Covariance and Variance of Correlated Random Variables

In this question we will explore how to use covariance to compute the variance of correlated random variables

1. Let $X_1, \ldots, X_n$ be random variables such that $X_i = X_j$ and $$X_1 = \begin{cases} 1, \text{ with probability } 1/2 \\ 0, \text{ otherwise} \end{cases}$$ thus, we are in the case where the random variables are the same random variable.

Let $X = x_1 + X_2 + \cdots + X_n$. Compute $Var[X]$.

2. Let $X_1, \ldots, X_n$ be random variables such that $$X_1 = \begin{cases} 1, \text{ with probability } 1/2 \\ 0, \text{ otherwise} \end{cases}$$ and for $2 \leq i \leq n$ we have $$X_i = \begin{cases} X_1, \text{ with probability } 1/(2i) \\ 1 - X_1, \text{ otherwise} \end{cases}$$

Let $X = X_1 + X_2 + \cdots X_n$. Compute $Var[X]$.

Problem 5 - Martingales

Consider a fair game in a casino: on each play, you may stake any amount $S$ of money. You win or lose with probability $1/2$ each time (and all instances of the game are independent). If you win you get back your stake plus $S$, and if you lose you lose your stake.

1. What is the expected number of plays until you first win?

2. The following gambling strategy, known as the “martingale,” was popular in European casinos in the 18th century: on the first play, stake $1$; on the second play stake $2$; on the $k^{th}$ play, stake $2^{k-1}$. Stop playing and leave the casino when you first win!

Show that if you follow the martingale strategy, you will leave the casino $1$ unit of money richer with probability 1! (this is probably a reason why this strategy is banned in most casinos. Also, this course is not providing any gambling advice)

3. Let us know discuss the catch in the strategy above: let $X$ be the random variable that measures your maximum loss before winning. Show that $\mathbb{E}[X] = \infty$. What does this imply about your ability to play the matringale strategy in practice?

Problem 6 - Generating random strings

Alice and Bob have a fair coin and they are trying to generate a random sequence of 2n coin tosses containing exactly $n$ heads and $n$ tails.

1. Alice suggests to flip the coin $2n$ times. If we get exactly $n$ heads, output the sequence; otherwise, try again. How many tosses do you expect Alice will have to make under this scheme?

2. Bob claims that he has a much more efficient scheme: flip the coin until you have either $n$ heads or $n$ tails. Output this sequence, padded at the end with tails or heads respectively to make the total length $2n$. Clearly this scheme requires at most $2n$ tosses. Is this a good scheme? Justify your answer with a proof.

3. Suggest a simple scheme for solving this problem that is better than the previous two schemes. How many tosses does your scheme require in expectation?

Problem 7 - Concentration Inequalities

Questions from lecture 3:

1. Is Markov’s inequality tight? If it is, give examples of random variables for which it is tight.

2. Give examples of discrete probability distributions which do not have a $k^{th}$ moment. Also give examples of discrete probability distributions which do not have a $k^{th}$ central moment.

3. Can you generalize Chebyshev’s inequality for higher order moments?

4. Work out the proof of the lower tail bound for Chernoff’s bound.

5. Work out the proof of Hoeffding’s generalization of Chernoff’s inequality.