## 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)