Angelika Steger: Katalogdaten im Herbstsemester 2022

Name	Frau Prof. Dr. Angelika Steger
Lehrgebiet	Informatik (Theoretische Informatik)
Adresse	Inst. f. Theoretische Informatik ETH Zürich, OAT Z 27 Andreasstrasse 5 8092 Zürich SWITZERLAND
E-Mail	steger@inf.ethz.ch
URL	http://www.cadmo.ethz.ch/as/people/professor/asteger/index
Departement	Informatik
Beziehung	Ordentliche Professorin

Nummer	Titel	ECTS	Umfang	Dozierende
252-0209-00L	Algorithms, Probability, and Computing	8 KP	4V + 2U + 1A	B. Gärtner, R. Kyng, A. Steger, D. Steurer, E. Welzl
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.
252-0417-00L	Randomized Algorithms and Probabilistic Methods	10 KP	3V + 2U + 4A	A. Steger
Kurzbeschreibung	Las Vegas & Monte Carlo algorithms; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks
Lernziel	After this course students will know fundamental techniques from probabilistic combinatorics for designing randomized algorithms and will be able to apply them to solve typical problems in these areas.
Inhalt	Randomized Algorithms are algorithms that "flip coins" to take certain decisions. This concept extends the classical model of deterministic algorithms and has become very popular and useful within the last twenty years. In many cases, randomized algorithms are faster, simpler or just more elegant than deterministic ones. In the course, we will discuss basic principles and techniques and derive from them a number of randomized methods for problems in different areas.
Skript	Yes.
Literatur	- Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995) - Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)
252-4202-00L	Seminar in Theoretical Computer Science	2 KP	2S	E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, D. Steurer, B. Sudakov
Kurzbeschreibung	Präsentation wichtiger und aktueller Arbeiten aus der theoretischen Informatik, sowie eigener Ergebnisse von Diplomanden und Doktoranden.
Lernziel	Das Lernziel ist, Studierende an die aktuelle Forschung heranzuführen und sie in die Lage zu versetzen, wissenschaftliche Arbeiten zu lesen, zu verstehen, und zu präsentieren.
Voraussetzungen / Besonderes	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-0006-00L	Algorithms Lab Only for master students!	8 KP	4P + 3A	A. Steger, E. Welzl
Kurzbeschreibung	Students learn how to solve algorithmic problems given by a textual description (understanding problem setting, finding appropriate modeling, choosing suitable algorithms, and implementing them). Knowledge of basic algorithms and data structures is assumed; more advanced material and usage of standard libraries for combinatorial algorithms are introduced in tutorials.
Lernziel	The objective of this course is to learn how to solve algorithmic problems given by a textual description. This includes appropriate problem modeling, choice of suitable (combinatorial) algorithms, and implementing them (using C/C++, STL, CGAL, and BGL).
Literatur	T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990. J. Hromkovic, Teubner: Theoretische Informatik, Springer, 2004 (English: Theoretical Computer Science, Springer 2003). J. Kleinberg, É. Tardos: Algorithm Design, Addison Wesley, 2006. H. R. Lewis, C. H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1998. T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2012. R. Sedgewick: Algorithms in C++: Graph Algorithms, Addison-Wesley, 2001.