Suggested Final Project Topics

The Deque Conjecture

Suppose that – for some reason – you decide to implement a deque using a splay tree. That is, you’ll sup -

port the insertion and deletion of elements at the front or back of a sequence, using a splay tree as the un-

derlying mechanism for storing elements. (This isn’t as crazy an idea as it might initially seem; the finger

tree data structure does precisely this and gets a lot of love in the functional programming community.)

How fast would the deque be? The conjecture is that operations should run in amortized O(1) each. We

haven’t yet proved this, but we’re getting closer!