The class will cover advanced topics in sequence analysis: formal languages and grammars, finite automata, algorithms on words, string index structures.
Date | Topic | Exercises |
05.04.2019 | Introduction, logistics (F) | – |
12.04.2019 | Basic algorithms on strings, trees and sequences (J) | Exercises 1 |
19.04.2019 | – Good Friday – | – |
26.04.2019 | Trie, DAWG, Automata (M) | Exercises 2 |
03.05.2019 | Automata: determinisation, minimization (M) | Exercises 3 |
10.05.2019 | Pattern matching (J) | Exercises 4 |
17.05.2019 | Linear-time construction of suffix trees (J) | Exercises 5 |
24.05.2019 | Context-free languages (F) | Exercises 6 |
31.05.2019 | Pushdown automata (F) | Exercises 7 |
07.06.2019 | Turing-Church thesis (F) | Exercises 8 |
14.06.2019 | Decidability (F) | Exercises 9 |
21.06.2019 | Linear-time construction of suffix trees (cont'd), BWT (J) | Exercises 10 |
28.06.2019 | Periodic structures in words 1 (M) | Exercises 11 |
05.07.2019 | Periodic structures in words 2 (M) | – |
12.07.2019 | Oral exam (M,J) | – |
Oral exams will be on 12.07.2019. Please make an appointment with the secretary in U10-151, Heike Samuel.
A second oral exam can be taken on September 20, 2019. Please contact Heike Samuel if you are interested.
Back to Teaching