Suggested Final Project Topics

Why they’re worth studying: Throughout the quarter, you’ve seen that some data structures are fast in

Theoryland, some are fast IRL, and some are (coincidentally) fast in both. The Stree represents one way

of starting with a jewel of Theoryland and turning it into something workable. If you’re interested in tin-

kering and tweaking an existing structure to see if you can improve upon it – or generalize it to work for

64-bit machines – this would be a great starting point.

Radix Heaps

Fibonacci heaps are of great theoretical interest because they give O(m + n log n)-time implementations

of both Dijkstra’s algorithm and Prim’s algorithm. Now, suppose that you’d like to use one of those algo-

rithms and it happens to be the case that every edge in the graph has integral weight, and that weight is at

most some number C. Could you take advantage of integer operations to speed things up? The answer is

yes, and one of the first major steps toward doing so was the radix heap, which improves upon Dijkstra’s

algorithm for sparse graphs in this case.