Suggested Final Project Topics

Why they're worth studying: As you saw from lecture, cuckoo hashing is a simple idea with a surpris-

ingly complex analysis. Many of the updates to cuckoo hashing are known to work well in practice, but

have been tricky to analyze in a mathematically rigorous fashion. If you're looking for a project where

you'll get some exposure to really cool mathematical techniques while also getting the chance to try out

the techniques in practice, this might be a great place to begin.

The AMS Sketch

The AMS sketch (named after its inventors Alon, Matias, and Szegedy) was one of the first modern

streaming data structures and set the stage for much future development on the subject. The paper was on

the complexity of estimating the frequency norms F

p

 of a data stream, which generalizes the L₁ and L₂

norms we explored in the context of the count and count-min sketches.