Randomized Algorithms

Instructor:      Prof. Friedrich Eisenbrand

Assistant:      Carsten Moldenhauer

Language:      English

ECTS credits: 4


Lecture:   Wednesday, 11am, MA B1 524

Exercise: Tuesday, 10am, MA B1 524


– if you have not(!) gotten an email for your oral exam but would like to take it, contact Carsten immediately.


Assignment Due Date Solutions
Assignment 1 October 4, 2011  
Assignment 2 October 18, 2011 Notes
Assignment 3 November 01, 2011 Notes
Assignment 4 November 15, 2011  
Assignment 5 November 29, 2011  
Assignment 6 December 20, 2011  
Assignment 7 January 10, 2012  


Date Content Suggested Reading
September 21 Introduction, Randomized Quicksort, Karger’s Algorithm for Min-Cuts Randomized Algorithms p. 7-9
September 28 Perfect Matchings  
October 5 Markov inequality, Chernoff bound for deviation below the mean, Set Cover Randomized Algorithms p. 67-70, Design of Approximation Algorithms p. 19-22
October 12 Chernoff bound for deviation above the mean, Raghavan&Thompson for Minimum Congestion Probability and Computing p. 61-67, Lecture notes of A. Blum & A. Gupta
October 19 Max Cut, vector programs, semidefinite programming, weighted majority with perfect expert Design of Approximation Algorithms p. 137-143
October 26 Weighted majority algorithms Arora,Hazan&Kale survey about weighted majority methods
November 2 Plotkin, Shmoys, Tardos – approximate LP solving, Clarkson’s algorithm Randomized Algorithms p. 262-268
November 9 LP basics and Clarkson I Gärtner&Welzl – Linear programming – Randomization and abstract frameworks (PDF)
November 16 Clarkson II, SeidelLP in arbitrary dimensions  
November 23 Primality tests  
November 30 Lovasz Local Lemma Randomized Algorithms Section 5.8, Probability and Computing Section 6.7
December 7 Constructive version of LLL Notes on Terence Tao’s blog
December 14 Randomized Algorithms for Max-Sat Approximation Algorithms (Vazirani) p. 130-136; Design of Approximation Algorithms p. 100-111


During the semester there will be an assignment every two weeks. There will be an oral exam at the end of the semester.

For PhD students:
to pass the course you are required to
– present your solutions to two of the assignment problems in the exercise sessions
and to obtain either
– at least 50% of all points of all assignments, or
– pass the oral exam.

For Master students:
to pass the course you are required to
– present your solutions to two of the assignment problems in the exercise sessions.
Further, you will obtain two grades, one for your solutions of the assignments and one for the oral exam. The final grade is the average of these two grades.
Note that if you are taking the course for credits towards your masters degree, you will not be able to use it as credits towards a potential following PhD at the EPFL.


Randomized Algorithms. Rajeev Motwani and Prabhakar Raghavan. ISBN 0-521-47465-5.

Probability and Computing. Michael Mitzenmacher and Eli Upfal. ISBN 978-0-521-83540-4.