252-0851-00L  Algorithms and Complexity

SemesterAutumn Semester 2019
LecturersJ. Lengler, A. Steger
Periodicityyearly recurring course
Language of instructionGerman


252-0851-00 VAlgorithmen und Komplexität2 hrs
Tue08-10HG D 1.2 »
J. Lengler, A. Steger
252-0851-00 UAlgorithmen und Komplexität1 hrs
Thu16-17CAB G 52 »
16-17CAB G 56 »
16-17IFW C 35 »
16-17LEE C 114 »
16-17LEE D 105 »
J. Lengler, A. Steger

Catalogue data

AbstractIntroduction: RAM machine, data structures; Algorithms: sorting, median, matrix multiplication, shortest paths, minimal spanning trees; Paradigms: divide & conquer, dynamic programming, greedy algorithms; Data Structures: search trees, dictionaries, priority queues; Complexity Theory: P and NP, NP-completeness, Cook's theorem, reductions.
ObjectiveAfter this course students know some basic algorithms as well as underlying paradigms. They will be familiar
with basic notions of complexity theory and can use them to classify problems.
ContentDie Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die zentralen Themengebiete sind: Sortieralgorithmen, Effiziente Datenstrukturen, Algorithmen für Graphen und Netzwerke, Paradigmen des Algorithmenentwurfs, Klassen P und NP, NP-Vollständigkeit, Approximationsalgorithmen.
Lecture notesJa. Wird zu Beginn des Semesters verteilt.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
In examination block forBachelor's Programme in Mathematics 2010; Version 24.02.2016 (Examination Block 1)
Bachelor's Programme in Mathematics 2016; Version 25.02.2020 (Examination Block 1)
ECTS credits4 credits
ExaminersJ. Lengler, A. Steger
Typesession examination
Language of examinationGerman
RepetitionThe performance assessment is offered every session. Repetition possible without re-enrolling for the course unit.
Mode of examinationwritten 120 minutes
Written aids10 handgeschriebene Din A4 Blätter
If the course unit is part of an examination block, the credits are allocated for the successful completion of the whole block.
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

Main linkInformation
Only public learning materials are listed.


No information on groups available.


There are no additional restrictions for the registration.

Offered in

Computer Science (General Courses)Computer Science for Non-Computer ScientistsZInformation
Mathematics BachelorExamination Block IOInformation