Johannes Lengler: Catalogue data in Autumn Semester 2019

Name Dr. Johannes Lengler
Address
Informatik (Theoretische Inform.)
ETH Zürich, CAB G 37.1
Universitätstrasse 6
8092 Zürich
SWITZERLAND
Telephone+41 44 632 70 53
E-mailjohannes.lengler@inf.ethz.ch
DepartmentComputer Science
RelationshipLecturer

NumberTitleECTSHoursLecturers
252-0851-00LAlgorithms and Complexity4 credits2V + 1UJ. Lengler, A. Steger
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.
252-4202-00LSeminar in Theoretical Computer Science Information 2 credits2SA. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov
AbstractPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
ObjectiveThe goal is to introduce students to current research, and to enable them to read, understand, and present scientific papers.
Prerequisites / NoticeThis seminar takes place as part of the joint research seminar of several theory groups. Intended participation is for students with excellent performance only. Formal minimal requirement is passing of one of the courses Algorithms, Probability, and Computing, Randomized Algorithms and Probabilistic Methods, Geometry: Combinatorics and Algorithms, Advanced Algorithms. (If you cannot fulfill this restriction, because this is your first term at ETH, but you believe that you satisfy equivalent criteria, please send an email with a detailed description of your reasoning to the organizers of the seminar.)