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. |
Courses
| Number | Title | Hours | Lecturers | |
|---|---|---|---|---|
| 272-0300-00 V | Algorithmik für schwere Probleme Does not take place this semester. | 2 hrs | D. Komm | |
| 272-0300-00 U | Algorithmik für schwere Probleme Does not take place this semester. | 1 hrs | D. Komm | |
| 272-0300-00 A | Algorithmik für schwere Probleme Does not take place this semester. | 1 hrs | D. Komm |
Catalogue data
| 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 |
|
Performance assessment
| Performance assessment information (valid until the course unit is held again) | |
Performance assessment as a semester course | |
| ECTS credits | 5 credits |
| Examiners | H.-J. Böckenhauer, D. Komm |
| Type | session examination |
| Language of examination | German |
| Repetition | The performance assessment is offered every session. Repetition possible without re-enrolling for the course unit. |
| Mode of examination | oral 30 minutes |
| This information can be updated until the beginning of the semester; information on the examination timetable is binding. | |
Learning materials
| Main link | Information |
| Only public learning materials are listed. | |
Groups
| No information on groups available. |
Restrictions
| There are no additional restrictions for the registration. |