Week 1 Check-in Quiz
Please complete the following quiz by the beginning of class Tues. 9/14/2020. You can resubmit as many times as you like. I will grade the most recent submission.
Email *
First and Last Name
NetID
Which of the following properties hold for all pairs of random variables X,Y? Check any that apply.
2 points
Which of the following properties hold for all pairs of *independent* random variables X,Y? Check any that apply.
2 points
A uniformly random hash function h is:
1 point
Statement: Given two random events A and B, if P(A|B) = P(A) then P(B|A) = P(B). Say whether this statement is Always, Sometimes, or Never true and justify your choice in a sentence.
1 point
Suppose we use the Count-Min algorithm to solve the (epsilon,k)-Frequent items problem. If we want to increase the accuracy with which we solve the problem by a factor a 2 (e.g. with epsilon/2 instead of epsilon accuracy) how does the space requirement of the algorithm change?
1 point
Consider the CAPTCHA problem from class, where we draw m items x_1, ..., x_m uniformly at random from a set of size n. Let a "three-way collision" be any subset of three elements (i,j,k) from 1,...,m with i < j < k such that x_i = x_j = x_k. Write down an expression for the expected number of three-way collisions after drawing m items.
2 points
A copy of your responses will be emailed to the address you provided.