DM553: Complexity and Computability

Announcements:
  1. There will be a review session on June 14, at 10:15, in U23A.
Assignments:
  1. Assignment 1 is due at 10:15 on March 13.
  2. Assignment 2 is due at 10:15 on May 1.
  3. Assignment 3 is due at 10:15 on June 8.
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): This is a subset of the notes for DM508 and the same as those for DM553 in 2015 and 2016.
Lecture notes and problems for discussions sections:
  1. Note 1. This includes general information about the course. Smartboard result from first lecture.
  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.
Slides for the 2-approximation algorithm for TSP with the triangle inequality: Slides.
Slides about local search: Slides.
Slides from introduction to online algorithms: Slides.
Results from the midterm course evaluation.
Teaching assistant's, David Hammer's ("instruktors") homepage.
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 SDU ▪ Databeskyttelse på SDU