Weekly notes and further information concerning the course DM19 Fall 2006

Slides for the exam

• Cook's Theorem
• Hamiltonian cycle is NPC
• The KMP algorithm
• Vertex cover is NPC
• Subset sum is NPC

Extra course notes

• Notes on hamiltonian paths in tournaments in PDF.
• Notes on lower bound proofs by J. Bang-Jensen in PDF
• Notes of 2-SAT from Bang-Jensen and Gutin, Digraphs: Theory, Algorithms and Applications, Springer 2001.

Weekly notes

• Weekly note 1
• Weekly note 2
• Weekly note 3
• Weekly note 4
• Weekly note 5
• Weekly note 6
• Weekly note 7
• Weekly note 8
• Weekly note 9
• Weekly note 10
• Weekly note 11
• Weekly note 12
• Weekly note 13
• Weekly note 14
• Weekly note 15