CS 170 Reading Quiz -- Week 14, Tuesday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.


Name:

SID: [No spaces and no dashes.]

Login ID : [e.g., cs170-xy]


1. One required property of an universal hash family is that for any distinct objects x,y, P(h(x) = h(y)) = 1/m. What happens if this requirement was not present?

Give an example of a family of functions H such that for any object x and any bucket i, applying a random function h from H meets the condition that P(h(x) = i) = 1/m, _but_ applying a random function h from H to two distinct objects x,y will always result in a collision.

Hint: there should be m functions...


2. If we are planning on storing n objects, approximately how many buckets should a Bloom filter have if we are fine with a false positive rate of 10%? What if we insist on a false positive rate of 0.01%? Give a short justification.


3. What did you find difficult or confusing about the reading for the upcoming lecture, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.


4. What questions do you still have about previous material? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

5. What feedback do you have on quizzes? Were the questions too difficult/easy? Did they affect how you studied, or help your learning?


CS 170 home page