Weekly notes and further information concerning the course DM553 (MM850) spring 2023

Information

The course has two codes: DM553 for computer science students and MM850 for mathematics students.

You should check the schedule on the faculty pages.

We use two books and some hand out notes and papers. The books are:

Michael Sipser, Introduction to the theory of computation, 3rd edition Gengage learning. You should buy the book before the first lecture as we start with this.
Cormen, Leiserson, Rivest and Stein, Introduction to algorithms, 3rd edition, MITpress.

Exam assignments

These will appear here as the are posed. Recall from the course description that the final grade will be based on an overall impression of your performance in the assignments and the oral exam.

Oral Exam

Exam questions and information regading the 2024 exam (May change slightly!)

Pensum for the exam in 2024 (same as in 2023)

pensum list

Slides for proof Cooks theorem in Sipser

You may use these slides during the exam Cook proof

Weekly notes in PDF

Slides from Video Lectures

Various notes

Previous exam problems in DM17 in danish

Note that DM17 was a course about computability which covered more than we do in the first part of DM553. Hence some of the questions do not reflect the pensum for DM553. Still many of the problems directly reflect the kind of problems you may meet in DM553. If you do not read danish, please ask a fellow student to help translate the few danish words in the problems.

Previous exam problems in DM17 in Danish and English

Previous exams in DM517

Joergen Bang-Jensen (jbj@imada.sdu.dk)