Differences

This shows you the differences between two versions of the page.

Link to this comparison view

teaching:2019summer:asa [2020/02/14 09:07] (current)
Line 1: Line 1:
 +====== 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]] ​