Suggested Final Project Topics

Why they’re worth studying: Along with queaps and fishspears (described later), the working set struc-

ture is designed to provide good performance not just in the worst case, but in the sorts of cases that tend

to come up in practice. We honestly don’t know how fast this structure is in practice – does it compare fa-

vorably against a regular balanced BST or a splay tree? – and diving into that question would be a great

way to gauge how well the mathematical theory matches practice.

Rotation Distance

Tree rotations are a fundamental primitive on binary search trees, and in fact, any two binary search trees

with the same set of keys can be transformed into one another using tree rotations. That then sparks a

question: what’s the maximum number of rotations needed to turn one BST into another? By reframing

binary search trees as triangulations of convex polygons and mapping everything into hyperbolic space,

it’s possible to get both an upper and lower bound to this question.