Information about the course Complexiteit (IBC028), spring 2018

Teacher (lectures on Tuesday 10:45-12:30 in LIN 5):
Prof Dr Hans Zantema,
Mercator 1, room 1.16 (only on Tuesday),
tel 040-2472749 (except for Tuesday),
email: h.zantema@tue.nl

Teachers (exercise sessions on Friday 10:45-12:30):

Group 1: Guillome Allais, MSc, email: gallais@cs.ru.nl, exercise session in HG00.065, until March 2. From March 9 on, students of this group are asked to ditribute over the other groups.
Group 2: Tom van Bussel, email: tom.van.bussel@student.ru.nl, exercise session in HG 00.086
Group 3: Gijs Hendriksen, email: gijs.hendriksen@student.ru.nl, exercise session in HG 00.310
Group 4: Jan Martens, email: j.martens@student.ru.nl, exercise session in HG 01.028

To decide in which group you are: take (the last two digits of) your student number, compute modulo 4 and add 1. So if your number is divisible by 4, you are in group 1, if it is 1 mod 4, your are in group 2, and so on.

Topics:

This course is a follow-up of "Algoritmen en Datastructuren".
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.

Literature:
Additional lecture notes of this course
(version from March 14, 2018)

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 "Algoritmen en Datastructuren".


Lectures and topics:
date topic book exercises
February 6 General techniques, Fibonacci, depth AVL trees 19.4 (pp 523-525), first 5 pages of lecture notes extra exercises, 4.3:2,3,6 (page 87)
February 13 No lecture
February 20 Divide and conquer, Master Theorem, examples: median, Karatsuba multiplication Chapter 4 until 4.5 (page 96) + pp 220-222 4.4:1,2,3,4 (pp 92-93), 4.5:1,3 (pp 96-97)
February 27 Strassen algorithm, smallest distance in set of points, P and NP Remainder Chapter 4, Chapter 33.4 (pp 1039-1043), start Chapter 34 problems 4-1, 4-3 (pp 107-108), 4.2-1, 4.2-7 (pp 82-83), 28.2-1 (pp 831), 33.4:3,4,6 (pp 1044)
March 6 P and NP, SAT, NP-completeness: Cook-Levin Theorem Chapter 34, also see lecture notes and http://en.wikipedia.org/wiki/Cook-Levin_theorem 34.2:4,5; 34.3:2,3; 34.4:6
March 13 Cook-Levin Theorem, NP-complete problems: 3SAT, ILP Chapter 34 until page 1085
March 20 NP-completeness: clique, vertex cover, 3-coloring, subset sum Rest Chapter 34, except pp 1092-1096 34.5: 4,5, problems 34-1 en 34-2 (pp 1101-1102)
March 27 Mahjong, the class PSPACE, course overview see lecture notes


Examination
At the written examination no books or notes are allowed (closed book). Apart from that at the exercise sessions of March 2 and March 16 homework exercises may be handed in. These will be graded and commented; if they are done well maximally one point extra may be obtained for the examination.

The material for the examination:
The lecture notes, plus from the book: 19.4 (pp 523-524), 9.3 (pp 220-222), Chapter 4, 33.4 (pp 1039-1043), and Chapter 34, except pp 1070-1077,1080-1081 (replaced by Turing machine based proof in lecture notes) and pp 1092-1096.


Exercises:

First set of homework exercises, to be handed in on March 2, 2018

Second set of homework exercises, to be handed in on March 16, 2018

Examination of June 23, 2015

Elaborated examination of June 23, 2015

Examination of August 13, 2015

Elaborated examination of June 28, 2016

Examination of August 25, 2016

Examination of June 28, 2017

Examination of August 23, 2017

Examination of April 5, 2018

Last change: April 17, 2018