User Tools

Site Tools


teaching:2019summer:asa

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
teaching:2019summer:asa [2019/05/16 13:24]
Jens Stoye
teaching:2019summer:asa [2019/07/14 08:43] (current)
Jens Stoye [Time table]
Line 9: Line 9:
 ==== Literature ==== ==== Literature ====
  
-  * J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages, and Computation. ​Addison-Wesley1979.+  * 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 Learning2012.
   * H. R. Lewis, C. H. Papadimitriou:​ Elements of the Theory of Computation. Prentice Hall, 1997.   * 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.   * 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 ==== ==== Time table ====
Line 23: Line 25:
 | 10.05.2019 ​ | Pattern matching (J) | {{:​teaching:​2019summer:​asa:​ex04.pdf|Exercises 4}} | | 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}} | | 17.05.2019 ​ | Linear-time construction of suffix trees (J) | {{:​teaching:​2019summer:​asa:​ex05.pdf|Exercises 5}} |
-| 24.05.2019 ​ | Counting repeats ​(F)                                                                                     +| 24.05.2019 ​ | Context-free languages ​(F) | {{:​teaching:​2019summer:​asa:​ex06.pdf|Exercises 6}} 
-| 31.05.2019 ​ | Finding repeats ​(F)                                   ​                                                   +| 31.05.2019 ​ | Pushdown automata ​(F) | {{:​teaching:​2019summer:​asa:​ex07.pdf|Exercises 7}} 
-| 07.06.2019 ​ | Tandem repeats ​(F)                                                                                       +| 07.06.2019 ​ | Turing-Church thesis ​(F)| {{:​teaching:​2019summer:​asa:​ex08.pdf|Exercises 8}} 
-| 14.06.2019 ​ | More repeats ​(F)                                                                                         +| 14.06.2019 ​ | Decidability ​(F) | {{:​teaching:​2019summer:​asa:​ex09.pdf|Exercises 9}} 
-| 21.06.2019 ​ | The number ​of alignments ​(J)                                                                             +| 21.06.2019 ​ | Linear-time construction ​of suffix trees (cont'​d),​ BWT (J) | {{:​teaching:​2019summer:​asa:​ex10.pdf|Exercises 10}} 
-| 28.06.2019 ​ | Parametric alignment ​(J                                                                                +| 28.06.2019 ​ | Periodic structures in words 1 (M) | {{:​teaching:​2019summer:​asa:​ex11.pdf|Exercises 11}} 
-| 05.07.2019 ​ | TBA (M)                                        | --                                                 ​+| 05.07.2019 ​ | Periodic structures in words 2 (M) | -- | 
-| 12.07.2019 ​ | Oral exam (M,F,J)                                     ​| --                                                 ​| +| 12.07.2019 ​ | Oral exam (M,J) | -- |
- +
 ==== Examination dates ==== ==== Examination dates ====
  
teaching/2019summer/asa.1558013047.txt · Last modified: 2019/05/16 13:24 by Jens Stoye