• No extension will be provided, unless for serious documented reasons.
• Start early!
• Study the material taught in class, and feel free to do so in small groups, but the solutions should be a product of your own work.
• This is not a multiple choice homework; reasoning, and mathematical proofs are required before giving your final answer.
1 Reservoir Sampling [15 points]
Design an algorithm that samples k ≥ 1 elements uniformly at random from an insert-only stream, whose length is unknown. Present the pseudocode and prove the correctness of the proposed algorithm.
2 Median trick - a useful technique [15 points]
Prove the claim on slide 13. Be specific about the values of the constants C1,C2 you use in your proof, where .
3 Variance of Morris Counter [20 points] Prove equation Var( on slide 47.
4 More on uniform RVs [10+10 points]
Let X1,...,Xn be iid uniform random variables, Xi ∈ U(0,1) for all i. (a) What is the pdf and (b) what is the expectation of the k-th smallest value among X1,...,Xn for k = 1,...,n?
5 Coding [40 points]
Check the Jupyter notebook on our Git repo.
1 of 1
