Modulcode:	infFGA-01a
Englische Bezeichnung:	Fine Grained Algorithms
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (SS22 SS24)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) BSc-WInf-WP-Inf (BSc WInf (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))
Lehrsprache:	Englisch
Voraussetzungen:

Kurzfassung:

We discuss basic tools, advanced algorithmic techniques and lower bounds for parameterized algorithms.

Lernziele:

Participants of this course will learn new algorithmic techniques to solve graph theoretical problems in the context of parameterization where the goal is to achieve a running time f(k) poly(n) for graphs with n vertices and function f which depends on a parameter k of the problem (e.g. the treewidth of the graph) or to show that this is impossible under some natural complexity assumptions.

Lehrinhalte:

1. Kernelization
2. Bounded search trees
3. Iterative compression
4. Randomized methods
5. Dynamic Programming and Integer Programming
6. Treewidth
7. Advanced algorithmic techniques
8. Lower bounds (W(1), W(2), ETH, kernelization)

Weitere Voraussetzungen:

Introduction to Algorithms, Mathematics A and B, or equivalent courses.

Prüfungsleistung:

The prerequisite for the examination is the successful completion of homework (Exercises).

For the exam students are set individual research tasks that they have to work on. The research task consists of 2 parts, which are weighted in a ratio of 2: 1:

written elaboration (approx. 8-15 pages) of a research result, e.g. improvement of an algorithm with regard to running time or improved lower bound for an optimization problem. Instead of a research result, it is also possible to implement a new algorithmic idea and an elaborate it.

a presentation of the result.

Lehr- und Lernmethoden:

Lecture on theoretical foundaton of parameterized algorithms with theoretical exercises to understand the algorithms and the underlying theory.

Verwendbarkeit:

Literatur:

M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh: Parameterized Algorithms, Springer Verlag.

Verweise:

Kommentar: