Description
1 Random Cuckoo Hashing
Cuckoo birds are parasitic beasts. They are known for hijacking the nests of other bird species and
evicting the eggs already inside. Cuckoo hashing is inspired by this behavior. In cuckoo hashing,
when we get a collision, the element that was already there gets evicted and rehashed.
We study a simple (but ineffective, as we’ll see) version of cuckoo hashing, where all hashes are
random. Let’s say we want to hash n pieces of data D1,D2,…,Dn into n possible hash buckets
labeled 1,…,n. We hash the D1,…,Dn in that order. When hashing Di
, we assign it a random
bucket chosen uniformly from 1,…,n. If there is no collision, then we place Di
into that bucket. If
there is a collision with some other Dj
, we evict Dj and assign it another random bucket uniformly
from 1,…,n. (It is possible that Dj gets assigned back to the bucket it was just evicted from!) We
again perform the eviction step if we get another collision. We keep doing this until there is no
more collision, and we then introduce the next piece of data, Di+1 to the hash table.
(a) What is the probability that there are no collisions over the entire process of hashing D1,…,Dn
to buckets 1,…,n? What value does the probability tend towards as n grows very large?
(b) Assume we have already hashed D1,…,Dn−1, and they each occupy their own bucket. We
now introduce Dn into our hash table. What is the expected number of collisions that we’ll
see while hashing Dn? (Hint: What happens when we hash Dn and get a collision, so we evict
some other Di and have to hash Di? Are we at a situation that we’ve seen before?)
CS 70, Fall 2018, HW 11 1
2 Markov’s Inequality and Chebyshev’s Inequality
A random variable X has variance var(X) = 9 and expectation E[X] = 2. Furthermore, the value
of X is never greater than 10. Given this information, provide either a proof or a counterexample
for the following statements.
(a) E
X
2
= 13.
(b) P[X ≤ 1] ≤ 8/9.
(c) P[X ≥ 6] ≤ 9/16.
(d) P[X ≥ 6] ≤ 9/32.
3 Easy A’s
A friend tells you about a course called “Laziness in Modern Society” that requires almost no work.
You hope to take this course next semester to give yourself a well-deserved break after working
hard in CS 70. At the first lecture, the professor announces that grades will depend only on two
homework assignments. Homework 1 will consist of three questions, each worth 10 points, and
Homework 2 will consist of four questions, also each worth 10 points. He will give an A to any
student who gets at least 60 of the possible 70 points.
However, speaking with the professor in office hours you hear some very disturbing news. He tells
you that, in the spirit of the class, the GSIs are very lazy, and to save time the grading will be
done as follows. For each student’s Homework 1, the GSIs will choose an integer randomly from
a distribution with mean µ = 5 and variance σ
2 = 1. They’ll mark each of the three questions
with that score. To grade Homework 2, they’ll again choose a random number from the same
distribution, independently of the first number, and will mark all four questions with that score.
If you take the class, what will the mean and variance of your total class score be? Use Chebyshev’s
inequality to conclude that you have less than a 5% chance of getting an A when the grades are
randomly chosen this way.
4 Confidence Interval Introduction
We observe a random variable X which has mean µ and standard deviation σ ∈ (0,∞). Assume
that the mean µ is unknown, but σ is known.
We would like to give a 95% confidence interval for the unknown mean µ. In other words, we
want to give a random interval (a,b) (it is random because it depends on the random observation
X) such that the probability that µ lies in (a,b) is at least 95%.
We will use a confidence interval of the form (X − ε,X + ε), where ε > 0 is the width of the
confidence interval. When ε is smaller, it means that the confidence interval is narrower, i.e., we
are giving a more precise estimate of µ.
CS 70, Fall 2018, HW 11 2
(a) Using Chebyshev’s Inequality, calculate an upper bound on P{|X − µ| ≥ ε}.
(b) Explain why P{|X − µ| < ε} is the same as P{µ ∈ (X −ε,X +ε)}.
(c) Using the previous two parts, choose the width of the confidence interval ε to be large enough
so that P{µ ∈ (X −ε,X +ε)} is guaranteed to exceed 95%.
[Note: Your confidence interval is allowed to depend on X, which is observed, and σ, which
is known. Your confidence interval is not allowed to depend on µ, which is unknown.]
(d) The previous three parts dealt with the case when you observe one sample X. Now, let n be a
positive integer and let X1,…,Xn be i.i.d. samples, each with mean µ and standard deviation
σ ∈ (0,∞). As before, assume that µ is unknown but σ is known.
Here, a good estimator for µ is the sample mean X¯ := n
−1 ∑
n
i=1 Xi
. Calculate the mean and
variance of X¯.
(e) We will now use a confidence interval of the form (X¯ −ε,X¯ +ε) where ε > 0 again represents
the width of the confidence interval. Imitate the steps of (a) through (c) to choose the width ε
to be large enough so that P{µ ∈ (X¯ −ε,X¯ +ε)} is guaranteed to exceed 95%.
To check your answer, your confidence interval should be smaller when n is larger. Intuitively,
if you collect more samples, then you should be able to give a more precise estimate of µ.
CS 70, Fall 2018, HW 11 3
