Advanced Algorithms

Credits 
7 

Lecturer 
Michael Kapralov


Schedule 
Lectures: Tuesdays 810 in RLCE 1240 on zoom and Thursdays 1315 in CM 1 on zoom.
Exercises: Fridays 1013 in CM 1105 and INF1 on zoom.

A first graduate course in algorithms, this course assumes minimal background,
but moves rapidly. The objective is to learn the main techniques of algorithm
analysis and design while building
a repertory of basic algorithmic solutions to problems in many domains.
This is a course for Master students. The lectures will be in English.
For more details see the official couse book here.
Important dates

Midterm exam: TBD

Final Exam: During exam session (exact date TBD)
Topics to be covered
A preliminary list of potential topics:

When and why does the basic Greedy algorithm work? Matroids. Also, matroid intersection.

Convex programming for discrete optimization: linear programming (extreme point structure, duality) and semidefinite programming.
 Approximation algorithms (tradeoff between time and solution quality).

Simplex method, ellipsoid method, gradient descent, and multiplicative weight update method.

Submodular function optimization: polynomial time minimization and approximate maximization.

Online algorithms (tradeoff between knowledge about future and solution quality).

Streaming algorithms (tradeoff between knowledge about future and solution quality).

Randomized algorithms (hashing, power of two choices, Karger's mincut algorithm).

Spectral graph theory (random walks, Cheeger's inequality)
Reading
The detailed schedule, lecture notes, and additional links to material will be available on the course
moodle:
http://moodle.epfl.ch/
Midterm and Final Exam
You are allowed to use a
hand written A4page on which you can write anything on both sides. (You are not allowed to look at it using a magnifying glass!)
Grading
The final grade will be based on two homeworks [30%], the midterm [30%], and the final exam [40%].