272-0300-00L Algorithmics for Hard Problems
| Semester | Spring Semester 2024 |
| Lecturers | D. Komm |
| Periodicity | two-yearly recurring course |
| Course | Does not take place this semester. |
| Language of instruction | German |
| Comment | This course d o e s n o t include the Mentored Work Specialised Courses with an Educational Focus in Computer Science A. |
| Abstract | This course unit looks into algorithmic approaches to the solving of hard problems, particularly with moderately exponential-time algorithms and parameterized algorithms. The seminar is accompanied by a comprehensive reflection upon the significance of the approaches presented for computer science tuition at high schools. | ||||||||||||||||||||||||||||||
| Learning objective | To systematically acquire an overview of the methods for solving hard problems. To get deeper knowledge of exact and parameterized algorithms. | ||||||||||||||||||||||||||||||
| Content | First, the concept of hardness of computation is introduced (repeated for the computer science students). Then some methods for solving hard problems are treated in a systematic way. For each algorithm design method, it is discussed what guarantees it can give and how we pay for the improved efficiency. A special focus lies on moderately exponential-time algorithms and parameterized algorithms. | ||||||||||||||||||||||||||||||
| Lecture notes | Unterlagen und Folien werden zur Verfügung gestellt. | ||||||||||||||||||||||||||||||
| Literature | J. Hromkovic: Algorithmics for Hard Problems, Springer 2004. R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006. M. Cygan et al.: Parameterized Algorithms, 2015. F. Fomin et al.: Kernelization, 2019. F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010. | ||||||||||||||||||||||||||||||
Competencies |
|