Information about the course Complexiteit (IBC028), spring 2017

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

Teachers (exercise sessions on Thursday 8:45-10:30):

Group 1: Guillome Allais, MSc, email: gallais@cs.ru.nl, exercise session in HG00.065
Group 2: Dr Michiel de Bondt, email: m.debondt@math.ru.nl, exercise session in HG 00.308
Group 3: Rick Erkens, email: rjarickerkens@gmail.com, exercise session in HG 00.310
Group 4: Tom van Bussel, email: tom.van.bussel@student.ru.nl, exercise session in HG 00.633

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 April 10, 2017)

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
April 11 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)
April 18 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)
May 2 No lecture
May 9 Strassen algorithm, Master Theorem Remainder Chapter 4 problems 4-1, 4-3 (pp 107-108), 4.2-1, 4.2-7 (pp 82-83), 28.2-1 (pp 831)
May 16 Computational geometry: smallest distance in set of points, P and NP Chapter 33.4 (pp 1039-1043), start Chapter 34 33.4:3,4,6; 34.3:2,3
May 23 SAT, NP-completeness: Cook-Levin Theorem Chapter 34, also see lecture notes and http://en.wikipedia.org/wiki/Cook-Levin_theorem 34.2:2,4,5; 34.4:5,6(,7)
May 30 NP-complete problems: ILP, clique Chapter 34 until page 1089
June 6 NP-completeness: vertex cover, 3-coloring, subset sum, Mahjong problem 34-3 (pp 1103-1104), 34.5.5 (pp 1097-1101) 34.5: 4,5, problems 34-1 en 34-2 (pp 1101-1102)
June 13 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 May 4 and June 8 and at the lecture of May 23 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 May 4, 2017

Second set of homework exercises, to be handed in on May 23, 2017

Third and last set of homework exercises, to be handed in on June 8, 2017

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

Last change: June 14, 2017