VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

251-0851-00L 4 Credits BSC , DS D-MATH , D-INFK

Algorithms and Complexity

Algorithmen und Komplexität

Lecturers & Examiners: Prof. Dr. Angelika Steger

VVZ CR n/a

Last Updated: 2026-02-05 15:24:40

Abstract

Introduction: 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; Outlook: optimization problems, approximation algorithms

Content

Die 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.

Resources

Lecture Notes

Ja. Wird zu Beginn des Semesters verteilt.

General Information

Language: German
Levels: BSC , DS
Frequency: Yearly recurring

Examination

Type: session examination
Mode: written 120 minutes
Aids: 10 handgeschriebene Din A4 Blätter

Course Components

Type	Title	Time & Place	Hours
lecture	Algorithmen und Komplexität	Tue 08:15-10:00 (HG D 1.2)	2 h weekly
exercise	Algorithmen und Komplexität	Thu 16:15-17:00 (CAB G 56) Thu 16:15-17:00 (HG E 1.2) Thu 16:15-17:00 (HG E 33.1) Thu 16:15-17:00 (HG F 26.3)	1 h weekly