The participants will after the course know how to apply randomized techniques in the context of parallel algorithms, online algorithms, graph algorithms, and computational geometry.
The participants must at the end of the course be able to:
Randomized algorithms for the above mentioned topics. Details will appear in the course plan below.
Mohammad Ali Abam, Peyman Afshani, Deepak Ajwani, and Peter Hachenberger.
First lecture will be Tuesday April 14, 15.15, in Ada-018.
Week | Date | Content | Literature | Lecturer |
---|---|---|---|---|
16 | 14/4 | VC-dimension, pages 11-14 of the book | The Discrepancy Method: Randomness and Complexity, B. Chazelle, Cambridge University Press, 2001 (available online) Approximation Algorithms in Geometry, Lecture Notes, Sariel Har-Peled |
Peyman Afshani |
17 | 21/4 14:00-15:00 at Turing-014 | ε-net, ε-approximation, page 171 of the book | ||
23/4 14:00-15:45 at Ada-018 | ε-net, ε-approximation, pages 177-178, 180-181 of the book; pages 72-73 of the lecture notes | |||
18 | 28/4 13:00-14:00 at Shannon 157 | weak ε-nets, pages 187-189 of the book | ||
30/4 14:00-15:45 at Ada-018 | PRAM- Introduction, Prefix sum, Maximum | Chapter 12: Parallel and Distributed Algorithms
from Randomized
Algorithms, R. Motwani and P. Raghavan, Cambridge University
Press, 1995 PRAM Algorithms, Lecture notes, Satish Rao PRAM Algorithms, Lecture notes, Siddhartha Chatterjee and Jan Prins | Deepak Ajwani | |
19 | 5/5 13:00-14:00 at Shannon 157 | PRAM - List Ranking, Integer Sorting | ||
20 | 12/5 13:00-14:00 at Shannon 157 | PRAM - General Sorting, Maximal Independent Set | ||
14/5 14:00-15:45 at Ada-018 | Markov chains and random walks |
Chapter 6: Parallel and Distributed Algorithms
from Randomized
Algorithms, R. Motwani and P. Raghavan, Cambridge University
Press, 1995 Chapter 1: Markov Chains by James Norris The PageRank Citation Ranking: Bringing Order to the Web by L. Page, S. Brin, R. Motwani, and T. Winograd |
Peter Hachenberger | |
21 | 19/5 13:00-14:00 at Shannon 157 | |||
22 | 26/5 13:00-14:00 at Shannon 157 | |||
28/5 14:00-15:45 at Ada-018 | Probabalistic Method | The Probabalistic Method, J. Matousek | Mohammad Abam | |
23 | 2/6 13:00-14:00 at Shannon 157 | Randomized Divide-and-Conquer Algorithms | Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, editors, CRC Press (Chapter 40) | |
4/6 14:00-15:45 at Ada-018 | Randomized Incremental Algorithms |
Literature for the course will be chapters from the below book and additional handouts.
(larger picture) |
Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995. 492 pages. ISBN: 0-521-47465-5. |
4th (Spring 2009).
5 ETCS points.
English.
Homework handin.
Based on mandatory hand-in's and attendance, pass/fail.