David Steurer: Catalogue data in Autumn Semester 2019 |
| Name | Prof. Dr. David Steurer |
| Field | Theoretical Computer Science |
| Address | Professur Theoretische Informatik ETH Zürich, OAT Z 22.2 Andreasstrasse 5 8092 Zürich SWITZERLAND |
| david.steurer@inf.ethz.ch | |
| URL | https://www.dsteurer.org |
| Department | Computer Science |
| Relationship | Associate Professor |
| Number | Title | ECTS | Hours | Lecturers | |
|---|---|---|---|---|---|
| 252-0026-00L | Algorithms and Data Structures   | 7 credits | 3V + 2U + 1A | M. Püschel, D. Steurer | |
| Abstract | This course is about fundamental algorithm design paradigms, classic algorithmic problems, and data structures. The connection between algorithms and data structures is explained for geometric and graph problems. For this purpose, fundamental graph theoretic concepts are introduced. | ||||
| Learning objective | An understanding of the design and analysis of fundamental algorithms and data structures. | ||||
| Content | Es werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt. | ||||
| Literature | Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011 | ||||
| 252-0209-00L | Algorithms, Probability, and Computing | 8 credits | 4V + 2U + 1A | A. Steger, B. Gärtner, M. Ghaffari, D. Steurer | |
| Abstract | Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Linear Programming, Randomized Algebraic Algorithms (matchings), Probabilistically Checkable Proofs (introduction). | ||||
| Learning objective | Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory. | ||||
| Lecture notes | Will be handed out. | ||||
| Literature | Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest; Randomized Algorithms by R. Motwani und P. Raghavan; Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. | ||||
| 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.) | ||||