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 Suffix tries, suffix trees (M/J)
03.05.2019 Suffix automata (M)
10.05.2019 Use of suffix trees and automata (M)
17.05.2019 Pattern matching machine (M)
24.05.2019 Counting repeats (F)
31.05.2019 Finding repeats (F)
07.06.2019 Tandem repeats (F)
14.06.2019 More repeats (F)
21.06.2019 The number of alignments (J)
28.06.2019 Parametric alignment (J)
05.07.2019 Repetition (J)
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/04/11 16:08 by Jens Stoye