Algorithm Engineering (SS 2021)


Lectures and tutorials will take place electronically.

  • Lectures will begin on 13.4. (Tuesday) at 12 ct.
  • Lectures and tutorials will be held live via screen sharing at the below mentioned times.
  • Access links to the streams will be available 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. 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 12:00 - 14:00
Wednesday 12:00 - 14:00

Office hours: By appointment


Hung Tran

Manuel Penschuck

Friday 16:00 - 18:00

Office hours: By appointment

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.


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.


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.


The exam type is to be determined.


Lecture notes and extra material


320.04.NotesRecordingBeyond Efficiency
421.04.NotesRecordingModelling Sudoku
527.04.NotesRecordingSSSP Basic & Refined Algorithm
628.04.NotesRecordingSSSP Dijkstra
704.05.NotesRecordingSSSP Dijkstra II
805.05.NotesRecordingSSSP Glob-Criterion, ABI-Dijkstra
911.05.NotesRecordingSSSP (u,v,k)-gadgets
1012.05.NotesRecordingSSSP Bellman-Ford
1118.05.NotesRecordingSSSP Lower Bounds
1219.05.NotesRecordingSSSP SP-S
1325.05.NotesRecordingSSSP SP-S II, Smoothed Complexity
1426.05.NotesRecordingSmoothed Complexity II
1501.06.NotesRecordingBidirectional search
1602.06.NotesRecordingBidirectional search II
1708.06.NotesRecordingExternal-Memory Model
1809.06.NotesRecordingMatrix Multiplication, Lower Bound Sorting
1915.06.NotesRecordingLower Bound Sorting II, EM Mergesort
2016.06.NotesRecordingEM Mergesort 2
2122.06.NotesRecordingEM Fifo & Dict
2223.06.NotesRecording(a, b)-trees, EM PQs
2329.06.NotesRecordingB-Trees, Time Forward Processing (TFP)
2430.06.NotesRecordingTFP Tree Expression Evaluation, Ind. Set
2506.07.NotesRecordingList Ranking
2607.07.NotesRecordingList Ranking II / Euler Tours
2713.07. RecordingMSFs / Connected Components
2814.07. RecordingRandom Graph Generation


Assignments Algorithm Engineering

Assignment 12 PM 
Assignment 12 PM 
Assignment 304.05.11.05. 12 PMtemplate, sudoku_3.txt, sudoku_4.txt
Assignment 411.05.18.05. 12 PMtemplate
Assignment 518.05.25.05. 12 PM 
Assignment 625.05.02.06. 12 PM (sic!) 
Assignment 701.06. (updated 11AM)08.06. 12 PM 
Assignment 815.06.22.06. 12 PM 
Assignment 922.06.29.06. 12 PM 
Assignment 1029.06.06.07. 12 PM