T-79.240 Special Course on Computational Complexity
Home Assignments, Autumn 2004
- Exercise numbers refer to the exercises in Papadimitriou's book.
- The non-negotiable fall-back deadline of all home assignments is
January 14th, 2005.
- Maximum points for a home assignment returned after the primary
2-point deadline but before the fall-back deadline is 1.5!
- Remember to justify your answers
- Current point standings
Program
- HW 1
- 2-point deadline is 28.9.2004
- 1A: 1.4.10, functions (b), (c), (d) and (g).
Simply saying that f(n) = O(g(n)) is not enough!
- 1B: 2.8.8 (a)
- HW 2
- 2-point deadline is 5.10.2004
- 2A: 2.8.18 (a)
- 2B: 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.
- HW 3
- 2-point deadline is 12.10.2004
- 3A: 4.4.5
- 3B: 7.4.5
- HW 4
- 2-point deadline is 19.10.2004
- 4A: 8.4.2
- 4B: 8.4.3
- HW 5
- 2-point deadline is 26.10.2004
- 5A: 9.5.2
- 5B: 9.5.6
- HW 6
- 2-point deadline is 2.11.2004
- 6A: 9.5.7
- 6B: 9.5.10 (a)
- HW 7
- 2-point deadline is 9.11.2004
- 7A: 10.4.13
- 7B: 10.4.19 (a)
- HW 8
- 2-point deadline is 16.11.2004
- 8A: 11.5.14
- 8B: 11.5.16 (a)
- HW 9
- 2-point deadline is 23.11.2004
- 9A: 12.3.9 (b)
- 9B: 13.4.13 (a)
- HW 10
- 2-point deadline is 30.11.2004
- 10A: 14.5.5 (only the KNAPSACK part)
- 10B: 15.5.9 (a)
- HW 11
- 2-point deadline is 7.12.2004
- 11A: 17.3.2 (a), (b)
- 11B: 17.3.12
- HW 12
- 2-point deadline is 14.12.2004
- Resubmission deadline is
exceptionally
14.1.2005, reception time 10.1.2005 at 12-13
- 12A: 18.3.6
- 12B: 19.4.5
- HW 13
- 2-point deadline is 18.12.2004
- Resubmission deadline is exceptionally
14.1.2005, reception time 10.1.2005 at 12-13
- 13A: 9.5.18 (a), (b)
- 13B: 9.5.34 (a)