IA167 String algorithms

Fakulta informatiky
jaro 2014
Rozsah
2/2/0. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučující
Alexandru Popa, Ph.D. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Rozvrh
Po 14:00–15:50 G123, Út 14:00–15:50 G126
Předpoklady
The students should have a good understanding of algorithms and their worst-case analysis. A basic understanding of Graph Theory is also expected.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
This course expands on courses Algorithm design I and Algorithm design II and aims to introduce the students into the world of stringology. At the end of the course the students should be able to: understand and implement the main algorithms used in this field; understand the connection of the topics presented in the course with other research areas; read and summarise a research paper on stringology.
Osnova
  • 1. Introduction. Classical offline pattern matching model and basic pattern matching algorithms (Rabin-Karp, Boyer-Moore, Knuth-Morris Pratt).
  • 2. Suffix trees, Ukkonen's algorithm for constructing a suffix tree in linear time.
  • 3. Suffix arrays. Building suffix arrays in linear time. Longest Common Prefix and Range Minimum Queries.
  • 4. Pattern matching with don't care symbols, errors, and mistakes. Abrahamson algorithm for computing mismatches. Wu-Manber algorithm. Fast Fourier Transforms and Kangaroo hopping.
  • 5. Pattern matching in the streaming model (where the text arrives online and our memory is less than the size of the pattern).
  • Porat&Porat algorithm solving the pattern matching in the streaming model using only O(log m log n) bits of extra memory.
  • 6. Edit distance vs longest common subsequence. LCS in linear space. Myers' algorithm for edit distance (algorithm used in 'diff' program from UNIX). Computing LCS in subquadratic time (the algorithm of Masek and Paterson).
  • 7. Indexing for approximate pattern matching.
  • 8. Two-dimensional pattern matching algorithms. Zhu-Takaoka algorithm. Bird/Baker algorithm.
  • 9. Introduction to equations on words.
  • 10. Shortest Common Superstring problem. Approximation algorithms and the connection with the Travelling Salesman problem.
  • 11. Introduction to combinatorics on words.
Literatura
    doporučená literatura
  • Jewels of stringology. Edited by Maxime Crochemore - Wojciech Rytter. River Edge, NJ: World Scientific, 2002, x, 310 p. ISBN 9810247826. info
  • GUSFIELD, Dan. Algorithms on strings, trees, and sequences : computer science and computional biology. Cambridge: Cambridge University Press, 1997, xviii, 534. ISBN 0521585198. info
Výukové metody
Lectures, class discussion.
Vyučovací jazyk
Angličtina
Informace učitele
fi.muni.cz/~popa
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2014/IA167