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.

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.

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".

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 |

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.

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