Week 2 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 end of the day on Wed. 9/23/2020.

Email *

First and Last Name

NetID

Which of these functions can be implemented exactly using a constant space streaming algorithm run on the data set X = x1, ..., xn, where each xi is a scalar value. Check all that apply.

2 points

The Euclidean norm ||X||_2

max(X)

mean(X)

median(X)

Suppose we use the hashing based FM estimator for distinct elements discussed in class. According to the proven bound, how much would our space complexity need to increase if wanted to improve our failure probability from 1/10 to 1/100?

1 point

Which of the following are examples of exponential concentration inequalities/tail bounds? Check all that apply.

1 point

Chernoff Bound

Laplace Bound

Bernstein Bound

The central limit theorem.

Hoeffding bound.

Suppose we use MinHash to estimate the Jaccard similarity between two binary vectors. To improve our accuracy from epsilon =.1 to epsilon=.01, how much larger of a sketch would we need to use?

1 point

You might expect to apply an exponential tail bound when you wish to bound:

1 point

The average of many random variables.

The maximum of many random variables.

The product of many random variable.

None of the above.

Clear selection

If X, Y, and Z are pairwise independent random variables then X, Y, and Z are mutual independent.

1 point

Always

Sometimes

Never

Clear selection

If we throw n balls randomly into n bins, then for some constant c, with high probability the bin with the most balls contains at most:

1 point

c*n balls

c*sqrt(n) balls

c*log(n) balls

c balls

Clear selection

Submit

Clear form

Never submit passwords through Google Forms.

This form was created inside of New York University. Report Abuse

Forms