Information about the course Complexiteit (IBC028), spring 2016

Teacher (lectures on Tuesday 10:45-12:30 in HG0.071):
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 10:45-12:30):

Guillome Allais, MSc, email: gallais@cs.ru.nl, exercise session in HFML0220
Dr Michiel de Bondt, email: m.debondt@math.ru.nl, exercise session in HG 00.308
Rick Erkens, email: rjarickerkens@gmail.com, exercise session in HG 00.310

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.
Next some more algorithm are presented, in particular 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.


Literature:
Additional lecture notes of this course

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 12 General techniques, Fibonacci, depth AVL trees, divide and conquer 19.4 (pp 523-525), 4.1 (pp 65-74), 4.3 (pp 83-86) extra exercises, 4.3:2,3,6 (page 87), 4.4:4 (pp 92/93)
April 19 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)
April 26 Strassen algorithm, Master Theorem, intro computational geometry Remainder Chapter 4 problems 4-1 en 4-3 (pp 107-108)
May 10 Computational geometry: intersection of segments, convex hull Chapter 33 33.2:1,3,4,5 (page 1028); 33.3:1,2,3 (page 1038)
May 17 Computational geometry: smallest distance in set of points, P and NP Chapter 33, start Chapter 34 33.4:2,3,4,6; 34.3:2,3
May 24 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 31 NP-complete problems: ILP, clique, vertex cover, 3-coloring Chapter 34 until page 1091 + problem 34-3 (pp 1103-1104)
June 7 NP-completeness: subset sum, Mahjong, course overview 34.5.5 (pp 1097-1101) 34.5: 4,5, problems 34-1 en 34-2 (pp 1101-1102)
June 14 Opportunity to ask questions (vragenuur)


Examination
At the written examination no books or notes are allowed (closed book). Apart from that at the exercise sessions of April 28, May 19 and June 2 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-525), 9.3 (pp 220-222), Chapters 4, 33 en 34, except pp 103-105 and pp 1092-1096.


Exercises:

First set of homework exercises, to be handed in on April 28, 2016

Second set of homework exercises, to be handed in on May 19, 2016

Third and last set of homework exercises, to be handed in on June 2, 2016

Examination of June 23, 2015

Elaborated examination of June 23, 2015

Examination of August 13, 2015

Elaborated examination of June 28, 2016

Last change: June 30, 2016