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)