| 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 | Chapter 34, also see lecture notes and http://en.wikipedia.org/wiki/Cook-Levin_theorem | 34.2:4,5; 34.3:3,6; 34.4:6 |
| February 26 | Cook-Levin Theorem, NP-complete problems: CNF-SAT, <=3-SAT | Chapter 34 until page 1085 | |
| March 5 | No lecture | ||
| March 12 | NP-completeness: 3SAT, ILP, clique, vertex cover, 3-coloring | Rest Chapter 34, except pp 1092-1096 | 34.5: 4,5, problems 34-1 en 34-2 (pp 1101-1102) |
| March 19 | Subset sum, the class PSPACE, course overview | see lecture notes |