# IBC028 Complexity, Spring 2020

## 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

• Additional lecture notes of this course (version from March 4, 2019)
• Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, Third Edition, 2009 The same book is used in "Algorithms and Data Structures".

## Examination

There is a 2hr written exam. Apart from that there will be 2 assignments you can hand in to get a "bonus".

There will be two moments in the course when homework exercises may be handed in. You are very strongly suggested to do so: these will be graded and commented. The average of your 2 homework grades, divided by 10 is your "bonus".

## Set up

The course consists of 2 hours lecture (hoorcollege) Tuesday, 13:30--15:15, plus "self study" and an exercise class (werkcollege) on Friday, 8:30-10:15 .

An exception to this schedule is the "carnaval week" (week 9): Tuesday is lecture-free, so the lecture will be on Friday 28/2, 8:30-10:15 and there will be no exercise class.

## Exercise classes

1. Eline Bovy, (E.Bovy@student.ru.nl) HG00.062, studentnr = 0 (mod 6)
2. Bas Hofmans, (b.hofmans@student.ru.nl) HFML0220, studentnr = 1 (mod 6)
3. Thomas van Ouwerkerk, (T.vanOuwerkerk@student.ru.nl) HG00.310, studentnr = 2 (mod 6)
4. Lars van Rhijn, (L.vanRhijn@student.ru.nl) HG01.028, studentnr = 3 (mod 6)
5. Gijs Hendriksen (gijs.hendriksen@student.ru.nl) HG03.054, studentnr = 4 (mod 6)
6. Deivid Rodrigues do Vale, (deividvale@cs.ru.nl) HG00.068, studentnr = 5 (mod 6)

## The course by week

The following is the weekly schedule. The content description and exercises are preliminary. See the schedule (rooster) for the most up to date information on the lecture room.
Year-week Order Date and Location Topics Material Exercises
6 1 4/2, LIN 1 General techniques, Fibonacci, depth AVL trees, Divide and conquer, merge sort Slides lecture1, 19.4 (pp 523-525), first 6.5 pages of lecture notes Ex. 4.3-3, 4.3-6 (page 87) and extra exercises,
7 2 11/2, LIN 1 Master Theorem, examples: merge sort, median Slides lecture2, pages 7-8 of lecture notes, Chapter until 4.5 (page 96), but not 4.2 + pp 220-222 Ex. 4.4-1, 4.4-2, 4.4-3, 4.4-4 (pp 92-93), 4.5-1, 4.5-3 (pp 96-97)
8 3 18/2, LIN 1 Karatsuba multiplication, Strassen algorithm, proof sketch Master Theorem, smallest distance in set of points Slides lecture3, pages 9-10 of lecture notes, Remainder Chapter 4, Chapter 33.4 (pp 1039-1043) 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). See also Assignment 1, which can be handed in by 28/2
9 4 28/2, HG00.307 P and NP, NP-hard, NP-complete Slides lecture4, Chapter 34 until Fig 34.6, p. 1070, also see lecture notes Assignment 1 can be handed in on 28/2, in the delivery box of your TA in front of room M1.07A. Deadline: 11:00 AM. Here are the solutions to Assignment 1
10 5 3/3, LIN 1 Cook-Levin Theorem, NP-complete problems: CNF-SAT, <=3-SAT [No slides this week] Chapter 34 until page 1085, also see lecture notes and Wikipedia on the Cook-Levin Theorem 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)
11 6 10/3, LIN 1 NP-completeness: 3SAT, ILP, clique, vertex cover, 3-coloring Slides lecture5,Chapter 34 until page 1092 Ex. 34-1 and 34-2 (pp 1101-1102). See also Assignment 2, which can be handed in by 20/3
12 7 17/3, LIN 1 Clique-3Cover, Subset sum, the class PSPACE, course overview Slides lecture6, see lecture notes and see below for the web-lectures for lecture 7. Assignment 2 can be handed in on 20/3. Please send your assignment by mail to your TA! Here are the solutions to Assignment 2
14 30/3, HAL 2 12:45--14:45, EXAM Old exams (in Dutch) with solutions: June 23, 2015 and June 28, 2016. Note the topics covered are slightly different and these are "closed book" exams.
28 8/7, MERC I 00.28 12:45--14:45, resit EXAM

## Web-lectures for the lecture of week 12 (lecture 7)

Because of the COVID-19 virus outbreak, all lectures at the university have been suspended. Therefore, I have made some "home made" web-lectures for Lecture 7.

herman at cs dot ru dot nl