Suggested Final Project Topics

Why it’s worth studying:  If you thought that suffix trees were a fun topic in and of themselves, this

would be a great way to continue that exploration and to see how topics typically associated with data

structures can be applied to machine learning and linear algebra.

Suffix Automata

You can think of a trie as a sort of finite automaton that just happens to have the shape of a tree. A suffix

trie is therefore an automaton for all the suffixes of a string. But what happens if you remove the restric-

tion that the automaton have a tree shape? In that case, you'd end up with a suffix automaton (sometimes

called a directed acyclic word graph or DAWG), a small automaton recognizing all and only the suffixes of

a given string. Impressively, this automaton will always have linear size!