Advanced Algorithmics (SS 13)
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 (INF-54-54-V-7).
Dates
Lectures and exercise sessions will be held throughout the reading period, that is from April 15th to July 19th. Individual sessions will take place weekly on
- Wednesdays, 10:00 - 11:30 in 48-654 (lecture),
- Wednesdays, 13:45 - 15:15 in 48-654 (exercises) and
- Thursdays, 10:00 - 11:30 in 48-654 (lecture).
Note that we will not meet on public holidays, i.e. May 1st, May 9th, May 30th.
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 in the first lecture or via email to Raphael.
Material
Week | Lectures | Exercises | Hands-On |
---|---|---|---|
I | L1 | Sheet 1 | Sheet 1, Data |
II | L2, L3* | Sheet 2^{+} | Sheet 2 |
III | L4 | Sheet 3 | |
IV | L5 | Sheet 4^{+} | |
V | L6, L7 | Sheet 5^{+} | Sheet 3 |
VI | L8, L9 | Sheet 6 | Sheet 4 |
VII | L10 | Sheet 7 | |
VIII | L11, L12 | Sheet 8^{+} | Sheet 5 |
IX | L13*, L14 | Sheet 9^{+} | |
X | L15*, L16* | Sheet 10 | |
XI | L17, L18 | Sheet 11 | |
XII | L19, L20 | Sheet 12 | |
XIII | L21, L22 | Session 11 | |
XIV | L23 | Sheet 06 |
^{* There have been changes since the lecture.}
^{+ There have been changes since hand-in.}
Lecture slides are only available for logged in users; please use the credentials given to you in class.
Exams
Examination procedure will be announced in the first lecture.
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