252-0851-00L  Algorithms and Complexity

SemesterAutumn Semester 2017
LecturersA. Steger
Periodicityyearly recurring course
Language of instructionGerman


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.