Johannes Lengler: Catalogue data in Autumn Semester 2024 |
| 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-0026-00L | Algorithms and Data Structures | 7 credits | 3V + 2U + 1A | J. Lengler, D. Steurer | |||||||||||||||||||||||||||||||||||
| Abstract | The course provides the foundation of the design and analysis of algorithms. The material is introduced using classical algorithmic problems including graph problems. The necessary basic introduction to graph theory is provided as part of this course. | ||||||||||||||||||||||||||||||||||||||
| Learning objective | An understanding of the design and analysis of fundamental algorithms and data structures. A basic understanding of graph theory and several basic graph algorithms. | ||||||||||||||||||||||||||||||||||||||
| Content | This course is an introduction into the design and analysis of algorithms. On the one hand this includes classical algorithm design patterns including induction, divide-and-conquer and dynamic programming. We study these using classical example such as searching and sorting. On the other hand the course covers the interaction between algorithms and data structures including linked lists, search trees, heaps, and union-find structures. A particular focus are graph algorithms for shortest path and minimal spanning tree problems. We provide the necessary introduction into graph theory as part of this course. | ||||||||||||||||||||||||||||||||||||||
| Lecture notes | A complete script in German is under development. | ||||||||||||||||||||||||||||||||||||||
| Literature | Apart from the script and lecture materials, we recommend the following books as additional reference material. Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: An Introduction to Algorithms, 3rd edition, MIT Press, 2009 | ||||||||||||||||||||||||||||||||||||||
Competencies |
| ||||||||||||||||||||||||||||||||||||||
| 252-4202-00L | Seminar in Theoretical Computer Science  | 2 credits | 2S | A. Steger, B. Gärtner, M. Hoffmann, J. Lengler, D. Steurer | |||||||||||||||||||||||||||||||||||
| 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 restriction is: prior successful participation in a master level seminar in theoretical computer science. | ||||||||||||||||||||||||||||||||||||||
| 263-4500-00L | Advanced Algorithms | 9 credits | 3V + 2U + 3A | J. Lengler, B. Häupler, M. Probst | |||||||||||||||||||||||||||||||||||
| Abstract | This is a graduate-level course on algorithm design (and analysis). It covers a range of topics and techniques in approximation algorithms, sketching and streaming algorithms, and online algorithms. | ||||||||||||||||||||||||||||||||||||||
| Learning objective | This course familiarizes the students with some of the main tools and techniques in modern subareas of algorithm design. | ||||||||||||||||||||||||||||||||||||||
| Content | The lectures will cover modern topics in algorithm design and analysis, including the following: graph sparsifications while preserving cuts or distances, various approximation algorithms techniques and concepts, metric embeddings and probabilistic tree embeddings, online algorithms, multiplicative weight updates, streaming algorithms, sketching algorithms. | ||||||||||||||||||||||||||||||||||||||
| Lecture notes | https://people.inf.ethz.ch/~aroeyskoe/AA24 | ||||||||||||||||||||||||||||||||||||||
| Prerequisites / Notice | This course is designed for masters and doctoral students and it especially targets those interested in theoretical computer science, but it should also be accessible to last-year bachelor students. Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Concentrations. E.g., having passed the course Algorithms, Probability, and Computing (APC) is recommended, though not required formally. If you are not sure whether you're ready for this class or not, please consult the instructor. | ||||||||||||||||||||||||||||||||||||||
| Competencies |
| ||||||||||||||||||||||||||||||||||||||