# Angelika Steger: Catalogue data in Autumn Semester 2014

Name | Prof. Dr. Angelika Steger |

Field | Informatik (Theoretische Informatik) |

Address | Inst. f. Theoretische Informatik ETH Zürich, CAB G 37.2 Universitätstrasse 6 8092 Zürich SWITZERLAND |

Telephone | +41 44 632 04 97 |

Fax | +41 44 632 13 99 |

steger@inf.ethz.ch | |

URL | http://www.cadmo.ethz.ch/as/people/professor/asteger/index |

Department | Computer Science |

Relationship | Full Professor |

Number | Title | ECTS | Hours | Lecturers | |
---|---|---|---|---|---|

252-0417-00L | Randomized Algorithms and Probabilistic Methods | 7 credits | 3V + 2U + 1A | A. Steger, A. Ferber | |

Abstract | 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 | ||||

Objective | 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. | ||||

Content | 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. | ||||

Lecture notes | Yes. | ||||

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-4101-00L | ACM-Lab | 4 credits | 3P | A. Steger | |

Abstract | Solve programming problems from previous ACM Programming Contests (see http://acm.uva.es/problemset/); learn and use efficient programming methods and algorithms. | ||||

Objective | The 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. | ||||

263-0006-00L | Algorithms Lab | 6 credits | 4P + 1A | A. Steger, E. Welzl, P. Widmayer | |

Abstract | 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. | ||||

Objective | 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). | ||||

Literature | 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. |