Exercise numbers in this page refer to exercises in Papadimitriou's book.
Home Assignments
The non-negotiable fall-back deadline of all home assignments is
January 15th, 2000.
Remember: maximum points for a home assignment
returned after primary 2-point deadline
but before the fall-back dealine is 1.5!
- Week 36
- 2-point return deadline is 22.9.1999
- 1.4.10, functions (b), (c), (d) and (g)
- 2.8.8 (a)
- Week 37
- 2-point return deadline is 29.9.1999
- 2.8.18 (a)
- 3.4.1 (b), (c) and (g)
- Week 38
- 2-point return deadline is 6.10.1999
- 4.4.5
- 7.4.5
- Week 39
- 2-point return deadline is 13.10.1999
- 8.4.2
- 8.4.3
- Week 40
- 2-point return deadline is 20.10.1999
- 9.5.2
- 9.5.6
- Week 41
- 2-point return deadline is 27.10.1999
- 9.5.7
- 9.5.10 (a)
- Week 42
- 2-point return deadline is 3.11.1999
- 10.4.13
- 10.4.19 (a)
- Week 43
- 2-point return deadline is 10.11.1999
- 11.5.14
- 11.5.16 (a)
- Week 44
- 2-point return deadline is 17.11.1999
- 12.3.9 (b)
- 13.4.13 (a)
- Week 45
- 2-point return deadline is 24.11.1999
- 14.5.5 (only the KNAPSACK part)
- 15.5.9 (a)
- Week 46
- 2-point return deadline is 1.12.1999
- 17.3.2 (a), (b)
- 17.3.12
- Week 47
- 2-point return deadline is 8.12.1999
- 18.3.6
- 19.4.5
- Week 48
- No lectures, exercises or home assignments
- Week 49
- 2-point return deadline is 22.12.1999
- 9.5.18 (a), (b)
- 9.5.34 (a)
Class room exercises
- Week 36
- Week 37
- Week 38
- Week 39
- Week 40
- Week 41
- A proof that INDEPENDENT SET is NP-complete
- A proof that PARTITION INTO TRIANGLES is NP-complete
- Solutions in postscript
- Week 42
- Week 43
- Week 44
- Week 45