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?