Advanced Algorithmics (SS 15)
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.
Dates
Lectures and exercise sessions will be held throughout the reading period, that is from April 20th to July 24th. Individual sessions will take place weekly on
- Mondays, 10:00 - 11:30 in 48-654 (lecture),
- Wednesdays, 10:00 - 11:30 in 48-654 (lecture) and
- Fridays, 15:30 - 17:00 in 48-654 (exercises)
Note that we will not meet on public holidays, i.e. May 1st and May 25th. We will notify you about replacement dates and other exceptions on a case-by-case basis.
Exercises
There will be weekly exercise sheets with problems relating to the current lecture material. You can hand in your solutions for grading. We will discuss the exercise problems in weekly exercise sessions, provided sufficient participation. Your TA will be Raphael.
Participation is optional. Register via email to Raphael.
Material
| Week | Transcripts* | Exercises | Hands-On |
|---|---|---|---|
| I | L1, L2 | Sheet 1 | Sheet 1, Data |
| II | L3, L4 | Sheet 2 | Sheet 2 |
| III | L5, L6, E1 | Sheet 3 | — |
| IV | L7, L8, E2 | Sheet 4+ | Sheet 3 |
| V | L9, L10, E3 | Sheet 5 | Sheet 4 |
| VI | L11, E4 | Sheet 6 | — |
| VII | L12, L13, E5 | Sheet 7 | Sheet 5 |
| VIII | L14, E6 | Sheet 8 | — |
| IX | L15, L16, E7 | Sheet 9 | — |
| X | L17, L18, E8 | Sheet 10 | Sheet 6 |
| XI | L19, L20, E9 | Sheet 11 | — |
| XII | L21, L22, E10 | — | — |
| XIII | L23, E11 | — | — |
| XIV | E12, E13 | — | — |
+ Changed after first hand-out.
Find the Git repository used for collaboration on the hands-on sheets here. Please clone the repository and issue pull requests if you want to contribute.
Exams
There will be oral exams. Please contact Prof. Nebel towards the end of the lecture period to inquire about possible dates.
Suggested Reading
- D. Hochbaum: Approximation Algorithms for NP-Hard Problems
ISBN: 978-0-534-94968-6, available in our library (key text) - J. Hromkovič: Algorithmics for Hard Problems
ISBN: 978-3-642-07909-2, available in our library (key text) - V. Vazirani: Approximation Algorithms
ISBN: 978-3-540-65367-7, available in our library (key text) - R. Motwani, P. Raghavan: Randomized Algorithms
ISBN: 978-0-521-47465-8, available in our library - J. Balcazar, J. Diaz, J. Gabarro: Structural Complexity
ISBN: 978-3-540-58384-4 and 978-3-540-52079-5, available in our library (key text) - R. Niedermeier: Invitation to Fixed Parameter Algorithms
ISBN: 978-0-198-56607-6, available in our library