This is a graduate-level course on algorithm design (and analysis). It covers a range of topics and techniques in approximation algorithms, sketching and streaming algorithms, and online algorithms.
Learning objective
This course familiarizes the students with some of the main tools and techniques in modern subareas of algorithm design.
Content
The lectures will cover modern topics in algorithm design and analysis, 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 recommended, though not required formally. If you are not sure whether you're ready for this class or not, please consult the instructor.
Competencies
Subject-specific Competencies
Concepts and Theories
fostered
Method-specific Competencies
Analytical Competencies
fostered
Decision-making
fostered
Problem-solving
fostered
Performance assessment
Performance assessment information (valid until the course unit is held again)
The performance assessment is only offered at the end after the course unit. Repetition only possible after re-enrolling.
Mode of examination
written 180 minutes
Additional information on mode of examination
This course has a final exam (3 hours, open book, 60% of the final grade) plus two graded homework (20% each). The two mandatory graded homework (compulsory continuous performance assessments) will be released throughout the semester, in specific dates that will be announced. Each graded homework will have a deadline two weeks after the release. The solutions must be typeset in LaTeX (or similar). These solutions will be graded and the grade for each GHW accounts for 20% of the final grade.
Written aids
open book: you are permitted to consult any books, handouts, and personal notes. The use of electronic devices is not allowed.
Performance assessment as a semester course