David Steurer: Katalogdaten im Herbstsemester 2018

Name	Herr Prof. Dr. David Steurer
Lehrgebiet	Theoretische Informatik
Adresse	Professur Theoretische Informatik ETH Zürich, OAT Z 22.2 Andreasstrasse 5 8092 Zürich SWITZERLAND
E-Mail	david.steurer@inf.ethz.ch
URL	https://www.dsteurer.org
Departement	Informatik
Beziehung	Ausserordentlicher Professor

Nummer	Titel	ECTS	Umfang	Dozierende
252-0026-00L	Algorithmen und Datenstrukturen	7 KP	3V + 2U + 1A	M. Püschel, D. Steurer
Kurzbeschreibung	Es werden grundlegende Entwurfsmuster für Algorithmen sowie klassische algorithmische Probleme und Datenstrukturen behandelt. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. In die Graphentheorie wird kurz eingeführt.
Lernziel	Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen.
Inhalt	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.
Literatur	Th. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011
252-0209-00L	Algorithms, Probability, and Computing	8 KP	4V + 2U + 1A	E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
Kurzbeschreibung	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).
Lernziel	Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
Skript	Will be handed out.
Literatur	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.
263-4110-00L	Interdisciplinary Algorithms Lab Maximale Teilnehmerzahl: 12 Im Masterstudium können zusätzlich zu den Vertiefungsübergreifenden Fächern nur max. 10 KP mit Laboratorien erarbeitet werden. Weitere Labs werden auf dem Beiblatt aufgeführt.	5 KP	2P	A. Steger, D. Steurer, J. Lengler
Kurzbeschreibung	In this course students will develop solutions for algorithmic problems posed by researchers from other fields.
Lernziel	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.
Voraussetzungen / Besonderes	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.