IBC028 Complexity, Spring 2021

Teachers

Herman Geuvers: home page
Hans Zantema: 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 huge matrices and geometric algorithms. The remaining main part of the course is about NP-completeness: investigating a wide range of algorithmic decision problems for which no polynomial algorithms are expected to exist. We give underlying theory and will prove NP-completeness for a wide range of problems, by which they are essentially equivalent. At the end some basics of the next complexity class are presented: PSPACE.

Material

Examination

There is a 2hr written exam, which will be on campus (so not online!). Apart from that there will be 2 assignments you can hand in to get a "bonus". So there are two moments in the course when homework exercises may be handed in, as assignment. You are very strongly suggested to do so: these will be graded and commented.

The final grade is the minimum of 10 and f + a/10, where f is your written exam grade and a is your assignment grade.

Set up

The course consists of 2 hours lecture (hoorcollege) Monday, 15:45--17:30, plus "self study" and an exercise class (werkcollege) on Wednesday, 8:30--10:15 or 10:30--12:15, depending on your exercise group.
NB. The "persoonlijke rooster" page sometimes mentions 15:30 as starting time of the lecture and sometimes 15:45. For clarity, we will always start at 15:45.

Exceptions to this schedule are:

The recordings of all lectures can be found on brightspace .

Exercise classes

Check in brightspace in which class you are.
  1. 08:30--10:15, Els Hoekstra (3ls.hoekstra@gmail.com)
  2. 08:30--10:15, Jorrit de Boer (jorrit.deboer@student.ru.nl)
  3. 08:30--10:15, Thomas van Ouwerkerk (T.vanOuwerkerk@student.ru.nl)
  4. 10:30--12:15, Ruben Holubek (r.holubek@student.ru.nl)
  5. 10:30--12:15, Jana Wagemaker (jana.wagemaker@ru.nl)
  6. 10:30--12:15, Deivid Rodrigues do Vale, (D.Vale@cs.ru.nl)

The course by week

The following is the weekly schedule. The content description and exercises are preliminary. You can consult the schedule (rooster), but that lists only on-campus activities. In fact, only from May 10 onwards, lectures will be on-campus.
Year-week Lecture Date lect Topics Material Date ex.class Exercises
14 1 6/4 General techniques, Fibonacci, depth AVL trees, Divide and conquer, merge sort Slides lecture 1 (see recording and annotated slides on brightspace ), 19.4 (pp 523-525), first 6.5 pages of lecture notes 7/4 Ex. 4.3-3, 4.3-6 (page 87) and extra exercises. To be discussed on 15/4
15 2 12/4 Master Theorem, examples: merge sort, median Slides lecture 2 (see recording and annotated slides on brightspace ), pages 7-8 of lecture notes, Chapter until 4.5 (page 96), but not 4.2 + pp 220-222 15/4 Ex. 4.4-2, 4.4-3, 4.4-4, 4.4-5 (pp 92-93), 4.5-1, 4.5-3 (pp 96-97). To be discussed on 22/4
16 3 19/4 Karatsuba multiplication, Strassen algorithm, proof sketch Master Theorem, smallest distance in set of points Slides lecture 3 (see recording and annotated slides on brightspace ), pages 9-10 of lecture notes, Remainder Chapter 4, Chapter 33.4 (pp 1039-1043) 22/4 Ex. 4-1, 4-3 (pp 107-108), 4.2-1, 4.2-7 (pp 82-83), 28.2-1 (pp 831), 33.4-3, 33.4-4, 33.4-6 (pp 1044). To be discussed on 29/4
17 4 26/4 P and NP, NP-hard, NP-complete Slides lecture 4 (see recording and annotated slides on brightspace ), Chapter 34 until Fig 34.6, p. 1070, also see lecture notes 29/4 Assignment 1 can be found on brightspace , to be handed in on 10/5, also via brightspace: Deadline: 11:00 AM on 10/5.
19 5 10/5 NP-completeness: 3SAT, CNF-SAT, <=3-SAT, ILP, clique, vertex cover, 3-coloring Slides lecture 5 (see recording and annotated slides on brightspace ), Chapter 34 until page 1092 13/5 Extra exercise and Ex. 34-1 and 34-2 (pp 1101-1102). To be discussed on 20/5
20 6 17/5 Clique-3Cover, Subset sum, the class PSPACE. Slides lecture 6, see lecture notes 20/5 Ex. 34.2-1, 34.2-4, 34.2-5 (p 1066); 34.3-3, 34.3-6 (p 1077); 34.4-6 (p 1086). To be discussed on 27/5
21 No lecture, but there is an exercise class on Wednesday 26/5 [No lecture this week] 27/5 Assignment 2 can be handed in on 1/6, electronically to your TA. Deadline 11:00 AM, 1/6
22 7 31/5 Cook-Levin Theorem: Proof that 3-SAT is NP-complete; course overview [No slides this week?] Chapter 34 until page 1085, also see lecture notes and Wikipedia on the Cook-Levin Theorem 2/6 Answers to Assignment 2.
25 21/6 8:30--10:30, EXAM (in de Vereeniging!) Old exams (in Dutch) with solutions: June 23, 2015 and June 28, 2016. Note the topics covered are slightly different. Old exam of March 30, 2020, but note that this was an online "open book" exam.
28 13/7 8:30--10:30, resit EXAM (on campus, in HG)


herman at cs dot ru dot nl