Suggested Final Project Topics

Why it’s worth studying: FM-indices interface with a number of other beautiful concepts from string

data structures (Burrows-Wheeler transform) and succinct data structures (wavelet trees). Exploring this

space will give you a real sense for what data structure design looks like when the goal is minimizing

memory usage, in both a practical (“it needs to fit in RAM”) and theoretical (can we do better than

Θ(m)?) sense.

---

 6 / 22

If You Liked Balanced Trees, Check Out...

Finger Trees

A finger tree is a B-tree augmented with a “finger” that points to some element. The tree is then reshaped

by pulling the finger up to the root and letting the rest of the tree hang down from the finger. These trees

have some remarkable properties. For example, when used in a purely functional setting, they give an ex-

cellent implementation of a double-ended queue with amortized efficient insertion and deletion.