Course code  CTU03  
Course title  Text Searching Algorithms  
Institution  Czech Technical University in Prague  
Course address  Thákurova 7  
City  Prague 6  
Minimum year of study  3rd year  
Minimum level of English  Good  
Minimum level of French  None  
Key words  Stringology, finite automata, exact and approximate string matching, forward and backward string matching, factor automata, subsequence automata 

Language  English  
Professor responsible  Ondrej Guth  
Telephone  +420 224 359 867  
Fax  
ondrej.guth@fit.cvut.cz  
Participating professors  Borivoj Melichar 

Number of places  Minimum: 10, Maximum: 20, Reserved for local students: 0  
Objectives 


Programme to be followed  · Five 3hour lectures: 1. Overview of Stringology, string matching problems, string matching and finite automata.2. Forward string matching, dynamic programming and bit parallelism.3. Factor automata, subsequence automata, repetition in text.4. Forward string matching, fail function.5. Backward string matching, models of backward string matching, BoyerMoore algorithm. · Four 2hour seminars: 1. Mastering finite automata: determinisation, union, intersection, etransitions removal, elimination of more than one initial states.2. Construction of string matching automata, their determinisation and simulation. 3. Application of factor automata. 4. Backward string matching.  
Prerequisites  Sets, relations, oriented graphs, finite automata, regular expressions.  
Course exam  Written exam with the duration of 1 hour, evaluation of the results. 