Johannes Lengler: Catalogue data in Autumn Semester 2019 |
| Name | Prof. Dr. Johannes Lengler |
| Address | Informatik (Theoretische Inform.) ETH Zürich, OAT Z 14.1 Andreasstrasse 5 8092 Zürich SWITZERLAND |
| johannes.lengler@inf.ethz.ch | |
| Department | Computer Science |
| Relationship | Adjunct Professor |
| Number | Title | ECTS | Hours | Lecturers | |
|---|---|---|---|---|---|
| 252-0851-00L | Algorithms and Complexity | 4 credits | 2V + 1U | J. Lengler, A. Steger | |
| 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. | ||||
| Learning 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. | ||||
| Lecture notes | Ja. Wird zu Beginn des Semesters verteilt. | ||||
| 252-4202-00L | Seminar in Theoretical Computer Science  | 2 credits | 2S | A. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov | |
| Abstract | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | ||||
| Learning objective | The goal is to introduce students to current research, and to enable them to read, understand, and present scientific papers. | ||||
| Prerequisites / Notice | This 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.) | ||||