Angelika Steger: Catalogue data in Autumn Semester 2016

Award: The Golden Owl
Name Prof. Dr. Angelika Steger
FieldInformatik (Theoretische Informatik)
Address
Inst. f. Theoretische Informatik
ETH Zürich, OAT Z 27
Andreasstrasse 5
8092 Zürich
SWITZERLAND
E-mailsteger@inf.ethz.ch
URLhttp://www.cadmo.ethz.ch/as/people/professor/asteger/index
DepartmentComputer Science
RelationshipFull Professor

NumberTitleECTSHoursLecturers
252-0209-00LAlgorithms, Probability, and Computing Information 8 credits4V + 2U + 1AE. Welzl, M. Ghaffari, A. Steger, P. Widmayer
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).
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-0417-00LRandomized Algorithms and Probabilistic Methods7 credits3V + 2U + 1AA. Steger, E. Welzl
AbstractLas 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
ObjectiveAfter 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.
ContentRandomized 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.
Lecture notesYes.
Literature- Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995)
- Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)
252-0851-00LAlgorithms and Complexity4 credits2V + 1UA. Steger
AbstractIntroduction: RAM machine, data structures; Algorithms: sorting, median, matrix multiplication, shortest paths, minimal spanning trees; Paradigms: divide & conquer, dynamic programming, greedy algorithms; Data Structures: search trees, dictionaries, priority queues; Complexity Theory: P and NP, NP-completeness, Cook's theorem, reductions.
ObjectiveAfter this course students know some basic algorithms as well as underlying paradigms. They will be familiar
with basic notions of complexity theory and can use them to classify problems.
ContentDie Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die zentralen Themengebiete sind: Sortieralgorithmen, Effiziente Datenstrukturen, Algorithmen für Graphen und Netzwerke, Paradigmen des Algorithmenentwurfs, Klassen P und NP, NP-Vollständigkeit, Approximationsalgorithmen.
Lecture notesJa. Wird zu Beginn des Semesters verteilt.
252-4101-00LACM-Lab
Does not take place this semester.
4 credits3PA. Steger
AbstractSolve programming problems from previous ACM Programming Contests (see http://acm.uva.es/problemset/); learn and use efficient programming methods and algorithms.
ObjectiveThe objective of this course is to learn how to solve algorithmic problems given as descriptions in natural language, similar to those posed in ACM Programming Contests. This includes appropriate problem modeling, choice of suitable (combinatorial) algorithms, and their efficient implementation using C/C++ and the STL.
252-4202-00LSeminar in Theoretical Computer Science Information 2 credits2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov
AbstractPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
ObjectiveThe goal is to introduce students to current research, and to enable them to read, understand, and present scientific papers.
263-0006-00LAlgorithms Lab6 credits4P + 1AA. Steger, E. Welzl, P. Widmayer
AbstractStudents 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.
ObjectiveThe 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).
LiteratureT. 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.