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

252-0851-00L 4 Credits BSC , DR , MSC D-MATH , D-INFK
You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Algorithms and Complexity

Algorithmen und Komplexität

Lecturers & Examiners: Prof. Dr. Johannes Lengler
VVZ CR n/a

Last Updated: 2026-02-05 15:35:14

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, cryptography and zero-knowledge proofs.

Objective

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

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 , DR , MSC
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
Die Vorlesung wird hybrid stattfinden, d.h. eine beschränkte Zahl an Studierenden wird die Vorlesung im Hörsaal besuchen können. Aufgrund der momentanen Kapazitätsbeschränkungen reicht der Platz aber nicht für alle Studenten, deshalb ist für einen persönlichen Besuch eine Anmeldung über Moodle erforderlich. Für alle anderen wird die Vorlesung per Livestream übertragen. Die anwesenden Studierenden können eigene Fragen stellen und Fragen von Online-HörerInnen aus einem Chat weitergeben. Auf diese Weise wird eine bessere Interaktivität erreicht als bei reinem Streaming.
  • Tue 08:15-10:00 (ML F 39)
2 h weekly
exercise Algorithmen und Komplexität
Groups are selected in myStudies. Die genauen Unterrichtszeiten von ONLINE - Veranstaltungen werden von den Dozierenden kommuniziert.
  • Wed 12:00-13:00 (ON LI NE)
  • Wed 12:15-13:00 (CHN D 42)
  • Wed 12:15-13:00 (CHN D 44)
  • Wed 12:15-13:00 (CHN D 46)
  • Wed 13:15-14:00 (CHN D 42)
  • Wed 13:15-14:00 (CHN D 44)
  • Wed 13:15-14:00 (CHN D 46)
1 h weekly

Offered In