T-79.5103 Computational Complexity Theory
Tutorial Program, Autumn 2007
- 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.
- 19.9 Wednesday at 16:15 (tutorial 1)
- 24.9. Lecture instead of tutorial.
(Tutorial cancelled due to travel.)
- 1.10. (tutorial 2)
- 8.10. (tutorial 3)
- 15.10. (tutorial 4)
- 22.10. (tutorial 5)
- A proof that MAX2SAT is NP-complete
- A proof that INDEPENDENT SET is NP-complete
- A proof that LONGEST PATH is NP-complete
- A proof that SUBGRAPH ISOMORPHISM is NP-complete
- Solutions in
postscript
- 24.10 (Wednesday) at 16:15 (tutorial 6)
- A proof that FEEDBACK VERTEX SET is NP-complete
- A proof that PARTITION INTO TRIANGLES is NP-complete
- 10.4.4
- 10.4.6
- Solutions in
postscript
5.11. (tutorial 7)
12.11. (tutorial 8)
19.11. (tutorial 9) Cancelled
26.11. (tutorial 10)
10.12 (Monday) at 12:15 in T-B354: Feedback for home assignment 3
To be announced: Review of the
final exam