Parameterized Algorithms
Lecturer: Thomas Bläsius
Teaching Assistants: Jean-Pierre von der Heydt, Elly Schmidt, Wendy Yi
Many algorithmic problems appearing in applications are NP-hard. This means that there are no algorithms that efficiently solve these problems on every input (assuming P ≠ NP). Nonetheless, one can often solve these problems efficiently if the inputs are in some sense well-behaved. The parameterized complexity provides a way to formalize the concept of well-behaved inputs. This is done by associating with every input a parameter k, which represents a measure for the complexity of the input. Then the goal is to find an algorithms with running time polynomial in the input size, while allowing it to be exponential (or worse) in the parameter k. Compared to the coarse classification of problems in to polynomially solvable or NP-hard, this provides a more nuanced perspective on the computational complexity of problems.
ILIAS course: https://ilias.studium.kit.edu/ilias.php?baseClass=ilrepositorygui&cmdNode=xs:mo&cmdClass=ilobjcoursegui&ref_id=2902870&item_ref_id=0
Link to the Course Catalog: https://campus.studium.kit.edu/english/events/catalog.php#!campus/all/event.asp?gguid=0xC0A098BC09324A06803091FA10D2039F&rwfiguid=0x1E3F2182340B41DE9361C0EDDE382C0F
Link to Discord: https://discord.gg/JrM8qaJvCK
Schedule
We meet every week on Monday and Thursday at 15:45 in Room 131. The first lecture will take place on April 20 (Monday) at 15:45.
| Monday 15:45 | Thursday 15:45 | ||
|---|---|---|---|
| 20.4. | Lecture | 23.4. | Exercise |
| 27.4. | Lecture | 30.4. | Active Session |
| 4.5. | Lecture | 7.5. | Exercise |
| 11.5. | Lecture | 14.5. | 🌸 Ascension Day |
| 18.5. | Lecture | 21.5. | Exercise |
| 25.5. | 🌸 Pentecost | 28.5. | 🌸 Pentecost |
| 1.6. | Lecture | 4.6. | 🌸 Corpus Christi |
| 8.6. | Lecture | 11.6. | Exercise |
| 15.6. | Lecture | 18.6. | Active Session |
| 22.6. | Lecture | 25.6. | Exercise |
| 29.6. | Lecture | 2.7. | Active Session |
| 6.7. | Lecture | 9.7. | Exercise |
| 13.7. | Lecture | 16.7. | Active Session |
| 20.7. | Lecture | 23.7. | Exercise |
| 27.7. | Lecture | 30.7. | Summary |
Exercise Sheets
Solutions to the sheets should be submitted in the ILIAS course (https://ilias.studium.kit.edu/ilias.php?baseClass=ilrepositorygui&cmdNode=xs:mo&cmdClass=ilobjcoursegui&ref_id=2902870&item_ref_id=0)