Lecture Time & Place: Tuesdays 10:00-12:00 at CABG61
Exercise Session Time & Place: Fridays 10:00-12:00 at CABG59
Office Hours: By appointment/email
Prerequisite: Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Basic Inequalities.
For instance, having passed the course Algorithms, Probability, and Computing (APC) is highly recommended, though not required formally.
If you're not sure whether you're ready for this class or not, please consult the instructor.
Grading: Three graded homeworks 30%, and a 3-hour final exam 70% (time and location to be determined).
Homeworks, Problem Sets, and Exercise Sessions: After lectures 4, 7, and 12, we will provide some specially-marked graded homeworks. Each of these graded homeworks will account for 10% of your grade.
You should submit your solutions within two weeks (to be made precise). The solutions must be typeset in LaTeX and should be emailed to Manuela Fischer (manuela.fischer at inf.ethz.ch) before the indicated deadline.
Moreover, we will regularly have other problem sets, roughly one per lecture. You do not need to hand in their solutions.
However, we strongly recommed that you try to solve all of these problems on your own, and seek help from the assistants, if you get stuck. These problem sets will be discussed during the exercise sessions.
The exercise sessions are an indispensable part of the course, the material covered in them will be included in the final exam, and we strongly recommend attending them.
Lecture Notes (last update Feb 5, 2019): Here is a compilation of the scribe notes of the 2018 offering, courtesy of Davin Choo.
Tentative Topic List
(09/18) Lecture 01: Approximation Algorithms 1 --- Greedy: Set Cover, Vertex Cover, and Monotone Submodular Maximization
A handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring 2011), and
another handout by Angelika Steger and Emo Welzl (Randomized Algorithms and Probabilistic Methods, ETH, Fall 2017).