Algorithm Engineering (SS 2020)

Lecture

Oral exams will be offered both after the first part and after the end of the lecture period.

Updated course regulations regarding B.Sc. students studying under the examination regulations of 2011 (PO2011):

The course can only be taken in two variants, namely for 5 CPs and 10 CPs.
Taking the course is not possible for 8 CPs.

Note that for M.Sc. students and B.Sc. students studying under regulations of 2019 this does not apply.

Lectures and tutorials will take place electronically.

Lectures will begin on 21.4. (Tuesday) at 10 ct.
Lectures and tutorials will be held live via screen sharing at the below mentioned times.
Access links to the streams can be found in Moodle using your HRZ-account. If you do not have an HRZ-account please contact Hung Tran.

By mutual agreement, the language of instruction can be changed to German.

In this semester communication will take place via website and e-mails more than ever. Please take a look at this website regularly. When sending e-mails to us please use your student e-mail address if possible. In the past, we experienced issues where messages ended in the junk folder.

Prof. Dr. Ulrich Meyer

Tuesday 10:00 - 12:00 SR 11 (R-M-S 11-15)
Thursday 10:00 - 12:00 Magnus Hörsaal (R-M-S 11-15)

Office hours: By appointment

Tutorials

Hung Tran

Manuel Penschuck

Friday 14:00 - 16:00
SR307 (R-M-S 11-15)

Office hours: By appointment

Please do not go to the university for the lecture and the tutorial. The above stated rooms are for the case when physical presence is possible again.

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. The rules on bonification depend on the type of exam which will be announced in the near future. Working in groups is recommended 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. 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

Oral exams will be offered both after the first part and after the end of the lecture period.

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)
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

Lecture 01 (21.04.): Handwritten Notes ⋅ Recording
Lecture 02 (23.04.): Handwritten Notes ⋅ Recording
Lecture 03 (28.04.): Handwritten Notes ⋅ Recording
Lecture 04 (30.04.): Handwritten Notes ⋅ Recording
Lecture 05 (05.05.): Handwritten Notes ⋅ Recording
Lecture 06 (07.05.): Handwritten Notes ⋅ Recording
Lecture 07 (12.05.): Handwritten Notes ⋅ Recording
Lecture 08 (14.05.): Handwritten Notes ⋅ Recording
Lecture 09 (19.05.): Handwritten Notes ⋅ Recording
Lecture 10 (26.05.): Handwritten Notes ⋅ Recording
Lecture 11 (28.05.): Handwritten Notes ⋅ Recording
Lecture 12 (02.06.): Handwritten Notes ⋅ Recording ⋅ annotated Meyer et al. (TAPAS 2011)
Lecture 13 (04.06.): Handwritten Notes ⋅ Recording
Lecture 14 (09.06.): Handwritten Notes ⋅ Recording
Lecture 15 (16.06.): Handwritten Notes ⋅ Recording
Lecture 16 (18.06.): Handwritten Notes ⋅ Recording
Lecture 17 (23.06.): Handwritten Notes ⋅ Recording
Lecture 18 (25.06.): Handwritten Notes ⋅ Recording
Lecture 19 (30.06.): Handwritten Notes ⋅ Recording
Lecture 20 (02.07.): Handwritten Notes ⋅ Recording
Lecture 21 (07.07.): Handwritten Notes ⋅ Recording
Lecture 22 (09.07.): Handwritten Notes ⋅ Recording
Lecture 23 (14.07.): Handwritten Notes ⋅ Recording
Lecture 24 (16.07.): Handwritten Notes ⋅ Recording

Assignments

Assignments Algorihm Engineering 1 (5CP and 8CP)

Download	Issued	Due	Files
Assignment 1	28.04.	05.05. 10 AM
Assignment 2	05.05.	12.05. 10 AM	template, sudoku_3.txt, sudoku_4.txt
Assignment 3	12.05.	19.05. 10 AM
Assignment 4	26.05. (updated 12.26 AM)	02.06. 10 AM	template
Assignment 5	02.06.	09.06. 10 AM
Assignment 6	09.06.	16.06. 10 AM	updates to 6.1a) are indicated in red
Assignment 7	16.06.	23.06. 10 AM
Assignment 8	30.06.	07.07. 10 AM
Assignment 9	07.07.	14.07. 10 AM

Menu