Advanced Algorithms

Course goals

After completing this course, the student will have:

• knowledge of important combinatorial algorithms and advanced algorithmic techniques;
• the ability to model problems from applications mathematically (e.g., as graph problems);
• the ability to apply algorithmic techniques to solve these problems;
• the ability to design combinatorial algorithms;
• the ability to prove correctness of algorithms;
• the ability to analyze the running time of complex algorithms.
• have an overview of various algorithmic research directions in theoretical computer science
• the ability to work with continuous models of computation and prove lower bounds in this regime

Assessment
There are a number (approximately 14) of exercises, and two exams.

• The exercises contribute 20% of the final grade. Students get points for submission during the tutorial and participation in peer-feedback.
• The midterm and final exams each count for 40% of the final grade. Approximately 30% of each exam consists of open pool questions, the rest consist of surprise questions. The open pool questions are given to students before the exam.

In order to pass the course, you need:

• an average grade of at least 5.5.
• an average of at least 5.0 for the exams.

To qualify for a repair of the final result the mark needs to be at least a 4, or “AANV”.

Content

This course explores advanced techniques for efficient algorithm design, with a focus on combinatorial problems. Networks (graphs) are used as a primary theoretical model for both practical applications and theoretical study. Topics include classical combinatorial problems such as packing, covering, knapsack, subset sum, and scheduling problems.

The course is divided into two parts:

• Part 1: Fundamental algorithms with practical and theoretical importance, including (stable) matchings, advanced algorithms for maximum flow/minimum cut, minimum cost flows, Euler tours, planar graphs.
• Part 2: Broader algorithmic topics, including fixed-parameter tractability, treewidth, exact exponential-time algorithms, approximation algorithms, and the existential theory of the reals.

Course form
Lectures and tutorials. Each lecture is accompanied by homework exercises (which may be part of the open exam pool. Students have one week to complete the homework.