Suggested Final Project Topics

Why it's worth studying: On a practical note, we think that learning more about how to build hash func-

tions will give you a much better appreciation for the power of randomized data structures. On a theoreti-

cal note, the math behind tabulation hashing and why it’s so effective is beautiful (but tricky!) and would

be a great place to dive deeper into the types of analyses we’ve done this quarter.

Approximate Distance Oracles

Computing the shortest paths between all pairs of nodes in a graph can be done in time O(n

3

) using the

Floyd-Warshall algorithm. What if you want to get the distances between many pairs of nodes, but not all

of them? If you're willing to settle for an approximate answer, you can use subcubic preprocessing time to

estimate distances in time O(1).