## 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!
• Current point standings

#### Program

• HW 1
• 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
• 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
• 3A: 4.4.5
• 3B: 7.4.5
• HW 4
• 4A: 8.4.2
• 4B: 8.4.3
• HW 5
• 5A: 9.5.2
• 5B: 9.5.6
• HW 6
• 6A: 9.5.7
• 6B: 9.5.10 (a)
• HW 7
• 7A: 10.4.13
• 7B: 10.4.19 (a)
• HW 8
• 8A: 11.5.14
• 8B: 11.5.16 (a)
• HW 9
• 9A: 12.3.9 (b)
• 9B: 13.4.13 (a)
• HW 10
• 10A: 14.5.5 (only the KNAPSACK part)
• 10B: 15.5.9 (a)
• HW 11