CAS 779 / String Processing Algorithms

3 unit(s)

Prerequisite(s): Good understanding of the undergraduate material in discrete mathematics, algorithms & data structures, and complexity theory. Programming knowledge in Python, C, and C++ is preferred.

The ever increasing use of data and the need to process it to extract meaningful information has made the development of efficient algorithms for string processing all the more relevant. This course will cover string processing algorithms for exact and approximate pattern matching, for computing string regularities, and for string indexing, sorting and compression. Different string generalizations such as partial words and indeterminate/degenerate strings will be covered. String data structures such as suffix trees, suffix arrays and Burrows-Wheeler transform will also be studied. Applications to research areas such as bioinformatics and data analysis will be highlighted.