====== Advanced Sequence Analysis ======

|[[http://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=153224525|392119]]/[[http://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=153253078|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) | {{:teaching:2019summer:asa:ex01.pdf|Exercises 1}} |
| 19.04.2019  | -- Good Friday -- | -- |
| 26.04.2019  | Trie, DAWG, Automata (M) | {{:teaching:2019summer:asa:ex02.pdf|Exercises 2}} |
| 03.05.2019  | Automata: determinisation, minimization (M) | {{:teaching:2019summer:asa:ex03.pdf|Exercises 3}} |
| 10.05.2019  | Pattern matching (J) | {{:teaching:2019summer:asa:ex04.pdf|Exercises 4}} |
| 17.05.2019  | Linear-time construction of suffix trees (J) | {{:teaching:2019summer:asa:ex05.pdf|Exercises 5}} |
| 24.05.2019  | Context-free languages (F) | {{:teaching:2019summer:asa:ex06.pdf|Exercises 6}} |
| 31.05.2019  | Pushdown automata (F) | {{:teaching:2019summer:asa:ex07.pdf|Exercises 7}} |
| 07.06.2019  | Turing-Church thesis (F)| {{:teaching:2019summer:asa:ex08.pdf|Exercises 8}} |
| 14.06.2019  | Decidability (F) | {{:teaching:2019summer:asa:ex09.pdf|Exercises 9}} |
| 21.06.2019  | Linear-time construction of suffix trees (cont'd), BWT (J) | {{:teaching:2019summer:asa:ex10.pdf|Exercises 10}} |
| 28.06.2019  | Periodic structures in words 1 (M) | {{:teaching:2019summer:asa:ex11.pdf|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|Teaching]]