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&ref_id=2902870
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
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.
Update: We got a larger room – From April 23 on, we will meet in room 045/046 in building 50.41 except for two dates (see table below)
Update 2: From May 7 on, we will split the Thursday sessions, one starting at 2pm and one starting at 3.45pm in room 131 in the computer science building.
| Monday 15:45 (in 50.41) | Thursday 14:00 and 15:45 in 131 | ||
|---|---|---|---|
| 20.4. | Lecture | 23.4. | Exercise |
| 27.4. | Lecture | 30.4. | Active Session (10.81, Theodor-Rehbock-Seminarraum (HS59)) |
| 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 (30.35 Hochspannungstechnik-Hörsaal (HSI)) | 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 |
Solutions to the sheets should be submitted via the ILIAS course (https://ilias.studium.kit.edu/ilias.php?baseClass=ilrepositorygui&ref_id=2902870)