====== Parameterized Algorithms ======

**Lecturer:** [[people:thomasblaesius|]]

**Teaching Assistants:** [[people:vonderheydt|]], [[people:ellyschmidt]], [[people:wendyyi|]] 
\\
\\

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

===== Schedule =====

We meet every week on Monday and Thursday at 15:45 <del>in room 131</del>. 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                                                         |

===== Lecture =====

  - FPT-Basics: {{ :teaching:2026ss:param_algo:01-fpt-basics.pdf |with clicks}}, {{ :teaching:2026ss:param_algo:01-fpt-basics-print.pdf |without clicks}}
  - Bounded Search Trees: {{ :teaching:2026ss:param_algo:02-bounded-search-tree.pdf |with clicks}}, {{ :teaching:2026ss:param_algo:02-bounded-search-tree-print.pdf |without clicks}}
  - Iterative Compression: {{ :teaching:2026ss:param_algo:03-iterative-compression.pdf |with clicks}}, {{ :teaching:2026ss:param_algo:03-iterative-compression-print.pdf |without clicks}}

===== Exercise Session =====
  * {{ :teaching:2026ss:param_algo:01-exercise.pdf | Exercise 1}}
  * {{ :teaching:2026ss:param_algo:02-exercise.pdf | Exercise 2 (with solutions)}}
===== Exercise Sheets =====
Solutions to the sheets should be submitted via the ILIAS course (https://ilias.studium.kit.edu/ilias.php?baseClass=ilrepositorygui&ref_id=2902870)

  * {{ :teaching:2026ss:param_algo:sheet01.pdf | Sheet 1}} {{ :teaching:2026ss:param_algo:solution01.pdf | Solution 1}}
  * {{ :teaching:2026ss:param_algo:sheet02.pdf | Sheet 2}}, files for implementation task: {{ :teaching:2026ss:param_algo:vertex_cover_assignment.zip | vertex_cover_assignment.zip}}
===== Active Sessions =====
  - Bounded Search Trees: {{ :teaching:2026ss:param_algo:01-active-search-tree.pdf |slides}}