David Steurer: Catalogue data in Autumn Semester 2024

Name Prof. Dr. David Steurer
FieldTheoretical Computer Science
Address
Professur Theoretische Informatik
ETH Zürich, OAT Z 22.2
Andreasstrasse 5
8092 Zürich
SWITZERLAND
E-maildavid.steurer@inf.ethz.ch
URLhttps://www.dsteurer.org
DepartmentComputer Science
RelationshipAssociate Professor

NumberTitleECTSHoursLecturers
252-0026-00LAlgorithms and Data Structures7 credits3V + 2U + 1AJ. Lengler, D. Steurer
AbstractThe 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 objectiveAn understanding of the design and analysis of fundamental algorithms and data structures. A basic understanding of graph theory and several basic graph algorithms.
ContentThis 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 notesA complete script in German is under development.
LiteratureApart 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
CompetenciesCompetencies
Subject-specific CompetenciesConcepts and Theoriesassessed
Techniques and Technologiesassessed
Method-specific CompetenciesAnalytical Competenciesassessed
Media and Digital Technologiesassessed
Problem-solvingassessed
Social CompetenciesCommunicationfostered
Cooperation and Teamworkfostered
Personal CompetenciesCreative Thinkingassessed
Critical Thinkingassessed
Integrity and Work Ethicsfostered
Self-direction and Self-management fostered
252-0209-00LAlgorithms, Probability, and Computing Information 8 credits4V + 2U + 1AB. Gärtner, R. Kyng, A. Steger, D. Steurer
AbstractAdvanced 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 objectiveStudying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
Lecture notesWill be handed out.
LiteratureIntroduction 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-00LSeminar in Theoretical Computer Science Information Restricted registration - show details 2 credits2SA. Steger, B. Gärtner, M. Hoffmann, J. Lengler, D. Steurer
AbstractPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
Learning 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 restriction is: prior successful participation in a master level seminar in theoretical computer science.