Modulcode:	Inf-AlgSeq
Englische Bezeichnung:	Algorithms on Sequences
Modulverantwortliche(r):	Dr. Pamela Fleischmann
Turnus:	jedes Jahr (WS13/14 WS14/15 WS15/16 WS16/17 WS17/18 WS18/19 WS19/20 SS21 SS22 SS23 SS24 SS25)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 h lectures, 30 h exercises, 120 h self studies
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) WI (BSc Inf (15)) MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-Inf (MSc WInf (21)) TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) IG (MSc Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Englisch
Voraussetzungen:

Kurzfassung:

This course is an introduction into the theory of stringology, or algorithms on sequences of symbols (also called words or strings). Our main intention is to present a series of basic algorithmic and combinatorial results, which can be used to develop efficient word-processing tools. While the emphasis of the course is on the theoretical side of stringology, we also present a series of applications of the presented concepts in areas like data-compression or computational biology.

Lernziele:

We expect that the participants to this course will gain an understanding of classical string-processing tools. They are supposed to understand and be able to use in various situations: classical text algorithms (e.g., pattern matching algorithms, edit distance), classical text indexing data structures (e.g., suffix arrays / trees), and classical combinatorial results that are useful in this context (e.g., periodicity lemmas).

Lehrinhalte:

The main topics our course will cover are: basic combinatorics on words, pattern matching algorithms, data structures for text indexing (suffix arrays, suffix trees), text compression (Huffman encoding, Lempel-Ziv method), detection of regularities in words, algorithms for words with don't care symbols (partial words), word distance algorithms, longest common subsequence algorithms, approximate pattern matching. The presentation of each theoretical topic from the above will be accompanied by a brief discussion on its possible applications.

Weitere Voraussetzungen:

Math A from Kiel University or basic mathematical courses in which proving and basic proving techniques were taught.

Prüfungsleistung:

oral or written exam at the end of the course

Lehr- und Lernmethoden:

lecture with beamer and tablet presentation ; exercises

Verwendbarkeit:

Literatur:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms (3rd Edition), MIT Press, 2009.

M. Crochemore, C. Hancart, T. Lecroq: Algorithms on Strings, Cambridge University Press, 2007.

M. Crochemore, W. Rytter: Jewels of Stringology, World Scientific, 2002.

D. Gusfield. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, 1997.

Verweise:

Kommentar: