T-79.5103 Computational Complexity Theory
Tutorial Program, Autumn 2006
- Tutorials take place on Mondays at 14:15 in T-B355 (exceptions are
marked in red)
- Exercise numbers refer to the exercises in Papadimitriou's book.
- Feedback session for
weekly
home assignments takes place immediately after the
tutorials
- Friday 22.9 at 12:15 in T-B353 (tutorial 1)
- 2.10. (tutorial 2)
- 9.10. (tutorial 3)
- Review of the first quarter exam
- A translation from NFA to Boolean circuits
- 7.4.6
- 7.4.3 (a)
- Solutions in
postscript
- 16.10. (tutorial 4)
- 23.10. (tutorial 5)
- A proof that MAX2SAT is NP-complete
- A proof that LONGEST PATH is NP-complete
- A proof that SUBGRAPH ISOMORPHISM is NP-complete
- Solutions in
postscript
- Feedback for HA 2
- Wednesday 25.10. at 10:15 in
T-B353 (replaces Wednesday's lecture) (tutorial 6)
- A proof that INDEPENDENT SET is NP-complete
- A proof that FEEDBACK VERTEX SET is NP-complete
- A proof that PARTITION INTO TRIANGLES is NP-complete
- Solutions in
postscript
- Friday 10.11. at 12:15 in T-B353 (tutorial 7)
- 13.11. (tutorial 8)
- 20.11. (tutorial 9)
- Friday 1.12. at 12:15 in T-B353 (tutorial 10)
- 4.12. (tutorial 11)
- 11.12. in T-B354
- 8.1.2007 at 12:00 in T-B354
- Feedback for HAs 10 and 11