Course AC: Algorithms and Complexity

Time:	Monday 13.15–15.00
Period:	8 September 2025 – 10 November 2025
Location:	All LNMB courses take place on the Campus Utrecht Science Park. Room HFG 611, Hans-Freudenthal building, Budapestlaan 6, 3584 CD Utrecht
Lecturers:	Dr. P. Bouman (EUR), Dr. T. van der Zanden (UM)

Course description

Principles for construction of algorithms: Decomposition, greedy algorithms, dynamic programming. Algorithm analysis. Probabilistic algorithms. Approximation. Selected applications to sets, graphs, and geometry. Exponential time algorithms and Fixed Parameter Tractability.

Complexity Theory: Reductions. Complexity classes P (polynomial time), NP (non-deterministic polynomial time). NP-complete problems.

Literature

Most material will be provided on the website. Additionally, for parts of the course it may be useful to buy the book
`Introduction to Algorithms', by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.

Website: https://tomvanderzanden.nl/LNMB-AC/

Prerequisites

Knowledge of basic mathematics (set and logic notation, linear algebra, proof by induction, probability theory, big-O notation)

Examination

Homework

Address of the lecturers

Dr. P. Bouman
Erasmus School of Economics, Erasmus University Rotterdam
Burgemeester Oudlaan 50, 3062 PA Rotterdam
E-mail: bouman@ese.eur.nl

Dr. T. van der Zanden
Dept. Data Analytics and Digitalisation
Maastricht University
E-mail: T.vanderZanden@maastrichtuniversity.nl