272-0300-00L Algorithmics for Hard Problems
|Semester||Spring Semester 2019|
|Lecturers||H.‑J. Böckenhauer, R. Kralovic|
|Periodicity||two-yearly recurring course|
|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.
|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, D. Kratsch: Exact Exponential Algorithms, 2010.