I love reservoir sampling. When I first heard about the algorithm I had been preparing a lab session for a course I was a TA on. (I had a lot of freedom to create labs in this course -- a good and bad thing!) I made dinner in a bit of a daze while I proved in my head that reservoir sampling worked. It's a simple inductive proof, which is a good thing because if it was more complicated I might not have been able to do it without paper, and I might not have eaten that night.

I've since learned there are many other interesting sampling algorithms that apply in a streaming setting. A few are give here: http://people.cs.umass.edu/~mcgregor/slides/10-jhu1.pdf