Exercise numbers in this page refer to the exercises in Papadimitriou's book.
Home Assignments
The non-negotiable fall-back deadline of all home assignments is
January 15th, 2003.
Remember: maximum points for a home assignment
returned after the primary 2-point deadline
but before the fall-back dealine is 1.5!
- Week 37
- 2-point return deadline is 25.9.2002
- 1.4.10, functions (b), (c), (d) and (g).
Remember to justify your answer,
simply saying that f(n) = O(g(n)) is not enough!
- 2.8.8 (a)
- Week 39
- 2-point return deadline is 9.10.2002
- 2.8.18 (a)
- 3.4.1 (b), (c) and (g).
Note: ignore the last line of exercise.
That is, you don't have to argument whether the non-recursive
languages you find are recursively enumerable or not.
- Week 40
- 2-point return deadline is 16.10.2002
- 4.4.5
- 7.4.5
- Week 41
- 2-point return deadline is 23.10.2002
- 8.4.2
- 8.4.3
- Week 42
- 2-point return deadline is 30.10.2002
- 9.5.2
- 9.5.6
- Week 43
- 2-point return deadline is 6.11.2002
- 9.5.7
- 9.5.10 (a)
- Week 44
- 2-point return deadline is 13.11.2002
- 10.4.13
- 10.4.19 (a)
- Week 45
- 2-point return deadline is 20.11.2002
- 11.5.14
- 11.5.16 (a)
- Week 46
- 2-point return deadline is 27.11.2002
- 12.3.9 (b)
- 13.4.13 (a)
- Week 47
- 2-point return deadline is 4.12.2002
- 14.5.5 (only the KNAPSACK part)
- 15.5.9 (a)
- Week 48
- 2-point return deadline is 11.12.2002
- 17.3.2 (a), (b)
- 17.3.12
- Week 49, Wednesday
- 2-point return deadline is 18.12.2002
- 18.3.6
- 19.4.5
- Week 49, Thursday
- 2-point return deadline is 19.12.2002
- 9.5.18 (a), (b)
- 9.5.34 (a)