Information about the course Complexiteit (IBC028), spring 2019

Teacher (lectures on Tuesday 13:30-15:15 in HG00.304):
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:30-12:15):

Group 1: Lars van Rhijn, email: larsvanrhijn@gmail.com, exercise session in HG00.065
Group 2: Timo Maarse, email: timo.maarse@gmail.com, exercise session in HG 00.086
Group 3: Gijs Hendriksen, email: gijs.hendriksen@student.ru.nl, exercise session in HG 00.310
Group 4: Bas Hofmans, email: b.hofmans@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
January 29 General techniques, Fibonacci, depth AVL trees 19.4 (pp 523-525), first 5 pages of lecture notes extra exercises, 4.3:3,6 (page 87)
February 5 Divide and conquer, Master Theorem, examples: merge sort, median 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 12 Karatsuba multiplication, Strassen algorithm, proof sketch Master Theorem, smallest distance in set of points Remainder Chapter 4, Chapter 33.4 (pp 1039-1043 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)
February 19 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
February 26 Cook-Levin Theorem, NP-complete problems: 3SAT, ILP Chapter 34 until page 1085
March 5 No lecture
March 12 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 19 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 February 15, March 1 and March 15 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 the exercise session on February 15, 2019, no later than 11:00 AM

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

Examination of July 11, 2018

Last change: February 13, 2019