From 2 November 2020, the autumn semester 2020 will take place online. Exceptions: Courses that can only be carried out with on-site presence.
Please note the information provided by the lecturers via e-mail.

263-4500-10L  Advanced Algorithms (with Project)

SemesterAutumn Semester 2018
LecturersM. Ghaffari, A. Krause
Periodicityyearly recurring course
Language of instructionEnglish
CommentOnly for Data Science MSc.

Catalogue data

AbstractThis 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.
ObjectiveThis 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.
Contentthe 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, and a bried glance at MapReduce algorithms.
Prerequisites / NoticeThis 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 consulte the instructor.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits8 credits
ExaminersA. Krause, M. Ghaffari
Typesession examination
Language of examinationEnglish
RepetitionThe performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examinationwritten 180 minutes
Additional information on mode of examinationOne project (compulsory continuous performance assessment) will contribute 25% to the final grade.

Three graded exercises (compulsory continuous performance assessments) will together contribute 25% to the final grade. We will hand out three specially marked exercises, whose solutions (typeset in LaTeX or similar) are due two weeks later in each case. These three solutions will be graded and will contribute equally to the final grade.

Written exam (180 min) accounting for 50% of the final grade;
Written aidsopen 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.

Learning materials

Main linkInformation
Only public learning materials are listed.


263-4500-00 VAdvanced Algorithms2 hrs
Tue10-12CAB G 61 »
M. Ghaffari, A. Krause
263-4500-00 UAdvanced Algorithms2 hrs
Fri10-12CAB G 59 »
M. Ghaffari, A. Krause
263-4500-10 PAdvanced Algorithms2 hrsA. Krause
263-4500-00 AAdvanced Algorithms1 hrsM. Ghaffari, A. Krause


No information on groups available.


PriorityRegistration for the course unit is only possible for the primary target group
Primary target groupData Science MSc (261000)

Offered in

Data Science MasterData ManagementWInformation