Description:

Students get knowledge of efficient algorithms for text pattern matching. They learn to use so called succinct data structures that are efficient in both access time and memory complexity. They will be able to use the knowledge in design of applications that utilize pattern matching.

Contents:

1. Introduction, basic definitions, border array.
2. Text full index: Suffix array.
3. Text full index: Suffix tree, LCP construction.
4. Text full index: Factor, suffix automata, on-line construction.
5. Exact pattern matching algorithms.
6. FFT in pattern matching.
7. Succinct data structure: rank & select.
8. Succinct data structure: wavelet tree.
9. FM-Index.
10. Dictionary representation, spell checking.
11. Approximate pattern matching.
12. (2) Pattern matching in bioinformatics.

Seminar contents:

1. Basic definitions.
2. Text full index
3. Exact pattern matching algorithms.
4. FFT in pattern matching.
5. Succinct data structure
6. FM-Index, approximate pattern matching.

Recommended literature:

1. Smyth, W. F. : Computing Patterns in Strings. Addison Wesley, 2003. ISBN 0201398397.
2. Crochemore, M. - Rytter, W. : Jewels of Stringology. World Scientific Publishing Company, 2003. ISBN 9810248970.
3. Navarro, G. - Raffinot, M. : Flexible Pattern Matching in Strings. Cambridge University Press, 2008. ISBN 0521039932.
4. Crochemore, M. - Hancart, C. - Lecroq, T. : Algorithms on Strings. Cambridge University Press, 2007. ISBN 0521848997.

Keywords:

pattern matching, fulltext index, succinct data structure

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar