Course AC: Algorithms and Complexity

(LNMB, Fall 2023)

This basic course explains the basics of algorithms and complexity. It assumes only knowledge of basic mathematics (set and logic notation, linear algebra, proof by induction, probability theory, big-O notation).

LNMB page: https://www.lnmb.nl/pages/courses/phdcourses/AC2324.html

Lecturers: Paul Bouman (bouman@ese.eur.nl) and Tom van der Zanden  (T.vanderZanden@maastrichtuniversity.nl)

Acknowledgement: Much of the material used in this course was previously developed by Gerhard Woeginger, Jesper Nederlof and Marie Schmidt.

Exercises (four series)

(If you have questions, send the lecturer an email or ask on Monday)

Important: comments on the homework.

Exercise series Deadline PDF
First series 2-Oct-2023 PDF
Second series 16-Oct-2023 PDF (v2) PDF (old)
Third series 30-Oct-2023 PDF
Fourth series 13-Nov-2023 PDF

Note: For those lacking background in algorithms design, we recommend to (at least) browse through the first three chapters of ‘Introduction to Algorithms’ by Cormen, Leiserson, Rivest and Stein.

Summary of Lectures

Date Topic Slides Extras
11-Sep-2023 Introduction, basic concepts, P versus NP Lecture Graphs Turing Machines
18-Sep-2023 NP-complete problems Lecture Cook-Levin theorem
25-Sep-2023 Strong/ weak NP-hardness, co-NP Lecture
2-Oct-2023 Approximation algorithms Lecture
9-Oct-2023 More on approximation algorithms Lecture
16-Oct-2023 Exact algorithms for NP-hard problems Lecture Lecture notes
23-Oct-2023 More exact algorithms for NP-hard problems, Dynamic Programming Lecture Lecture notes
30-Oct-2023 Treewidth Lecture Lecture notes
6-Nov-2023 Randomized Algorithms Lecture
13-Nov-2023 No Lecture

Extra material