Suggested Final Project Topics

Why they’re worth studying: Succinct trees exist at the interplay between information theory (why can’t

you encode trees is less than 2n + o(n) bits?), data structure isometries (representing trees as cleverly-cho-

sen bitvectors), and properties of trees (exploiting some hidden structure that was there all along). On top

of this, these techniques can be used in practice to build highly compact suffix trees and suffix arrays,

making it possible to push forward our understanding of computational biology with limited hardware.