NWI-IBC028

# Complexity, Q4 2022

In this course, which is a follow-up to “Algorithms and Data Structures”, you'll first learn to analyse and describe the runtime and memory usage of a particular algorithm, its so-called time and space complexity. In the second part of the course you'll see that there are limits to the efficiency with which some problems can be solved, and will learn to categorize problems in complexity classes such as P, NP and PSPACE.
Lecturers:
<{nweide,awesterb}@cs.ru.nl>

## Material

1. Lecture slides (see table below),
2. Hans Zantema's lecture notes from 2019, and
3. the book Introduction to Algorithms, Third Edition by Cormen, Leiserson, Rivest and Stein.

## Examination

The course ends with a two-hour written exam. You can earn a modest bonus to the final grade by handing in solutions to the weekly exercises; the final grade is computed according to the following algorithm.
``````
a = average of the grades for the six assignments
b = grade for the exam

if b > 5 {
b += a / 10.0
b = min(10.0, b)
}

return round(b)
``````
Here `round(b)` is the greatest of the numbers nearest to `b` in `{1.0, 1.5, 2.0, ..., 9.5, 10.0}\{5.5}` (e.g., `round(7.2)=7`, `round(7.25)=7.5`, and `round(5.5)=6`.)

## Course schedule

• Sunday evenings: exercises for the coming week are made available;
• Mondays 15.30—17.15, lecture in room CC 3;
• Mondays 15.30: deadline for handing in previous weeks' exercises;
• Thursdays 8.30—10.15 tutorial (locations below).
week # lecture topics date tutorial exercises exercises due
15 #1, April 11, by Bram (slides) Refresher on the basics, Master theorem, mindist April 14 exercise set #1 (w/ solutions) April 18
16 (easter monday) April 21 exercise set #2 (w/ solutions) April 25
17 #2, April 25, by Bram (slides) Karatsuba multiplication, Master theorem, multiplication of polynomials using FFT April 28 exercise set #3 (w/ solutions) May 9
18 (meivakantie) (meivakantie)
19 #3, May 9, by Niels (slides) Complexity classes, NP-completeness May 12 exercise set #4 (w/ solutions) May 16
20 #4, May 16, by Niels (slides, Note on 3-colorings) Proving NP-completeness, examples of NP-complete problems May 19 exercise set #5 (w/ solutions) May 30
21 #5, May 23, by Niels (slides, Note on Hamiltonian paths) More NP-complete problems, Approximation Algorithms (ascension day)
22 #6, May 30, by Bram (slides) NP-completeness of SAT (Cook-Levin) June 2 exercise set #6 (w/ solutions) June 6
23 (whit monday) June 9 none
24
25 Exam June 24 exam, with solutions
previous exams from 2015, 2016, and 2021. Note: topics covered are slightly different.
28 Resit Exam July 13 resit exam, with solutions
Exercises will appear in the table above and solutions must be handed in via Brightspace in PDF.

## Tutorial sessions

Tutorials will be held in the following rooms.
room capacity staff
HG00.065 22 persons Thomas van Ouwerkerk
HG00.308 28 persons Jorrit de Boer
HG02.028 20 persons Todd Bellavia