T-79.240 Special Course on Computational Complexity

Home Assignments, Autumn 2003

• Exercise numbers refer to the exercises in Papadimitriou's book.
• The non-negotiable fall-back deadline of all home assignments is January 15th, 2004.
• Maximum points for a home assignment returned after the primary 2-point deadline but before the fall-back deadline is 1.5!

Program

• Week 37
  • 2-point return deadline is 25.9.2003
  • 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 38
  • 2-point return deadline is 2.10.2003
  • 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 39: No home assignment this week
• Week 40
  • 2-point return deadline is 16.10.2003
  • 4.4.5
  • 7.4.5
• Week 41
  • 2-point return deadline is 23.10.2003
  • 8.4.2
  • 8.4.3
• Week 42
  • 2-point return deadline is 30.10.2003
  • 9.5.2
  • 9.5.6
• Week 43
  • 2-point return deadline is 6.11.2003
  • 9.5.7
  • 9.5.10 (a)
• Week 44
  • 2-point return deadline is 13.11.2003
  • 10.4.13
  • 10.4.19 (a)
• Week 45
  • 2-point return deadline is 20.11.2003
  • 11.5.14
  • 11.5.16 (a)
• Week 46
  • 2-point return deadline is 27.11.2003
  • 12.3.9 (b)
  • 13.4.13 (a)
• Week 47
  • 2-point return deadline is 4.12.2003
  • 14.5.5 (only the KNAPSACK part)
  • 15.5.9 (a)
• Week 48
  • 2-point return deadline is 11.12.2003
  • 17.3.2 (a), (b)
  • 17.3.12
• Week 49, Tuesday
  • 2-point return deadline is 16.12.2003
  • 18.3.6
  • 19.4.5
• Week 49, Thursday
  • 2-point return deadline is 18.12.2003
  • 9.5.18 (a), (b)
  • 9.5.34 (a)