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

• Current points

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