T-79.5103 Computational Complexity Theory
Homework, Autumn 2005
- Exercise numbers refer to the exercises in Papadimitriou's book.
- Remember to justify your answers.
- The problems are to be solved individually -
no plagiarism is
tolerated.
Grading
News
-
(20.12.) All HW answers returned before the primary deadlines have now
been graded for this year.
Good look for the fallback and bonus assignments, if you plan to
submit any, and Happy Holidays!
-
(28.11.) BONUS assignments
are available. Deadline is
January 16th 2006. The answers will be graded on the scale 0-1.5.
You cannot revise your answers for these problems. Read more here.
-
(28.11.) You can earn 0.5 HW points by giving
course feedback
in between December 9th 2005 and January 2nd 2006.
-
(22.9.) Notice the more specific instructions on how to return you HW answers
-
(19.9.) The 2-point deadline for HW 2 had a typo - check the corrected date!
How to Return Answers
You can hand in your answers by ...
- ... handing them to the lecturer on the wednesday lecture, or
- ... slipping them into the post box inbetween rooms B336 and
B337, or
- ... sending them by e-mail to the assistant
(mjjtcs.hut.fi). In this case the only acceptable file formats are postscript,
pdf, and ASCII text.
Write all of the following information on the first sheet:
- Course code and name
("T-79.5103 Computational Complexity Theory")
- Your name
- Your student number
- Homework round (e.g., HW 1)
- If you are returning a revised answer, write "revision"
If you return answers on paper:
- Use paper size A4 only
- If you return multiple sheets, bind them together with e.g. staples
If you return answers by email:
- Use the filename
lastname-homeworkround.fileformat.
For example: jarvisalo-1.ps
- Only file formats ps, pdf, and txt are allowed
Deadlines and Revisions
- If you return your original answer no later than the primary 2-point
deadline, you have the possibility to revise your answer based
on feedback.
- Feedback sessions are arranged in conjunction with tutorials.
- The revised answer must be returned no later than the Monday
following the feedback session related with the assignment.
- Revised answers are graded on the reduced scale 0-1.5
- The non-negotiable fall-back deadline of all home assignments is
January 16th, 2006.
- Answers returned after the primary 2-point deadline but no later
than the fall-back deadline are graded on the reduced scale 0-1.5
- Please notice the exceptional deadlines etc. marked in
red.
Program
- HW 1
- 1A: 1.4.10, functions (b), (c), (d) and (g).
Note: Simply saying that f(n) = O(g(n)) is not enough!
- 1B: 2.8.8 (a)
- 2-point deadline 21.9.
- feedback session 26.9.
- revision deadline 3.10.
- HW 2
- 2A: 2.8.18 (a)
- 2B: 3.4.1 (b), (c) and (g).
-
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.
- In the case of non-recursive languages,
use reductions from undecidable problems in the proof.
- 2-point deadline 28.9.
- feedback session 3.10.
- revision deadline 10.10.
- HW 3
- 3A: 4.4.5
- 3B: 7.4.5
- 2-point deadline 5.10.
- feedback session 10.10
- revision deadline 17.10.
- HW 4
- 4A: 8.4.2
- 4B: 8.4.3
- 2-point deadline 12.10.
- feedback session 17.10.
- revision deadline 31.10.
- HW 5
- 5A: 9.5.2
- 5B: 9.5.6
- 2-point deadline 19.10.
- feedback session 31.10.
- revision deadline 7.11.
- HW 6
- 6A: 9.5.7
- 6B: 9.5.10 (a)
- 2-point deadline 2.11.
- feedback session 7.11.
- revision deadline 14.11.
- HW 7
- 7A: 10.4.13
- 7B: 10.4.19 (a)
- 2-point deadline 9.11.
- feedback session 14.11.
- revision deadline 21.11.
- HW 8
- 8A: 11.5.14
- 8B: 11.5.16 (a)
- 2-point deadline 16.11.
- feedback session 21.11.
- revision deadline 28.11.
- HW 9
- 9A: 12.3.9 (b)
- 9B: 13.4.13 (a)
- 2-point deadline 23.11.
- feedback session 28.11.
- revision deadline 5.12.
- HW 10
- 10A: 14.5.5 (only the KNAPSACK part)
- 10B: 15.5.9 (a)
- 2-point deadline 30.11.
- feedback session 5.12.
- revision deadline 9.12.
- HW 11
- 11A: 17.3.2 (a), (b)
- 11B: 17.3.12
- 2-point deadline 7.12.
- feedback session 9.1.2006 at 12 noon in T-B354
- revision deadline 16.1.2006
- HW 12
- 12A: 18.3.6
- 12B: 19.4.5
- 2-point deadline 14.12.
- feedback session 9.1.2006 at 12 noon in T-B354
- revision deadline 16.1.2006
- HW 13
- 13A: 9.5.18 (a), (b)
- 13B: 9.5.34 (a)
- 2-point deadline 19.12.
- feedback session 9.1.2006 at 12 noon in T-B354
- revision deadline 16.1.2006