Suggested Final Project Topics

Why they’re worth studying: Purely functional red/black trees are a good first taste of what data struc-

tures look like in a purely functional setting. If you’re interested in seeing what data structures might have

evolved into if we thought about programming differently, or if you’re a fan of functional languages and

want to get a chance to experiment with data structure design in that space, this might be a great place to

look for inspiration!

Sequence Heaps

In one sense, you can think of the binomial or Fibonacci heap as a data structure specifically optimized to

get good results in Theoryland. What happens if you take the other approach and design a priority queue

where all that matters is wall-clock runtime? With a good deal of engineering effort, you might end up

with the sequence heap, a priority queue that’s specifically designed to play nicely with caches. Amaz-

ingly, this data structure can outperform a regular binary heap, even though binary heaps are already

packed densely into arrays.