Suggested Final Project Topics

Why they're worth studying: The techniques used in the AMS sketch combines techniques from a num-

ber of different fields of mathematics: random matrix projections, streaming algorithms, and information

theory, to name a few. Additionally,  F

p

-norm sketches are one of the few cases where we have strong

lower bounds on the time and space complexity of any data structure. If you'd like to see some fun math

that leads to proofs of correctness and optimality, this might be a great place to start.

---

 16 / 22

Hopscotch Hashing

Hopscotch hashing is a variation on open addressing that's designed to work well in concurrent environ-

ments. It associates each entry in the table with a “neighborhood” and uses clever bit-masking techniques

to quickly determine which elements in the neighborhood might be appropriate insertion points.