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
* Required
Email
*
Your email
First and Last Name
Your answer
NetID
Your answer
Which of the following properties hold for all pairs of random variables X,Y? Check any that apply.
2 points
E[a*X - b*Y] = a*E[X] - b*E[Y] for constants a,b.
E[X]E[Y] = E[XY]
Var[a*X + b*Y] = a^2*Var[X] + b^2*Var[Y] for constants a,b.
Pr[X > a] <= E[X]/a for constant a.
Which of the following properties hold for all pairs of *independent* random variables X,Y? Check any that apply.
2 points
E[a*X - b*Y] = a*E[X] - b*E[Y] for constants a,b.
E[X]E[Y] = E[XY]
Var[a*X + b*Y] = a^2*Var[X] + b^2*Var[Y] for constants a,b.
Pr[X > a] <= E[X]/a for constant a.
A uniformly random hash function h is:
1 point
Universal.
Pairwise independent.
Both of the above.
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
Your answer
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
Decrease by a factor of 2.
Increase by a factor of 2.
Decrease by a factor of 4.
Increase by a factor of 4.
Stays the same.
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
Your answer
A copy of your responses will be emailed to the address you provided.
Submit
Clear form
Never submit passwords through Google Forms.
reCAPTCHA
Privacy
Terms
This form was created inside of New York University.
Report Abuse
Forms