IBC028 Complexity, Spring 2023

Introduction

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.

Material

• Weekly slides and additional notes of the course
• Additional lecture notes of this course (version from March 2019)
• 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 "Algorithms and Data Structures", abbreviated to CLRS below.

Examination

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.

Set up

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):

• Sunday evening: exercises on the web page (first week: Monday evening)
• Monday: Lecture (first week: Wednesday)
• Wednesday/Thursday: students work on exercises
• Monday: hand in exercises before 10:00
• Wednesday/Thursday: explanation of exercises, grades on Brightspace.

Exercise classes

Register for an exercise class in Brightspace before the first exercise class.
1. Wednesday 13:30-15:15, Jorrit de Boer HG00.308 (week 15: Friday 14/4, 15:30-17:15)
2. Wednesday 13:30-15:15, Cass Alexandru HG00.310 (week 15: Friday 14/4, 15:30-17:15)
3. Wednesday 13:30-15:15, Mees Meuwissen HG03.085 (week 15: Friday 14/4, 15:30-17:15)
4. Wednesday 13:30-15:15, Markel Zubia Aldaburu HG00.514 (week 15: Friday 14/4, 15:30-17:15, HG02.052, week 21, May 24, in HG00.307 )
5. Wednesday 13:30-15:15, Casper de With HG01.028 (week 15: Friday 14/4, 15:30-17:15, HG02.032)
6. Wednesday 13:30-15:15, Martan van der Straaten HG00.086 (week 15: Friday 14/4, 15:30-17:15, HG00.065)
7. Wednesday 13:30-15:15, Ruben Turkenburg HG00.514 (week 15: Friday 14/4, 15:30-17:15, Transitorium -1.016), week 21, May 24, in HG00.307
8. Thursday 15:30-17:15, Nadezhda Dobreva HG02.028, for Double Bachelor Mathematics - Computer Science, not in week 17 and week 20

The course by week

The following is the weekly schedule. The content description and exercises are preliminary.
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

herman at cs dot ru dot nl