Module Number

INFO-4412
Module Title

Algorithms and Complexity
Lecture Type(s)

Lecture, Tutorial
ECTS 9
Work load
- Contact time
- Self study
Workload:
270 h
Class time:
90 h / 6 SWS
Self study:
180 h
Duration 1 Semester
Frequency Irregular
Language of instruction German and English
Type of Exam

Written exam (in case of a small number of participants: oral tests)

Content

Topics include matching, MinCostFlow, linear programming, approximation schemes, network analysis, algorithmic geometry, complexity issues such as lower bounds.

Objectives

Students deepen their knowledge of algorithmic techniques in various problem areas. This includes the application of complex graph algorithms, the mastery of strategies for network analysis as well as the ability to apply and develop approximation methods themselves. In the area of complexity issues, students are able to assess problems according to their degree of difficulty and also prove these assessments using the techniques they have learned.

Allocation of credits / grading
Type of Class
Status
SWS
Credits
Type of Exam
Exam duration
Evaluation
Calculation
of Module (%)
Lecture
V
o
4
6.0
wt
90
g
100
Tutorial
Ü
o
2
3.0
Prerequisite for participation There are no specific prerequisites.
Lecturer / Other Kaufmann
Literature

Raghavan, Magnati, Orlin: Network Algorithms
Mehlhorn, Näher: LEDA - A platform for combinatorial and geometric computation
Papadimitriou, Steiglitz: Combinatorial optimization : algorithms and complexity

Last offered unknown
Planned for Wintersemester 2024
Assigned Study Areas INFO-INFO, INFO-THEO, MEDI-APPL, MEDI-INFO, ML-CS