This is an advanced course on the design and analysis of algorithms, covering a range of topics and techniques not studied in typical introductory courses on algorithms.
Objective
This course is intended to familiarize students with (some of) the main tools and techniques developed over the last 15-20 years in algorithm design, which are by now among the key ingredients used in developing efficient algorithms.
Content
The lectures will cover a range of topics, including the following: graph sparsifications while preserving cuts or distances, various approximation algorithms techniques and concepts, metric embeddings and probabilistic tree embeddings, online algorithms, multiplicative weight updates, streaming algorithms, sketching algorithms.
This course is designed for masters and doctoral students and it especially targets those interested in theoretical computer science, but it should also be accessible to last-year bachelor students.
Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Concentrations. E.g., having passed the course Algorithms, Probability, and Computing (APC) is highly recommended, though not required formally. If you are not sure whether you're ready for this class or not, please consult the instructor.
Performance assessment
Performance assessment information (valid until the course unit is held again)
The performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examination
written 180 minutes
Additional information on mode of examination
There are three mandatory sets of exercise (compulsory continous performance assessments), the answer keys (typeset in LaTeX or similar) are due two weeks later. These solutions will be graded; the grades will each account for 10% of the final grade.
Written exam (180 min) accounting for 70% of the grade;
Written aids
open book: you are permitted to consult any books, handouts, and personal notes. The use of electronic devices is not allowed.
This information can be updated until the beginning of the semester; information on the examination timetable is binding.