VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

272-0300-00L 5 Credits DZ , SHE , MSC , WBZ D-MATH , D-INFK
You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Algorithmics for Hard Problems

Algorithmik für schwere Probleme

Lecturers & Examiners: Dr. Hans-Joachim Böckenhauer, Dr. Richard Kralovic, Prof. Dr. Dennis Komm
This course d o e s n o t include the Mentored Work Specialised Courses with an Educational Focus in Computer Science A.
VVZ CR n/a

Last Updated: 2026-06-01 11:33:07

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.

Resources

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.

Learning Materials (Links)

General Information

Language
German
Levels
DZ , SHE , MSC , WBZ
Frequency
Every two years

Examination

Type
session examination
Mode
oral 30 minutes

Course Components

Type Title Time & Place Hours
lecture Algorithmik für schwere Probleme
  • Tue 09:15-11:00 (CAB G 56)
2 h weekly
exercise Algorithmik für schwere Probleme
  • Tue 11:15-12:00 (CAB G 56)
1 h weekly
independent project Algorithmik für schwere Probleme No time listed 1 h weekly

Offered In