Algorithm Engineering (SS 2026)

Lecture

Prof. Dr. Ulrich Meyer

Tuesday 10:00 - 12:00, in SR11
Thursday 10:00 - 12:00, in SR11

Tutorials

Lukas Geis

Wednesday 12:00 - 14:00, in SR11

Organisation of tutorials

We will issue problem sheets weekly on Tuesday; you have one week to complete the assignments and hand them in before Tuesday’s lecture electronically. Details will follow. The solutions will then be discussed in the following tutorial.

Language

The lecture is held in English. By mutual agreement, the language of instruction can be changed to German, too.

You can solve the assignments in German or in English.

Content

Algorithm engineering applies development cycles with a close coupling of design, analysis, implementation, and experimental evaluation in order to narrow the gap between theory and practice. A subset of the following topics will be covered in the lecture:

• Realistic input models including average-case complexity and smoothed analysis.
• Realistic machine models (e.g., memory hierarchies).
• Heuristics and experimental evaluation.
• Robustness, e.g., certifying algorithms, exact arithmetic.
• Case studies and algorithm libraries.

Exam

The exam type is to be determined.

Materials

Lecture notes and extra material

• Old handwritten script
• Lecture Notes AE1
• Lecture Notes AE2
• Lecture Notes Effiziente Algorithmen 2015 (German) in Latex (FIRST PART OF AE2)
• Energiesparendes Sortieren (NOS 2011)
• Energy-efficient sorting (Dagstuhl)
• U. Meyer: Average-case complexity of single-source shortest-path algorithms: lower and upper bounds (Journal of Algorithms)
  U. Meyer: Entwurf und Analyse sequentieller und paralleler Algorithmen für das kürzeste-Wege-Problem (Slides)
  T. Hagerup: Simpler Computation of Single-Source Shortest Paths in Linear Average Time (STACS 2004)
  A. Goldberg: A practical shortest path algorithm with linear expected time (SICOMP 2008)
  A. Negoescu, U. Meyer, and V. Weichert: New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches (TAPAS 2011)
  H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, R. F. Werneck: Route Planning in Transportation Networks
  U. Meyer, M. Penschuck: Generating Massive Scale-Free Networks under Resource Constraints (ALENEX 16)
  Graph Traversal and Graph Generation in External-Memory (Folien)
• M. Müller-Hannemann, S. Schirra (Eds.) Algorithm Engineering
• U. Meyer, P. Sanders, J. Sibeyn (Eds.) Algorithms for Memory Hierarchies

Lectures

Assignments