CS161-Homework 4 Solved

1.   Suppose that h : U → {0,...,n−1} is a uniformly random function. That is, h(i) is distributed uniformly at random in the set {0,...,n − 1} for all i, and h(i) are independent for all i. Prove that for any x 6= y ∈ U,

 .

[We are expecting: A short but rigorous proof.]

2.   This exercise references the IPython notebook HW4.ipynb as well as the files mysteryA.pickle and mysteryB.pickle.

In the IPython notebook, run the cells to load the hash families A and B. Both A and B are lists of functions h : {0,...,21} → {0,1,2}. As shown in the notebook, at first glance both of these seem like reasonable hash families. However, one of them is a universal hash family and one of them is not. Which one is which? Play around with both hash families in Python until you figure it out.

[We are expecting: Your answer, along with compelling numerical evidence (either numbers or a plot), and an explanation about why your numerical evidence is compelling and what it has to do with the definition of a universal hash family.]

 

 

1.   Your friend has a proposal for a new universal hash function h : U → {0,...,n − 1}, where U = {0,...,n2−1}. Your friend thinks that you can skip this whole “choose uniformly from a universal hash family” stuff, and just go with

h(x) = x mod n.

More precisely, your friend says, just take the hash family H = {h} to be the set with just this one function in it.

(a) Your friend doesn’t have a very good track record on these homework sets, so you are dubious even before you hear their argument. Prove to your friend that their choice does not satisfy the key property of a universal hash family.

(b) Even given your proof, your friend plows on. Their first point:

Let h = x mod n be as above. If we choose x 6= y uniformly at random[1] from U, then  , where the probability is over the random choice of x and y.

Do you agree?

[

(c) Your friend continues:

Given the computation above, we have

 .

This is the definition of a universal hash family, so {h} must be a universal hash family.

Do you agree?

 

2.   Let T be a Red-Black tree with root x. Let TL be the subtree rooted at x’s left child, and let TR be the subtree rooted at x’s right child.

 

Decide if each of the following statements are true or false. If it is true, give a proof. If it is false, give a counter-example.

(a)    In the set-up above, we must have

                                                                       1         and          ,                       (1)

where |T| denotes the number of nodes in T (including the root, not including NIL nodes).

(b)   In the set-up above, we must have

                                                                  1         and          ,                  (2)

where |T| denotes the number of nodes in T (including the root, not including NIL nodes).

3.   A large flock of T Colorful Geese will migrate south for the winter over the Gates building in the next few weeks. Colorful Geese are an interesting species. They can come in a huge number of colors—say, M colors—but each flock only has m colors represented, where m < T. You’d like to be able to answer queries about what colors of geese appeared in the flock. The birds will fly overhead one at a time, and after they have flown by they won’t come back again.

For example, if T = 7, M = 100000 and m = 3, then a flock of T colorful geese might look like:

 

seabreeze, seabreeze, brick red, ultraviolet, brick red, ultraviolet, seabreeze

You’ll see this sequence in order, and only once. After the birds have gone, you’ll be asked questions like “How many brick red geese were there?” (Answer: 2), or “How many neon orange geese were there?” (Answer: 0).

You have access to a universal hash family H, so that each function h ∈ H maps the set of M colors into the set {0,...,n − 1}. For example, one function h ∈ H might have h(seabreeze) = 3.

(a)    Suppose that n = 10m, and you only have space to store n numbers in the set {0,...,T}, as well as one function h from H. Use the universal hash family H to create a randomized data structure that fits in this space and that supports the following operations:

•    Update(color): Update the data structure when you see a goose with color color.

•    Query(color): Return the number of geese of color color that you have seen so far. For each query, your query should be correct with probability at least 9/10. That is, for all colors i,

P{Query(i) = the number of geese with color .

You want each of these operations to be done in O(1) time (in the worst case), assuming that you can evaluate a function h ∈ H in O(1) time.

(b)   Suppose that you now have ten times the space you had in part (a). Adapt your data structure from part (a) so that the Query operation is correct with probability 1  .


 
[1] That is, choose x uniformly at random from U and then choose y uniformly at random from U\{x}