Streaming algorithms suitable for undergrad course I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course.

Good choices should probably satisfy the following requirements:


Solve a problem that is useful in practice or easy to motivate, or alternatively, illustrate techniques that are beautiful or useful.
Be suitable for presentation in an undergraduate algorithms course.  This means the algorithm and analysis can't be too complex.  Also they shouldn't require too much heavy probability theory to analyze (sadly, this rules out many beautiful algorithms).


What would be a good candidate?

One beautiful algorithm is the deterministic algorithm to find an element that occurs with frequency at least 50% (if any such element exists), using $O(1)$ space; or its generalization, find all items that occur with frequency at least $1/k$, using $O(k)$ space.  Are there any others that would be an excellent choice for an undergraduate course?
In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following:


Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space.
Approximate bit counting on a sliding window - given a bit-stream, answer queries approximating the number of $1$'s in the last $N$ bits, and do so using $O(\log N)$ space.
Sampling from a sliding window (at any point, give a sample of $k$ elements uniformly chosen from the last $N$ elements of a stream).
Exact item counting - answer queries of the form "how many times did $x$ appear in the stream" such that the answer will be correct w.h.p. using only sublinear space (modern data structures are quite complex, but Count–min sketch seems to fit undergrad course).