Suggested Final Project Topics

Why they're worth studying: Pathfinding is as important as ever, and the sizes of the data sets keeps in-

creasing. Approximate distance oracles are one possible approach to try to build scalable pathfinding algo-

rithms, though others exist as well. By exploring approximate distance oracles, you'll get a better feel for

what the state of the art looks like.

---

 15 / 22

FKS Hashing

The cuckoo hashing strategy we described in class is one way of making a dynamic perfect hash table. As

beautiful a technique as it is, it doesn’t have the best utilization of memory, and it seems to require strong

hash functions. Another technique for perfect hashing, the FKS hash table, uses weaker hash functions and

is based on a surprising idea: what if we resolved hash collisions by using another hash table?