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:
Niels van der Weide & Bram Westerbaan
<{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

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
HG02.032 21 persons Nadezhda Dobreva
HG02.052 22 persons Ruben Turkenburg (grading by Denise Verbakel)
HG03.085 20 persons Niek Terol
Transitorium 00.012 (April 21: HG02.052) 35 persons Deivid Vale (grading by Denise Verbakel)

To prevent overflowing rooms, please register which group you'd like to attend via Brightspace as soon as possible, but at least before April 15. If you do not register, the solutions you submit to Brightspace won't be graded!

We may assign you to a different group when a room's capacity has been exceeded, or to more equally divide the work among the teaching assistants.

Discord server

We have created a discord server for you to discuss this course with your fellow students that you may join by following this link.

Note that your TA might not check the discord server, so it's best to put any questions you might have for them to them in person during the tutorial sessions.