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, 2001.
Remember: maximum points for a home assignment
returned after primary 2-point deadline
but before the fall-back dealine is 1.5!
- Week 37
- 2-point return deadline is 27.9.2000
- 1.4.10, functions (b), (c), (d) and (g)
- 2.8.8 (a)
- Week 38
- 2-point return deadline is 4.10.2000
- 2.8.18 (a)
- 3.4.1 (b), (c) and (g)
- Week 39
- 2-point return deadline is 11.10.2000
- 4.4.5
- 7.4.5
- Week 40
- 2-point return deadline is 18.10.2000
- 8.4.2
- 8.4.3
- Week 41
- 2-point return deadline is 25.10.2000
- 9.5.2
- 9.5.6
- Week 42
- 2-point return deadline is 1.11.2000
- 9.5.7
- 9.5.10 (a)
- Week 43
- 2-point return deadline is 8.11.2000
- 10.4.13
- 10.4.19 (a)
- Week 44
- 2-point return deadline is 15.11.2000
- 11.5.14
- 11.5.16 (a)
- Week 45
- 2-point return deadline is 22.11.2000
- 12.3.9 (b)
- 13.4.13 (a)
- Week 46
- 2-point return deadline is 29.11.2000
- 14.5.5 (only the KNAPSACK part)
- 15.5.9 (a)
- Week 47
- 2-point return deadline is 7.12.2000
- 17.3.2 (a), (b)
- 17.3.12
- Week 48
- 2-point return deadline is 13.12.2000
- 18.3.6
- 19.4.5
- Week 49
- 2-point return deadline is 20.12.2000
- 9.5.18 (a), (b)
- 9.5.34 (a)
- See also the extra bonus assignments
Class room exercises
- Week 38
- Week 39
- Week 40
- Week 41
- Week 42
- Week 43
- A proof that FEEDBACK VERTEX SET is NP-complete
- A proof that PARTITION INTO TRIANGLES is NP-complete
- Solutions in postscript
- Week 44
- Week 45
- Week 46
- Week 47
- Week 48