Suggested Final Project Topics

Why it's worth studying:  The Burrows-Wheeler transform and its variations show up in a surprising

number of contexts. If you'd like to study a data structure that arises in a variety of disparate contexts,

this would be an excellent choice.

---

 5 / 22

LCP Induction

The SA-IS algorithm we explored in class can be modified to also produce LCP information for the suffix

array, and to do much faster than traditional LCP construction algorithms. As you’ve seen, LCP informa-

tion is extremely useful for all sorts of suffix array operations, so the practical speedup here is a big deal!