Advanced Topics in Algorithms and Complexity

MSc Lecture - Winter 2024/25

Links

Courses IT-Systems Engineering , Algorithm Engineering Moodle

Description

This course explores key challenges in computational complexity, focusing on hard computational problems and strategies for dealing with them. We begin with a recap of NP-hardness and polynomial-time reductions. From there, we delve into coping mechanisms with approximation algorithms. We will discuss a few techniques to design such algorithms and the limitations of approximability.

We will explore the complexity landscape further with topics like Ladner's Theorem, which sheds light on problems that are neither NP-complete nor in P, and complexity dichotomies that categorize problems into solvable and unsolvable groups under various frameworks. The course also covers #P-completeness and computational counting, examining problems whose complexity extends beyond decision problems to counting solutions.

Requirements

The lecture is intended for Master students who are interested in exploring the theoretical limits of computation and tackling intractable problems.

Prerequisites: A solid understanding of algorithms, basic complexity theory (including P vs NP), discrete mathematics, and familiarity with formal proofs.

The lectures will be held in English!

Learning and teaching methods

In the lecture we will work problem-oriented and partly interactive. To achieve this, lecture and exercise sessions will be mixed as needed.

Organisation

The course will be organised via the Moodle of the Algorithm Engineering Chair. You can log in with your usual HPI-Login, and register for the course. Registration on the moodle page is required for all participants because the exercise sheets will be published and graded there.

Dates

The first lecture will take place on Thursday 17.10 at 11:00 at K-2.04.

We meet two times per week,

Tuesday at 13:30 - 15:00 in room K-2.05.
Thursday at 13:30 - 15:00 in room K-2.05.

Grading

For examination, each student will give a 30 minute presentation and produce a written report on one topic of the course. The presentation counts for 50% of the final grade, and the report for 50%.

An average homework grade of at least 50% is required for students to participate in the final exam, but does not contribute towards the grade.