Advanced Algorithms (CS 627) is a specialization module (Vertiefungsmodul) covering algorithmic techniques for working with computationally hard problems as well as complementing impossibility results from complexity theory.

Planned Content

  • Approximation Algorithms
  • Parametrized and Exact Algorithms
  • Randomized Algorithms
  • Linear Programming, Primal-Dual Algorithms
  • Complexity Theory

Slido  ⋅  YouTube  ⋅  ILIAS  ⋅  Campuswire  ⋅  Units

Lectures

There will be synchronous interactive lectures, starting from October 12. Live participation is expected; lectures are live-streamed on YouTube (YouTube Channel) on a best-effort basis.

You can find lecture slots and rooms in Marvin.
Note: Times in Marvin are c.t. (We start 15min past the full hour).

Units

The module will consist of the following units; each has unit subpage linked in the table with slides, lecture notes, and video recordings for that unit.

Week w/c (Mon) Lecture Units Exercises
1 2026-10-12 Unit 0: Administrativa  
    Unit 1: Motivation  
2 2026-10-19 Unit 2: Complexity Theory Recap Sheet 01
3 2026-10-26 Unit 2: Complexity Theory Recap Sheet 02
4 2026-11-02 Unit 3: Pseudopolynomial Algorithms Sheet 03
    Unit 4: Fixed-parameter Algorithms Sheet 04
5 2026-11-09 Unit 5: Parameterized Hardness Sheet 05
6 2026-11-16 Unit 6: Advanced Parameterized Concepts Sheet 06
7 2026-11-23 Unit 7: Randomization Basics Sheet 07
8 2026-11-30 Unit 7: Randomization Basics Sheet 08
9 2026-12-07 Unit 8: Randomized Complexity Sheet 09
10 2026-12-14 Unit 9: Random Tricks Sheet 10
— 2026-12-21 Xmas break —
— 2026-12-28 Xmas break —
— 2027-01-04 Xmas break —
11 2027-01-11 Unit 10: Approximation Algorithms Sheet 11
12 2027-01-18 Unit 11: Linear Programming Sheet 12
13 2027-01-25 Unit 12: Inapproximability  
14 2027-02-01 Bonus: Research Talk, Q&A  

Tutorials (Übungen)

There will be exercises, required for admission to the exam. Details will be given in class.

Tutorial times and rooms: see the Marvin entry for the tutorials.

Online Tools

We will use several tools and services that have proven effective for this module.

Campuswire

Campuswire is our main online communication channel.
Any questions relating to the module should be posted on Campuswire on the question & answer forum, the “class feed”.
You can post anonymously if you prefer, and you are strongly encouraged to answer each other’s questions, as well!

You can also use the platform for (social or topical) discussions in the chat rooms.

ILIAS

We will use the university’s official learning management system ILIAS for announcements and examination-related information.

Slido

During the live lectures, I will use Slido to for interactive parts.

We maintain a collaborative exam question gallery.

Join us in making this a great resource for preparation for the exam – and if your questions are good enough, they might end up getting asked!

Exam & Assessment

The module mark is based on the final examination. To be admitted to the exam, you must achieve a passing grade in the tutorials.

More details will be given in class.

Further reading

The module does not follow a single specific textbook, but rather combines parts from several sources; the unit subpages give more details on the specific sources used in each unit.

  • J. Hromkovic: Algorithmics for Hard Problems
    overview, covers many of the same examples
  • S. Arora and B. Barak: Computational Complexity: A Modern Approach
    reference for the complexity theory parts
  • M. Cygan et al.: Parameterized Algorithms
    reference for the parameterized algorithms parts
  • V. Vazirani: Approximation Algorithms
    reference for the approximation algorithms parts
  • R. Motwani and P. Raghavan: Randomized Algorithms
    reference for the randomized parts

Large parts of this module are based on lectures I taught a while ago. Recordings are available below. These give a good idea for the content of the module, but note that parts of the material is different.

Other resources