Two Interesting Randomized Algorithms (2)

Continuing…

Reservoir Sampling

Why it Seems Impossible

A Small Example

The Algorithm

And… Induction