Suggested Final Project Topics

Why they're worth studying: Using ropes in place of strings can lead to performance gains in many set-

tings, and some programming languages use them as a default implementation of their string type. If

you're interested in seeing creative applications of balanced trees, this would be a great place to start.

A Caveat: Ropes are not as complicated as the other data structures on this list and many of the papers

about ropes have incorrect runtime bounds. If you choose to use this data structure, we'll expect that

you'll put in a significant amount of work comparing them to other approaches or developing novel ideas.

---

 8 / 22

Succinct Trees

What is the the information-theoretic minimum number of bits necessary to represent a balanced tree in a

way that lets you still perform queries with the regular time bounds? The standard representation of a bi-

nary search tree with  n  nodes, for example, uses Θ(n  log  n) bits just for the tree structure, since each

pointer requires a machine word to store. Amazingly, it’s possible to compress the tree representation

down to 2n + o(n) bits without sacrificing the runtime of performing standard operations on these trees.