Lecture, Algorithms and Data Structures II

The lecture takes place online, on Tu 9:15--10:45 and Wed 9:15--10:45.
The first lecture takes place on the 3rd November 2020.
There will be tutorials, the dates for the tutorials will be announced soon.
The material will be shared via the new Moodle. Here is a link to the course.
The lecture will be given synchron online.
A link to the lecture in LSF is here.
Tutorial will be assigned via Muesli.
The link to participate in the lecture is https://audimax.heiconf.uni-heidelberg.de/wnz9-chuy-wud3-mnukherevia.

ATTENTION: we switched last minute to BBB (link above) and do NOT use MS Teams.

More lecture details:

Goals: Students understand fundamental theoretical and practical concepts of advanced algorithms and data structures, get to know established methods and algorithms, are familiar with issues of efficient implementations, are able to identify/formulate algorithmic problems in/for different application areas, are able to analyse new algorithms as well as analysing their running time, and select appropriate algorithms for applications -- students are able to apply algorithms and data structures to real-world problems, and can objectively assess the quality of the results.

Content: Introduction to Algorithm Engineering, advanced data structures (efficient addressable priority queues, monotone priority queues, external priority queues), advances graph algorithms (strongly connected components, shortest paths, maximum flows / min s-t cuts, min-cost flows), techniques to solve problems to optimality (branch-and-bound, branch-and-reduce, dynamic programming, integer linear programming as a modelling tool), introduction to randomized algorithms, greedy algorithms, approximation algorithms, advanced string algorithms, geometric algorithms, external memory algorithms.

Prerequisites: Recommended: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Lineare Algebra 1

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

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