Instructor: Prof. Friedrich Eisenbrand
Assistant: Carsten Moldenhauer
Language: English
ECTS credits: 4
Lecture: Wednesday, 11am, MA B1 524
Exercise: Tuesday, 10am, MA B1 524
News
– if you have not(!) gotten an email for your oral exam but would like to take it, contact Carsten immediately.
Assignments
| 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 |
Contents
| 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 |
Grading
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.
Books
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.