β’ 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
