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 matrices and a geometric algorithm. The remaining main part of the course is about decision problems and whether they are in P (polynomially solvable) or in NP (nom-deterministic polynomial). We will investigate a range of problems for which no polynomial algorithms are expected to exist. We give underlying theory, we prove NP-completeness for a wide range of problems and we discuss the well-known open problem whether P equals NP. At the end some basics of the next complexity class are presented: PSPACE.
There is a 3hr written exam, on Monday June 16, 8:30-11:30. Apart from that there is the possibility to hand in weekly exercises that will be graded. The average 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 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.304 (except for week 17, then: Wednesday April 23, 15:30-17:15 in HG00.304) plus "self study" and a weekly 2hr exercise class on Thursday.
The lectures are recorded. These will be put on Brightspace.
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 | 7/4 | 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.) | 10/4 | Work on Exercises 1, due Monday 14/4. |
| 16 | 2 | 14/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.) | 17/4 | Work on Exercises 2, due Tuesday 22/4, discuss Exercises 1 |
| 17 | 3 | Wednesday 23/4 15:30-17:15 | Master Theorem, Karatsuba multiplication, Strassen algorithm, smallest distance in set of points | Slides lecture 3, pages 9-10 of lecture notes, (CLRS: Remainder Chapter 4, Chapter 33.4 (pp 1039-1043). Roughgarden: Sections 1.2, 1.3 and 3.3, 3.4 and 4.1, 4.2 and 4.3.) | 24/4 | Work on Exercises 3, due Tuesday 6/5, discuss Exercises 2 |
| 18 | No lecture, May break | [No lecture this week] | ||||
| 19 | No lecture, Liberation Day, but there are exercise classes on Thursday | [No lecture this week] | 8/5 | Discuss Exercises 3 | ||
| 20 | 4 | 12/5 | P and NP, NP-hard, NP-complete | Slides lecture 4 and lecture notes, (CLRS: Chapter 34 until Fig 34.6, p. 1070, Roughgarden: 19.3 and 22.1, 22.2) | 15/5 | Work on Exercises 4, due Monday 19/5 |
| 21 | 5 | 19/5 | NP-completeness: 3SAT, CNF-SAT, <=3-SAT, ILP, clique, vertex cover, 3-coloring | Slides lecture 5, extra note by Niels van de Weide on 3-coloring. (CLRS: Chapter 34 until page 1092) | 22/5 | Work on Exercises 5, due Monday 26/5, discuss Exercises 4 |
| 22 | 6 | 26/5 | Clique-3Cover, Subset sum, TSP, the class PSPACE. | Slides lecture 6, lecture notes and the extra note by Niels van de Weide on Hamilton Path. (CLRS: Chapter 34.) | No exercise class (Ascension Day), | Here is Exercises 6, due Monday 2/6 |
| 23 | 7 | 2/6 | Cook-Levin Theorem: Proof that 3-SAT is NP-complete; course overview | Slides lecture 7, lecture notes and Wikipedia on the Cook-Levin Theorem, (CLRS: Chapter 34 until page 1085).) | 5/6 | Discuss Exercises 5 and Exercises 6. |