Exercise numbers in this page refer to the exercises in Papadimitriou's book.

• Week 38
  • 1.4.10, functions (a), (f) and (j)
  • 2.8.7
  • Solutions in postscript
• Week 39
  • 3.4.1 (a), (d) and (f)
  • 3.4.6
  • Solutions in postscript
• Week 40
  • A translation from NFA to Boolean circuits
  • 7.4.6
  • 7.4.3 (a)
  • Solutions in postscript
• Week 41
  • A proof that HORNSAT is P-complete
  • 8.4.8
  • Solutions in postscript
• Week 42
  • 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
• Week 43
  • 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
• Week 44
  • 10.4.4
  • 10.4.6
  • Solutions in postscript
• Week 45 (postponed to week 46)
  • 11.5.12
  • 11.5.13
  • 11.5.15
  • Solutions in postscript
• Week 46
  • 12.3.2 (a)
  • 13.4.3
  • 13.4.5
  • Solutions in postscript
• Week 47
  • 14.5.9
  • 15.5.6 (a)
  • 17.3.3
  • 17.3.6
  • Solutions in postscript