Homework 1

This homework covers the material from lectures 1 to 4.

Due date: September 20th, 11:59pm Waterloo time.

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 - Amortized Analysis (20 points)

Part 1 (10 points)

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.

Part 2 (10 points)

An ordered stack is a data structure that stores a sequence of items and supports the following operations:

1. OrderedPush($x$) removes all items smaller than $x$ from the beginning of the sequence and then adds $x$ to the beginning of the sequence.
2. Pop() deletes and returns the first item in the sequence, or NULL if the sequence is empty.

Suppose we implement an ordered stack with a simple linked list, using the obvious OrderedPush and Pop algorithms. Prove that if we start with an empty data structure, the amortized cost of each OrderedPush or Pop operation is $O(1)$.

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 (each splay using only single rotations) 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)

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 4 - Concentration Inequalities (20 points)

In this problem, we are in the setting where given a set $S$ (which is not known to us - and this set does not have repeated elements), 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,\dots ,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\ne 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. Given a set $S$ of $n$ numbers as in part 1, 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 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 {(1-\frac{1}{n})}^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 {(1-\frac{1}{n})}^m+n(n-1)\cdot {(1-\frac{2}{n})}^m-n^2\cdot {(1-\frac{1}{n})}^{2m}$$

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

Hint: you may use the approximations $(1-x/n{)}^n\sim e^{-x}\cdot (1-x^2/2n)$ and $(1-1/n{)}^{xn}\sim e^{-x}\cdot (1-x/2n)$

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)

Part 1 (10 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}]\le n\cdot {(1-\frac{1}{n})}^m\sim n\cdot {\displaystyle \frac{1}{e^{m/n}}}={\displaystyle \frac{1}{e^c}}.$$

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

Hint: Inclusion-Exclusion.

Part 2 (10 points)

Consider the following variation of the coupon collector’s problem. Each box of cereal contains one of $2n$ different coupons. The coupons are organized into $n$ pairs, so that coupons 1 and 2 are a pair, coupons 3 and 4 are a pair, and so on. Once you obtain one coupon from every pair, you can obtain a prize. Assuming that each coupon in each box is chosen independently and uniformly at random from the $2n$ possibilities, what is the expected number of boxes you must buy before you can claim the prize?

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 - from Jeff Erickson’s book

Suppose we can insert or delete an element into a hash table in $O(1)$ time, and that we can construct a hash table of size $n$ in $Cn$ time, where $C>0$ is some absolute constant. In order to ensure that our hash table is always big enough, without wasting a lot of memory, we will use the following global rebuilding rules:

1. After an insertion, if the table is more than $3/4$ full, we allocate a new table twice as big as our current table, insert everything into the new table, and then free the old table.
2. After a deletion, if the table is less than $1/4$ full, we allocate a new table half as big as our current table, insert everything into the new table, and then free the old table.

Show that, starting from an empty hash table, for any sequence of insertions and deletions, the amortized time per operation is still $O(1)$.

Problem 3 - Probability - from MU’05 chapter 1

1. Consider the set $\{1,\dots ,n\}$. We generate a subset $X$ of this set as follows: a fair coin is flipped independently for each element of the set; if the coin lands heads then the element is added to $X$, and otherwise it is not. Argue that the resulting set $X$ is equally likely to be any one of the $2^n$ possible subsets.

2. Suppose that two sets $X$ and $Y$ are chosen independently and uniformly at random from all the $2^n$ subsets of $\{1,\dots ,n\}$. Determine $Pr[X\subseteq Y]$ and $Pr[X\cup Y=\{1,\dots ,n\}]$.

Hint: use part 1 of the problem.

Problem 4 - 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 5 - 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,\dots ,X_n$ be random variables such that $X_i=X_j$ and $$X_1=\{\begin{array}{l}1,\text{ with probability }1/2\\ 0,\text{ otherwise}\end{array}$$ 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,\dots ,X_n$ be random variables such that $$X_1=\{\begin{array}{l}1,\text{ with probability }1/2\\ 0,\text{ otherwise}\end{array}$$ and for $2\le i\le n$ we have $$X_i=\{\begin{array}{l}{X}_1,\text{ with probability }1/(2i)\\ 1-X_1,\text{ otherwise}\end{array}$$

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

Problem 6 - 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]=\mathrm{\infty }$. What does this imply about your ability to play the matringale strategy in practice?

Problem 7 - 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 8 - 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.

Problem 9 - Reservoir Sampling - from Mu’05 chapter 2

Suppose we have a sequence of items passing by one at a time. We want to maintain a sample of one item with the property that it is uniformly distributed over all the items that we have seen at each step. Moreover, we want to accomplish this without knowing the total number of items in advance or storing all of the items that we see.

1. Consider the following algorithm, which stores just one item in memory at all times. When the first item appears, it is stored in memory. When the $k^{th}$ item appears, it replaces the item in memory with probability $1/k$. Show why this algorithm solves the problem.

Note: the above algorithm is called reservoir sampling.

2. Suppose that we modify the reservoir sampling algorithm from the previous part so that, when the $k^{th}$ item appears, it replaces the item in memory with probability $1/2$. Describe the distribution of the item in memory.

Problem 10 - Exploring Chernoff

In this question, we will think about the following: when are Chernoff bounds actually giving us any non-trivial information?

1. Let $p\in (0,1/10)$ and $X$ be the random variable which takes value $1/p$ with probability $p$, and takes the value $0$ with probability $1-p$. Let $\epsilon =1/2$.

   • what is the expectation of $X$?
   • why can we use Chernoff here, since $X$ as defined is not Poisson Trial? What do we have to do to use Chernoff here?
   • what does Chernoff say about $Pr[|X-\mathbb{E}[X]|\ge \epsilon \cdot \mathbb{E}[X]]$?

2. One may be tempted to think in the example above that the reason why Chernoff didn’t give any non-trivial information was because the expectation is small compared to ${\epsilon }^2$. However, consider the following random variable: $Y=\alpha \cdot X$, where $X$ is the random variable of part 1 and $\alpha$ can be any positive real number.
   Prove that even though the expectation can now be large compared to ${\epsilon }^2$, Chernoff still does not say anything non-trivial.

Hint: for Chernoff we need Poisson trials.

3. What is the minimum number of independent copies $X_i$ of $X$ needed if we want Chernoff to say anything meaningful for $Pr[|Z-\mathbb{E}[Z]|\ge \epsilon \cdot \mathbb{E}[Z]]$, where $Z=\sum _{i=1}^t{X}_i$?