Modulcode:	Inf-AdvAlg
Englische Bezeichnung:	Advanced Topics on Algorithms
Modulverantwortliche(r):	Prof. Dr. Dirk Nowotka
Turnus:	jedes Jahr im SS (SS16 SS17 SS18 SS19)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MEd Inf) WPI (MEd Inf) WI (MSc WInf) IG (MSc Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Englisch
Voraussetzungen:

Kurzfassung:

In this course we present a series of selected results on data structures and efficient algorithms, and discuss a series of areas in which they can be applied successfully. The emphasis of the course is on the theory, we also approach the problem of a practical implementation of the presented algorithms.

Lernziele:

We expect that the students that will participate in this lecture will become familiar with efficient sorting and searching methods, advanced data structures, dynamic data structures, as well as other efficient algorithmic methods, they will be able to estimate the complexity of those algorithms, and they will be able to apply those algorithms to particular programming problems (from practical or theoretical settings).

Lehrinhalte:

The main topics our course will cover are: efficient sorting and searching (non-comparison based methods, van Emde Boas trees, Radix Sort), advanced tree-structures (Fibonacci heaps, B-Trees, structures for working with disjoint sets), dynamic data structures (range minimum queries, lowest common ancestor, applications to string algorithms: suffix arrays, suffix trees), Hashing and Dictionaries, Young tableaux, geometric algorithms (convex hull), number theoretic algorithms. The presentation of each theoretical topic from the above will be accompanied by a brief discussion on its possible applications.

Weitere Voraussetzungen:

Prüfungsleistung:

Oral exam after the course

Lehr- und Lernmethoden:

Lecture with beamer and whiteboard presentation; exercises; programming exercises.

Verwendbarkeit:

Literatur:

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms (3rd Edition), MIT Press, 2009.
• E. Demaine: Advanced Data Structures, MIT Course nr. 6.851, 2012.
• PaweÅ‚ Gawrychowski and Mayank Goswami and Patrick Nicholson: Efficient Data Structures, MPI Course, Summer 2014.

Verweise:

Kommentar: