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 |