Lecturer: Dr. Mihyun Kang
Schedule
The lecture begins on: 19.10.2005.| VL | Wednesday | 11:00 - 13:00 | (RUD 25, 4.112) |
|---|---|---|---|
| Friday | 11:00 - 13:00 | (RUD 26, 1.307) | |
| Office hour | Wednesday | 14:00 - 15:00 | (RUD 25, 3.417) |
| or by appointment |
Classification
- Hauptstudium, Halbkurs
- Theoretische Informatik
Summary of the course
Randomized algorithms and probabilistic analysis are important tools in algorithm design and complexity theory. Randomness used in algorithms often leads to much faster algorithms that are easier to analyze than determinsitic algorithms, and the probabilistic viewpoint is essential to understand some computational models. This course covers basic probability theory, random graphs, random walks and Markov chain Monte Carlo methods.
The participants will learn how to use randomness in designing efficient algorithms and to analyze randomized algorithms using probabilistic methods.
Prerequisites
- The prerequisite is basic knowledge in discrete mathematics. The language of the course is English.
References
- , The Probabilistic Method, Cambridge University Press, 1995
- , Random Graphs, Cambridge University Press, 2002
- , Probabilistic Analysis of Algorithms, in Probabilistic Methods for Algorithmic Discrete Mathematics (M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed eds.), Algorithms and combinatorics 16, Springer, 1998
- , Random Graphs, John Wiley & Sons, Inc., 2000
- , Mathematical foundations of the Markov chain Monte Carlo method, in Probabilistic Methods for Algorithmic Discrete Mathematics (M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed eds.), Algorithms and combinatorics 16, Springer, 1998
- , The Probabilistic Method
- , Randomized Algorithms, John Wiley & Sons, Inc., 1992
English