IBC028 Complexity, Spring 2026

Teacher

Herman Geuvers: home page

Introduction

This course is a follow-up of "Algorithms and Data Structures". First techniques to compute the complexity of recursive algorithms will be presented, based on recurrences as they can be derived from the algorithms. In particular the Master Theorem will be discussed. Several applications are presented, in particular algorithms for matrices and a geometric algorithm. The remaining main part of the course is about decision problems and whether they are in P (polynomially solvable) or in NP (nom-deterministic polynomial). We will investigate a range of problems for which no polynomial algorithms are expected to exist. We give underlying theory, we prove NP-completeness for a wide range of problems and we discuss the well-known open problem whether P equals NP. At the end some basics of the next complexity class are presented: PSPACE.

Material

Weekly slides will appear on this webpage, plus sometimes weekly additional notes.
For reference we use: Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, Third Edition, 2009, abbreviated to CLRS below. (This same book was used in the course "Algorithms and Data Structures" before 2023/2024.)
The material of this course can also be found in Algorithms Illuminated, Tim Roughgarden, Cambridge University Press, Omnibus Edition September 2022, hardcover, 690pp.
Here are some lecture notes by Hans Zantema for a previous version of this course.

Examination

There is a 3hr written exam, on Wednesday June 10, 12:45-15:45. Apart from that there is the possibility to hand in weekly exercises that will be graded. The average of your exercise grade is added as a bonus to your written exam grade.

The final grade is computed as follows.
Let f be your written exam grade and let e be your exercise grade, which is the average of the 6 (weekly) exercise grades.

If f is 5 or higher, the final grade is the minimum of 10 and f + e/10.
If f is below 5, the final grade is f.

Old Exams (material may differ slighty): exam 2021 with answers, exam 2022 with answers, resit 2022 with answers.

Set up

The course consists of 2 hours lecture (hoorcollege) Monday, 13:30--15:30 in HG00.307 (except for week 15, then: Wednesday April 8, 8:30-11:15 in LIN6) plus "self study" and a weekly 2hr exercise class on Friday.

The lectures are recorded. These will be put on Brightspace.

The course is roughly organised as follows (but see the schedule below for details, especially when the handed in exercises are due):

Monday lunch time: exercises on the web page
Monday afternoon: Lecture
Friday: exercise class, students work on exercises
Tuesday: hand in exercises before 11:00 via Brightspace
Friday: explanation of exercises, grades on Brightspace.

Exercise classes

There are two exercise classes. In each class, there will be a number of TAs present to help you with the exercises and to explain the answers of the exercises of the previous week.

Friday 13:30-15:15, HG00.539
Friday 13:30-15:15, HG00.062

You can hand in exercises, which will be graded by a TA. Register for a TA group in Brightspace before the first exercise class. This TA will grade your work. Note: in case you are not in one of the TA groups, your work will not be graded. If you still want to be enrolled in one of the groups: please mail the teacher. We have the following TAs.

Vicentia Stroe
Alexandru Gavajuc
Martina Tebar Jimenez-Millas
Lukas Nieuweboer
Jasper Laumen
Stefan Roman
Siebe Hooghof
George Nadejde
Bregt van der Lugt

The course by week

The following is the weekly schedule. The content description and exercises are preliminary.

Year-week	Lecture	Date lect	Topics	Material	Date ex.class	Exercises: work on / discuss
15	1	Wed 8/4	General techniques, Fibonacci, depth AVL trees, Divide and conquer, Merge sort, Substitution Method	Slides, CLRS: Sections 3.1, 3.2; pp 65-67; Section 4.3; Sections 2.3.1, 2.3.2 for MergeSort. (Roughgarden: Sections 1.4 and 1.5 and Chapter 2.)	10/4	Work on Exercises 1, due Tuesday 14/4.

16	2	13/4	Recursion tree Method, examples: merge sort, median; Master Theorem	Slides lecture 2; pages 7-8 of lecture notes (CLRS: Chapter until 4.5 (page 96), but not 4.2 + pp 220-222. Roughgarden: Sections 1.5, 6.3-6.4 and 4.2.)	17/4	Work on Exercises 2, due Tuesday 21/4, discuss Exercises 1

17	3	20/4	Master Theorem, Karatsuba multiplication, Strassen algorithm, smallest distance in set of points	Slides lecture 3, pages 9-10 of lecture notes, (CLRS: Remainder Chapter 4, Chapter 33.4 (pp 1039-1043). Roughgarden: Sections 1.2, 1.3 and 3.3, 3.4 and 4.1, 4.2 and 4.3.)	24/4	Work on Exercises 3, due Tuesday 5/5, discuss Exercises 2

18			No lecture, May break	[No lecture this week]

19	4	4/5	P and NP, NP-hard, NP-complete	Slides lecture 4 and lecture notes, (CLRS: Chapter 34 until Fig 34.6, p. 1070, Roughgarden: 19.3 and 22.1, 22.2)	8/5	Work on Exercises 4, due Tuesday 19/5, discuss Exercises 3

20	5	11/5	NP-completeness: 3SAT, CNF-SAT, <=3-SAT, ILP, clique, vertex cover, 3-coloring	Slides lecture 5, extra note by Niels van de Weide on 3-coloring. (CLRS: Chapter 34 until page 1092)	No ex. class	Here is Exercises 5, due Tuesday 26/5

21	6	18/5	Clique-3Cover, Subset sum, TSP, the class PSPACE.	Slides lecture 6, lecture notes and the extra note by Niels van de Weide on Hamilton Path. (CLRS: Chapter 34.)	22/5	Work on Exercises 5 (see above) and Exercises 6, due Tuesday 2/6, discuss Exercises 4

22			No lecture, Pentecost, but there are exercise classes on Friday	[No lecture this week]	29/5	Work on Exercises 6 (see above) and discuss Exercises 5.

23	7	1/6	Cook-Levin Theorem: Proof that 3-SAT is NP-complete; course overview	Slides lecture 7, lecture notes and Wikipedia on the Cook-Levin Theorem, (CLRS: Chapter 34 until page 1085).)	5/6	Discuss Exercises 6 and old exams

herman at cs dot ru dot nl