This course is a follow-up of "Algorithms and Data Structures". 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.
There is a 3hr written exam, on Friday June 21, 8:30-11:30. Apart from that there is the possibility to hand in weekly exercises that will be graded. The avarge of your exercise grade is added as a bonus to your written exam grade.
The final grade is computed as follows.
Let f be your written exam grade and let e
be your exercise grade, which is is the average of the 6 (weekly)
exercise grades.
Old Exams (material may differ slighty): exam 2021 with answers, exam 2022 with answers, resit 2022 with answers.
The course consists of 2 hours lecture (hoorcollege) Monday, 13:30--15:30 in HG00.307 (except for week 15, then: Monday April 8, 15:30-17:15 in LIN6) plus "self study" and a weekly 2hr exercise class on Friday.
The lectures are not recorded .
The course is roughly organised as follows (but see the schedule below for details, especially when the handed in exercises are due):
| Year-week | Lecture | Date lect | Topics | Material | Date ex.class | Exercises: work on / discuss |
|---|---|---|---|---|---|---|
| 15 | 1 | 8/4 15:30-17:15 | General techniques, Fibonacci, depth AVL trees, Divide and conquer, Merge sort, Substitution Method | Slides lecture 1; first 6.5 pages of lecture notes. (CLRS: pp 65-67 and Section 4.3, pp 83-87. Roughgarden: Sections 1.4 and 1.5 and Chapter 2.) | 12/4 | Work on Exercises 1, due 15/4. |
| 16 | 2 | 15/4 | Recursion tree Method, examples: merge sort, median; Master Theorem | Slides lecture 2; pages 7-8 of lecture notes ((CLRS: Chapter until 4.5 (page 96), but not 4.2 + pp 220-222. Roughgarden: Sections 1.5, 6.3-6.4 and 4.2.) | 19/4 | Work on Exercises 2, due 22/4, discuss Exercises 1 |
| 17 | 3 | 22/4 | Master Theorem, Karatsuba multiplication, Strassen algorithm, smallest distance in set of points | Slides lecture 3, pages 9-10 of lecture notes, Remainder Chapter 4, Chapter 33.4 (pp 1039-1043) | 26/4 | Work on Exercises 3, due 29/4, discuss Exercises 2 |
| 18 | No lecture, May break | [No lecture this week] | ||||
| 19 | 4 | 6/5 | P and NP, NP-hard, NP-complete | Slides lecture 4, Chapter 34 until Fig 34.6, p. 1070, also see lecture notes. | no exercise class | |
| 20 | 5 | 13/5 | NP-completeness: 3SAT, CNF-SAT, <=3-SAT, ILP, clique, vertex cover, 3-coloring | Slides lecture 5, Chapter 34 until page 1092, extra note by Niels van de Weide on 3-coloring | 17/5 | Work on Exercises 4, due 21/5, discuss Exercises 3 |
| 21 | No lecture (Pentecoast), but there are exercise classes on Friday | [No lecture this week] | 24/5 | Work on Exercises 5, due 27/5, discuss Exercises 4 | ||
| 22 | 6 | 27/5 | Clique-3Cover, Subset sum, TSP, the class PSPACE. | Slides lecture 6, Chapter 34 and lecture notes and the extra note by Niels van de Weide on Hamilton Path. | 31/5 | Work on Exercises 6, due 3/6, discuss Exercises 5. |
| 23 | 7 | 3/6 | Cook-Levin Theorem: Proof that 3-SAT is NP-complete; course overview | Slides lecture 7, Chapter 34 until page 1085, lecture notes and Wikipedia on the Cook-Levin Theorem | 7/6 | Discuss Exercises 6 |