Algorithm Engineering (SS 2019)
Lecture
Prof. Dr. Ulrich Meyer
Tuesdays 12:00 - 14:00
Wednsdays 12:00 - 14:00
SR 11 (R-M-S 11-15)
Tutorials
David Hammer
Hung Tran
Manuel Penschuck
Friday, 14:00 - 16:00
SR 11 (R-M-S 11-15)
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.
The solutions will then be discussed in the following tutorial.
The rules on bonification depend on the type of exam which will be announced in the near future.
Working in groups is suggested however if assignments are found to have been plagiarized we remove all points from the assignment on the first occurrence and the whole bonification on the second occurrence.
Language
The lecture is held in English.
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.
Literature
- Algorithm Engineering Bridging the Gap between Algorithm Theory and Practice
- You have free access to this book with your springer link account from university
Exams
There will be a written exam of 90 min (AE1 only, AE2 only for 5CP) or 180 min (AE1 + AE2 for 10CP, M-AE1 for 8CP).
Date: 25.07.2019, 9:00 - 12:00.
Location: Magnus-Hörsaal (Bockenheim)
Aids: None. Please, turn off all electrical devices (esp. mobile phones and smart watches) during the exam and do not carry them on you (put them in your bag).
Materials
Lecture notes and extra material
- Old handwritten script
- Lecture Notes AE1
- Lecture Notes AE2
- Lecture Notes Effiziente Algorithmen 2015 (German) in Latex
- Energiesparendes Sortieren (NOS 2011)
- 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)
Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck: Route Planning in Transportation Networks
Meyer et al: Generating Massive Scale-Free Networks under Resource Constraints (ALENEX 16)
Graph Traversal and Graph Generation in External-Memory (Folien) - U. Meyer, P. Sanders, J. Sibeyn (Eds.) Algorithms for Memory Hierarchies.
Assignments
Assignments Algorithm Engineering 1 (5CP and 8CP)
Assignments Algorithm Engineering 1 (8CP) and Algorithm Engineering 2 (5CP)
Exam Scope Algorithm Engineering 1+2 (10CP)
