The course with the Cockertoo...
The course gives an introduction to randomized algorithms. Randomization allows to design efficient algorithms, which are often of elegant simplicity. Selected tools and techniques from probability theory and game theory are reviewed, with a view towards algorithmic applications. The main focus is a thorough discussion of the main paradigms, techniques, and tools in the design and analysis of randomized algorithms. A detailed analysis of numerous algorithms will illustrate the abstract concepts and techniques. You will learn about random walks, Markov chains, the probabilistic method, discrepancy theory, etc. The basics of probability theory will be reviewed.
T | Jan 17 | Events, probabilities, minimum cut; read [MU,Chapter 1] |
R | Jan 19 | Contraction algorithm, fingerprinting; read lecture notes §2.1 |
T | Jan 24 | Random variables, expectation, randomized quicksort |
R | Jan 26 | Binomial and geometric distributions, coupon collector problem |
T | Jan 31 | Iverson notation, conditional expectation |
R | Feb 02 | Markov's and Chebychev's inequality, variance |
T | Feb 07 | Randomized median algorithm |
R | Feb 09 | Chernoff inequalities, set balancing, moment generating functions |
T | Feb 14 | Packet routing in the hypercube |
R | Feb 16 | Birthday paradox, balls and bins |
T | Feb 21 | Balanced allocations, hashing |
R | Feb 23 | Bloom filters |
T | Feb 27 | Poisson distribution, Poisson approximation |