Suggested Final Project Topics

Why it’s worth studying: Induced sorting is a very clever technique that touches on all sorts of nuances

of the structure of a string’s suffixes. If you’re interested in exploring more of the hidden structure of

strings and substrings, this would be a great way to do so while further solidifying your understanding of

the SA-IS algorithm.

Ukkonen's Algorithm

Prior to the development of SA-IS as a way of building suffix arrays, the most popular algorithm for

building suffix trees was Ukkonen's algorithm, which combines a number of optimizations on top of a rel-

atively straightforward tree-building procedure to build suffix trees in time O(m). Amazingly, the algo-

rithm works in a streaming setting – it can build suffix trees incrementally as the characters become avail-

able!