Suggested Final Project Topics

Why they’re worth studying: Practically speaking, sequence heaps are among the fastest priority queues

in practice across a number of different workflows. Theoretical speaking, sequence heaps are based on a

number of clever techniques for combining data streams together while playing well with caches. If you

enjoyed our discussion of B-trees and the idea of optimizing for cache transfers rather than instruction

counts, this would be a great data structure to investigate.

---

 9 / 22

Iacono’s Working Set Structure

Splay trees have the wonderful property that recently-accessed elements are much faster to look up than

infrequently-accessed elements. John Iacono developed a data structure that also has this property (called

the working set property) but which guarantees fast accesses in a worst-case rather than amortized-effi-

cient sense. The strategy employed – using an ensemble of smaller data structures in concert with one an-

other – is quite beautiful.