Suggested Final Project Topics

Why it's worth studying:  The algorithms involved in building Levenshtein automata are closely con-

nected to techniques for minimizing acyclic finite-state automata. If you're interested in seeing the inter-

play between CS154-style theory techniques and CS166-style string processing, this might be an interest-

ing place to start!

FM-Indices

Suffix arrays were initially introduced as a space-efficient alternative to the memory-hogging suffix trees.

But in some cases, even the suffix array might be too costly to use. The FM-index (officially, “Full-text in-

dex in Minute space,” but probably more accurately named after the authors Ferragina and Manzini) is re-

lated to suffix arrays, but can often be packed into sublinear space. If you were a fan of the stringology

bits that we covered when exploring suffix trees and suffix arrays (shared properties of overlapping suf-

fixes, properties of branching words, connections between substrings and suffixes, etc.), then this would be

a great way to dive deeper into that space.