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 2hr written exam, on Thursday June 22, 8:30-10: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 the minimum of 10 and f + e/10, where f is your written exam grade and e is your exercise grade, and e is the average of the 6 (weekly) exercise grades.
The course consists of 2 hours lecture (hoorcollege) Monday, 10:30--12:15 in CC2 (except for week 15, then: Wednesday April 12, 13:30-15:15 in LIN3) plus "self study" and a weekly 2hr exercise class.
The course is organised as follows (except for the first week, week 15):
| Year-week | Lecture | Date lect | Topics | Material | Date ex.class | Exercises: work on / discuss |
|---|---|---|---|---|---|---|
| 15 | 1 | 12/4 | General techniques, Fibonacci, depth AVL trees, Divide and conquer, Merge sort, Substitution Method | Slides lecture 1; pp 65-67 and Section 4.3, pp 83-87 of CLRS; first 6.5 pages of lecture notes. | 13/4, 14/4 | Exercises 1. |
| 16 | 2 | 17/4 | Recursion tree Method, examples: merge sort, median; Master Theorem | Slides lecture 2; pages 7-8 of lecture notes, Chapter until 4.5 (page 96), but not 4.2 + pp 220-222 | 19/4, 20/4 | Exercises 2. |
| 17 | 3 | 24/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 | Exercises 3. |
| 18 | No lecture, May break | [No lecture this week] | ||||
| 19 | 4 | 8/5 | P and NP, NP-hard, NP-complete | Slides lecture 4, Chapter 34 until Fig 34.6, p. 1070, also see lecture notes. | 10/5, 11/5 | Exercises 4. |
| 20 | 5 | 15/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 | Exercises 5. |
| 21 | 6 | 22/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. | 24/5, 25/5 | Exercises 6. |
| 22 | No lecture, but there are exercise classes on Wednesday and Thursday | [No lecture this week] | 31/5, 1/6 | Exercises 6 | ||
| 23 | 7 | 5/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, 8/6 | Old Exams (material may differ slighty): exam 2021 with answers, exam 2022 with answers, resit 2022 with answers |