Advanced Algorithmics (SS 17)
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.
Dates
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
Exercises
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.
Exams
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