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.
Sign in to Google to save your progress. Learn more
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
Clear selection
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
Clear selection
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.
Submit
Clear form
Never submit passwords through Google Forms.
reCAPTCHA
This form was created inside of New York University. Report Abuse