Suggested Final Project Topics

Why it's worth studying: If you had a dynamically optimal BST, how would you know? Lower-bound-

ing techniques like the one developed here are one of the best tools we've got for reasoning about the lim-

its of BSTs. If you're interested in seeing how these techniques are developed and would be up for a bit of

a history lesson, this might be a great place to start.

Crazy Good Chocolate Pop Tarts

In their paper “De-Amortizing Binary Search Trees,” Bose et al. provide a data structure transformation

that takes any amortized-efficient binary search tree and converts it into a new BST data structure that

maintains all of the existing amortized time bounds and guarantees worst-case O(log n) runtimes for each

operation. Their technique is based on a data structure called the chocolate pop tart, which they prove is

“crazy good” for an appropriate definition of “crazy good.” Impressively, this means that there’s a trans-

formation on splay trees that preserves all their amortized-efficient properties, yet guarantees that each op-

eration is asymptotically no slower than a perfectly-balanced tree.