User Tools

Site Tools


Advanced Sequence Analysis

392119/20 Braga, Martinez, Stoye Summer 2019 Fr 9:00-10:30 and 10:30-12:00 in U10-146


The class will cover advanced topics in sequence analysis: formal languages and grammars, finite automata, algorithms on words, string index structures.


  • J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
  • H. R. Lewis, C. H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1997.
  • M. Lothaire: Applied Combinatorics on Words. Cambridge University Press, 2005.

Time table

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 I (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 II (J)
28.06.2019 TBA (M)
05.07.2019 TBA (M)
12.07.2019 Oral exam (M,F,J)

Examination dates

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

teaching/2019summer/asa.txt · Last modified: 2019/06/19 13:12 by Jens Stoye