SoSe 19: Advanced Topics in Algorithms
László Kozma
Additional information / Pre-requisites
Target Audience
Masters students in Computer Science or Mathematics, advanced Bachelor students.
Prerequisites
"Advanced Algorithms" or a similar class
Comments
Randomized algorithms
The word "random" often has negative connotations: if something is random, then it may be unpredictable, unprecise, noisy, erratic, difficult to understand. It is therefore surprising that randomness is of great help in algorithmic problem-solving. Algorithms that use randomness are often more efficient, easier to implement and easier to understand than their deterministic counterparts, and in some cases, the only efficient method we know for solving a problem is a randomized one. Randomness can also be viewed as a useful (and often limited) computational resource, similarly to time and space usage. Understanding the exact role that randomness plays in computation is one of the great scientific questions of our time.
This course will survey various algorithmic techniques, covering different aspects of the use of randomness in computation. Topics include (but are not limited to): randomized binary search trees, hashing-based data structures, random sampling, random walks, linear-time minimum spanning trees, cuts in graphs, verifying matrix multiplication, predicting the future with the help of experts, geometric algorithms, randomized incremental construction, load balancing, pattern matching, the probabilistic method, Chernoff bounds, primality testing, isolation, online algorithms, ski-rental and paging, approximation and LP-rounding.
(The course will be given in English.)
closeSuggested reading
[MR] R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995
[MU] M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005
[CLRS] T. H. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, MIT Press 2009
[KT] J. Kleinberg, E. Tardos. Algorithm Design, Addison-Wesley 2005.
[M] J. Matoušek. Lectures in Discrete Geometry. Springer Verlag, 2002
close27 Class schedule
Regular appointments
Randomized algorithms
The word "random" often has negative connotations: if something is random, then it may be unpredictable, unprecise, noisy, erratic, difficult to understand. ... read more