Text Algorithms

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)

• linear space algorithm for finding LCS

• a survey chapter by Dan Hirschberg on LCS and edit distance

• Ukkonen's algorithm

• suffix array construction in linear time, see also: preliminary version, lecture notes by ?

• LCA and RMQ problems

• Approximation algorithms for Shortest Common Supersting, see also: M. Mucha' tutorial, chapter 7 of Vazirani's Approximation Algorithms

• Algorithms on Strings on Coursera

• 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:

• informal ranking

• 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)