Advanced Randomized Algorithms (Spring 2009, Q4)



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.

Learning outcomes and competences

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.

Time and Place

First lecture will be Tuesday April 14, 15.15, in Ada-018.

Course plan

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

Handin exercises


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.


Randomized Algorithms.

Course language


Compulsory programme

Homework handin.


Based on mandatory hand-in's and attendance, pass/fail.