Week 1 Check-in Quiz

JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

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

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

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

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