You are here: home » teaching » 2019summer » asa

Advanced Sequence Analysis

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

Contents

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

Literature

  • J. E. Hopcroft, R. Motwani and J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd edition, Pearson, 2006.
  • M. Sipser: Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012.
  • 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.
  • J. Stoye and D. Gusfield: Simple and flexible detection of contiguous repeats using a suffix tree, Theoretical Computer Science, Vol. 270, Issues 1–2, Pages 843-856, 2002.

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 (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) –

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