272-0300-00L  Algorithmics for Hard Problems

SemesterSpring Semester 2015
LecturersJ. Hromkovic, H.‑J. Böckenhauer, D. Komm
Periodicitytwo-yearly recurring course
Language of instructionGerman
CommentThis course d o e s n o t include the Mentored Work Specialised Courses with an Educational Focus in Computer Science A.


AbstractThis course unit looks into algorithmic approaches to the solving of hard problems. The seminar is accompanied by a comprehensive reflection upon the significance of the approaches presented for computer science tuition at high schools.
ObjectiveTo systematically acquire an overview of the methods for solving hard problems.
ContentFirst, 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.
Lecture notesUnterlagen und Folien werden zur Verfügung gestellt.
LiteratureJ. Hromkovic: Algorithmics for Hard Problems, Springer 2004.

R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006.

F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010.