Suggested Final Project Topics

Why it’s worth studying: Exploring what we know about the deque conjecture is a great way to learn

about the techniques people have explored in the quest for dynamic optimality. This would be a great

launching point to learn more about, say, how we lower-bound the costs of sequences of operations on

any possible binary search tree. And as a real kicker, the best upper bound we have right now is the mind-

bogglingly-slowly-growing O(α] trees*(n)). To understand what you’re looking at, α] trees(n) is the  Ackermann in-

verse function, which grows so slowly that we need special notation to write out a value of n for which

α] trees(n) = 6. The function α] trees*(n) is the iterated Ackermann inverse function – the number of times we need to

apply α] trees to a value before it drops to a constant. This might be the slowest-growing function ever used in a

serious proof in computer science!

---

 14 / 22