Text Algorithms (Fall 2016)
Textbooks:
Pattern Matching Algorithms, edited by Alberto Apostolico and Zvi Galil
Text algorithms and/or Jewels of Stringology, by Maxime Crochemore and Wojciech Rytter
Algorithms on strings, by Maxime Crochemore, Christophe Hancart, and Thierry Lecroq
Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, by Dan Gusfield
Text algorithms are available at the author's homepages: Maxime Crochemore's and Wojciech Rytter's. (The former also contains Algorithms on strings in French.)
Other Materials:
Exact String Matching Algorithms (descriptions and examples)
suffix array construction in linear time, see also: preliminary version, lecture notes by ?
Approximation algorithms for Shortest Common Supersting, see also: M. Mucha' tutorial, chapter 7 of Vazirani's Approximation Algorithms
An Alphabet Independent Approach to Two Dimensional Matching (slight differences between the versions): 1.ps, 2.pdf, 3.pdf; see also the chapter in Rytter and Crochemore or the following survey chapter by Amihood Amir
Real-Time Streaming String-Matching (conference version, identical to journal version, available for download)
Fully Compressed Pattern Matching; see also either of these for connections between LZ-encoding and grammar compression: survey, article
Indexing Compressed Text: see article, survey entry, or Pizza and Chili bibliography
Classes:
problem sets (see the bottom of the page) latest revision(s): problem set 7 added, hint and corrections on previous sets
Exam:
takes place on the 4th of February (Saturday) in room 25 (Great Eastern Lecture Hall), starts at 10:15am and lasts 3-4 hours
there will be 3 problems to solve (at least one hour per problem)