AG Algorithmen und Komplexität

Advanced Algorithmics (SS 17)

NP-hard problems are relevant in practical situations!

Complexity theory tells us that there are problems that seem to be inherently hard to solve. What can we do when faced which such a problem in practice? Over the decades, some useful techniques for tackling hard problems have emerged, for example

  • using heuristics to limit search spaces,
  • accepting wrong outputs with certain probability and
  • accepting suboptimal but still decent solutions.

We follow these approaches and develop theoretical foundations for solving hard problems sufficiently well and fast in practice.

This is an 8 ECTS advanced-level master course; find details in the official documents.

Solid knowledge of elementary algorithms and mathematical maturity are assumed; an introductory course on complexity classes P and NP is helpful, even though we recap the main results in class.

Please register in OLAT for the course to receive email notifications about news and short-term announcements.


Lectures and exercise sessions will be held throughout the reading period, that is from April 18th to July 22th. We will have two weekly sessions of lectures and one exercise class.

  • Lectures: every Monday and Thursday, 15:30 - 17:00 in room 11-201
  • Exercise Class:  every Friday, 13:45 - 15:15 in room 48-453


There will be exercise sheets with problems relating to the current lecture material. We will discuss the exercise problems in weekly exercise sessions. Your tutor will be Marvin Petersen.


There will be oral exams. The exams will have to be in July, so please arrange for some time to prepare directly after the reading period.

Oral exams can only be taken after successful participation in the course. This includes reaching at least a 1/e fraction of the total points on all exercise sheets.

Lecture Notes

Slides and notes from the lectures will be available here.

Lecture Videos

Recorded lectures are on youtube.

Suggested Reading

The lecture is self-contained and lecture notes will be available.

Further reading (might be subject to change)

  • J. Hromkovič: Algorithmics for Hard Problems
    ISBN: 978-3-642-07909-2, available in our library
  • J. Flum, M. Grohe: Parametrized Complexity Theory
    ISBN: 978-3-540-29952-3, available as pdf by our library
  • R. Niedermeier: Invitation to Fixed Parameter Algorithms
    ISBN: 978-0-198-56607-6, available in our library
  • M. Mitzenmachen, E. Upfal: Probability and Computing - Randomized Algorithms and Probabilistic Analysis
    ISBN: 978-0-521-83540-4
  • S. Arora, B. Barak: Computation Complexity - A Modern Approach
    ISBN: 978-0-521-42426-4, available in our library
  • D. Hochbaum: Approximation Algorithms for NP-Hard Problems
    ISBN: 978-0-534-94968-6, available in our library
  • V. Vazirani: Approximation Algorithms
    ISBN: 978-3-540-65367-7, available in our library

Prior Iterations

Advanced Algorithmics (SS 15)
Advanced Algorithmics (SS 13)