Advanced Algorithms WS 23/24

(Information in German below)

Instructors: László Kozma (lectures), Michaela Krüger (exercises)

This course will focus on the design and analysis of algorithms, with topics including:

• general principles of algorithm design,
• randomized algorithms,
• dynamic programming,
• flow problems on graphs,
• amortized analysis and advanced data structures,
• theory of NP-completeness,
• approximation methods for hard problems,
• other topics.

Prerequisites are basic knowledge of algorithms and relevant mathematics. All Bachelor and Master students interested in advanced algorithmic techniques are welcome.

The lectures will be in English.

• welcome announcement -- First meeting on Friday, 20th Oct, at 10 am, in T9/SR 005.
• some 2020 material (videos and notes with significant overlap with the current lectures) will be uploaded here as we go. (Note that there can still be differences in both order and content, as well as mistakes.)
• actual WS23/24 curriculum
• organization notes
• Exam: 23rd Feb, 2024, 10-12, A3HS1
• Re-Exam: 16th Apr, 2024, 10-12, HFB-A

Höhere Algorithmik

Es werden Themen wie:

• allgemeine Algorithmenentwurfsprinzipien,

• randomisierte Algorithmen,

• dynamische Programmierung,

• Flussprobleme in Graphen,

• Amortisierte Laufzeitanalyse und fortgeschrittene Datenstrukturen,

• NP-Vollständigkeit,

• Approximationsalgorithmen für schwere Probleme,

• arithmetische Algorithmen und Schaltkreise sowie schnelle Fourier-Transformation

behandelt.

Die Vorlesung wird in der englischen Sprache gehalten.

Literatur

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 4th Ed. MIT Press 2022
• Kleinberg, Tardos: Algorithm Design Addison-Wesley 2005.