Suggested Final Project Topics

Why they're worth studying:  Suffix automata, like suffix trees, have a number of applications in text

processing and computational biology. In many ways, they're simpler than suffix trees (the representation

doesn't require any crazy pointer compress tricks, for example). If you liked suffix trees and want to see

what they led into, this would be a great place to start.

The Burrows-Wheeler Transform

The Burrows-Wheeler transform is a transformation on a string that, in many cases, makes the string

more compressible. It's closely related to suffix arrays, and many years after its invention was repurposed

for use in string processing and searching applications. It now forms the basis for algorithms both in text

compression and sequence analysis.