Johannes Lengler: Catalogue data in Autumn Semester 2018 |
| 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. | ||||
| 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  The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | 2 credits | 2S | E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov | |
| Abstract | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | ||||
| Objective | The goal is to introduce students to current research, and to enable them to read, understand, and present scientific papers. | ||||
| 263-4110-00L | Interdisciplinary Algorithms Lab  Number of participants limited to 12. In the Master Programme max. 10 credits can be accounted by Labs on top of the Interfocus Courses. Additional Labs will be listed on the Addendum. | 5 credits | 2P | A. Steger, D. Steurer, J. Lengler | |
| Abstract | In this course students will develop solutions for algorithmic problems posed by researchers from other fields. | ||||
| Objective | Students will learn that in order to tackle algorithmic problems from an interdisciplinary or applied context one needs to combine a solid understanding of algorithmic methodology with insights into the problem at hand to judge which side constraints are essential and which can be loosened. | ||||
| Prerequisites / Notice | Students will work in teams. Ideally, skills of team members complement each other. Interested Bachelor students can apply for participation by sending an email to steger@inf.ethz.ch explaining motivation and transcripts. | ||||