General
Overview:
This is an advanced level (optional) course in the Fall of 2022 diving deeper into the theory side of algorithms. The focus of this iteration is on randomized algorithms with applications on parallel and distributed algorithms. Randomization often allows for relatively simple algorithm design outsourcing the hard part to the analysis. If deterministic algorithms are desired, one can often derandomize the randomized design with a small overhead. In the context of parallel algorithms, randomness offers tools for symmetry breaking, a crucial tool for efficient algorithms.
Prerequisites: Fundamentals of algorithm design and analysis (e.g. CS-E3190). Mathematical maturity.
First lecture: 6.9.2022 at 12:15 - 14:00 in T5 - A133
First exercise: 15.9.2022 at 12:15 - 14:00 in Undergraduate Centre, ALMA MEDIA - U356
Learning objectives
- An introduction to central concepts in randomized algorithms such as concentration bounds.
- Analysis of randomized processes with limited dependence.
- Derandomization through the method of conditional expectations
Schedule
Week 1: Introduction. Basic concepts related to random variables such as probability, independence, Las Vegas / Monte Carlo algorithms and probability boosting.
Week 2: The coupon's collector problem. Your favorite supermarket has announced a special offer for anyone that collects all of their 100 different campaign stickers. After each purchase, you obtain one sticker uniformly at random. How many purchases do you need to make in expectation and high probability until you obtained all the stickers?
Notes: 02-notes
Week 3: Suppose there is a randomized process that creates a combinatorial object, such as a graph cut, with a strictly positive probability. Then clearly, such an object must exists! We introduce the probabilistic method and use the expectation argument to find large cuts and satisfying assignments for the SAT problem.
Notes: 03-notes
Week 4: TBA
Week 5: TBA
Week 6: TBA
Week 7: TBA
Week 8: Bonus problems
FilePracticalities File PDF document