Karl Bringmann: Catalogue data in Spring Semester 2015 |
Name | Mr Karl Bringmann |
Department | Computer Science |
Relationship | Lecturer |
Number | Title | ECTS | Hours | Lecturers | |
---|---|---|---|---|---|
263-4100-00L | Randomized Algorithms and Probabilistic Methods: Advanced Topics | 5 credits | 2V + 1U + 1A | J. Lengler, K. Bringmann, T. S. Luria | |
Abstract | Advanced introduction to random walks. | ||||
Objective | Students will learn some advances techniques to analyze random walks, and they will see some examples of how algorithms make use of random walks. To successfully complete this course students need to be able to apply the acquired techniques and use random walks as a tool for designing algorithms. | ||||
Content | The lecture gives an advanced introduction to random walks. We treat methods to analyze them, and applications in which random walks are used. Some open problems will be discussed as well. Topics: - drift analysis - rapidly mixing random walks - random sampling and/or approximate counting e.g. of triangulations, latin squares - expander graphs - volume estimation of convex bodies - differential equation method | ||||
Prerequisites / Notice | Randomized Algorithms and Probabilistic Methods, or a similar course |