Lecture, Algorithm Engineering

The lecture takes place online, on Mo 9:15--10:45 and Tu 9:15--10:45.
The first lecture takes place on the 12th April 2021. The lecture takes place in HeiConf (https://audimax.heiconf.uni-heidelberg.de/uwd7-4hrj-q3qu-z2nh). The link to the Moodle of the lecture is here: https://moodle.uni-heidelberg.de/course/view.php?id=6383.

More lecture details:


Goals: Students obtain a systematic understanding of algorithmic questions and solution approaches in the area of algorithm engineering. The students will be able to transfer the learned techniques onto similar problems and be able to interpret and understand current research topics in the area of algorithm engineering. Given a real-world problem, students are able to select appropriate algorithms to come up with and implement efficient solutions. In particular, students know realistic machine models and applications, algorithm design, implementation techniques, experimental methodology and can interpret of measurements.

Content: The listed abilities will be learned by concrete examples. In particular, we will almost always cover the best practical and theoretical methods. This methods often deviate a lot by the algorithms learned in the basic courses. To this end the lecture covers FPT/Kernelization in practice (independent set, vertex cover, (all) minimum cuts (NOI algorithm), clique cover, node ordering), multi-level algorithms (graph partitioning, modularity clustering, dynamic clustering, process mapping, spectral techniques, exact approaches), route planning (contraction hierarchies, arc-flags, hub-label algorithm), dynamic graph algorithms (single-source reachability, transitive closure, matching, minimum cuts, graph generation).

Prerequisites: Recommended: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Lineare Algebra 1, Algorithms and Data Structures II (recommended, but not necessary)

Leistungspunkte: 8 LP

Duration: one semester

Teaching mode: 4 SWS lecture (in English), 2 SWS tutorial, homework assignments

Workload: 240h; thereof 90h lectures and tutorials, 15h exam preparations, 135h lecture wrap-up and homework

Passing the course: Successful participation in the exercises (at least 50\% of total achievable points) and passing a written exam

Verwendbarkeit:
B.Sc. Angewandte Informatik,
Lehramt Informatik,
M.Sc. Angewandte Informatik,
M.Sc. Scientific Computing