DM553/MM850: Complexity and Computability

  1. The re-exams will be Zoom exams following the same rules as for the original exam (except that the assignments will not count towards your grade). See the rules below under "Further information about the exam on Zoom".

  1. Assignment 1 Due March 15.
  2. Assignment 2 Due April 15.
  3. Assignment 3 Due May 17.

Textbooks and notes:
  1. Introduction to the Theory of Computation, 3rd edition, by Michael Sipser, Cengage Learning, 2013. This is for the first half of the course, and should be available in the bookstore.
  2. Introduction to Algorithms, 3rd edition, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, MIT Press, 2009. This and the extra notes will be used in the second half of the course.
  3. Extra notes (available from Course Materials in Blackboard):

Lecture notes and problems for discussions sections:
  1. Note 1.
  2. Note 2.
  3. Note 3.
  4. Note 4.
  5. Note 5.
  6. Note 6.
  7. Note 7.
  8. Note 8.
  9. Note 9.
  10. Note 10.
  11. Note 11.
  12. Note 12.
  13. Note 13.
  14. Note 14.
  15. Note 15.
  16. Note 16.
  17. Note 17.
  18. Note 18.
  19. Note 19.

Notes about proofs: Notes.
Slides for the formula in the Cook-Levin Theorem: Slides. May be used at the oral exam.
Slides for the 2-approximation algorithm for TSP with the triangle inequality: Slides.
Teaching assistant's, David Hammer's ("instruktors") homepage.
Exam information for 2020: Compared to 2018, for 2020, there is less about finite automata, and there is the material in "Course Materials" in Blackboard about parameterized algorithms. More information will be available later.
Questions" and additional exam information.
Further information" about the exam on Zoom.
"Pensum" (material students should know for the exam).
Exam information for 2018:
"Questions" and additional exam information.
"Pensum" (material students should know for the exam).
Exam information for 2016:
"Questions" and additional exam information.
"Pensum" (material students should know for the exam).

IMADA HOME | SDU HOME | Previous page |
Last modified: Wed Jun 8 16:42:32 CEST 2016 - Joan Boyar


   Data protection at SDUDatabeskyttelse på SDU