DM553: Complexity and Computability
Comment
Entry requirements
Academic preconditions
 Have knowledge of basic algorithms for manipulating (representations of) sets of numbers and graphs, along with analysis of algorithms.
 Be able to use basic mathematical argumentation, including proof by induction, proof by contradiction and logical expressions
 Be familiar with the use of combinatorial techniques to develop algorithms.
Course introduction
 Apply formalisms of formal languages in order to formulate decision problems precisely.
 Work with finite automata, regular expressions, pushdown automata and contextfree grammars as elements in an algorithmic solution of more complicated problems.
 Decide the complexity of new problems based on knowledge of the complexity of important examples of problems from the course.
 Judge whether a given problem may be solved by a computer or is undecidable.
 Argue that problems are NPcomplete.
 Judge the possibilities for developing an approximation or fixed parameter algorithm for a given NPhard optimization problem.
 Give lower bounds for the complexity of problems that are similar in nature to those studied in the course.
 Give the competence to analyze complexity of (decision) problems.
 Give knowledge about the computational power of different models of computation.
 Enable the student to construct pushdown automata and contextfree grammars for simple languages.
 Equip the students with important tools to prove that a given language cannot be recognized by a finite automation, a pushdown automaton or a Turing machine.
 Enable the student to prove lower bounds for the complexity of algorithms for a given problem.
 Enable the student to develop new approximation algorithms.
 Give the student important tools for proving that a given decision problem is NPcomplete or undecidable.
Expected learning outcome
 Judge the complexity of (decision) problems.
 Judge the computational power of various models of computation.
 Construct pushdown automata and contextfree grammars for simple languages.
 Prove that a given language, which in nature resembles those from the course, cannot be recognized by a finite automaton, a pushdown automaton or a Turing machine.
 Prove lower bounds for the complexity of algorithms for a given problem which in nature resembles those from the course.
 Design new approximation algorithms for a given problem which in nature resembles those from the course.
 Prove that a given decision problem which in nature resembles those from the course is NPcomplete or undecidable.
 Define fixed parameter tractability and explain an example of this.
 Give clear, precise definitions and proofs for the above.
Content
 Finite automata and pushdown automata
 Contextfree languages and grammars
 Turing machines
 Decidability
 Problem reductions
 Lower bounds (information theoretical and adversary arguments)
 The complexity classes P and NP
 The theory of NPcompleteness
 Approximation algorithms
 Parameterized complexity
Literature
Examination regulations
Prerequisites for participating in the exam a)
Timing
Tests
Written assignment
EKA
Assessment
Grading
Identification
Language
Examination aids
ECTS value
Additional information
Prerequisites for participating in the exam consists handing in a document with name and confirmation of participation in the oral exam. The prerequisite examination is a prerequisite for participation in exam element a).
Exam element a)
Timing
Prerequisites
Type  Prerequisite name  Prerequisite course 

Examination part  Prerequisites for participating in the exam a)  N330048101, DM553: Complexity and Computability 
Tests
Oral exam
EKA
Assessment
Grading
Identification
Language
Duration
Examination aids
To be announced during the course
ECTS value
Additional information
The exam consists of an oral exam and a number of assignments handed in during the course. The final grade is given on the basis of an overall assessment of assignments and the oral exam. The external examiner will be able to see the assignments.
The reexam is an oral exam. External examiner, Danish 7 mark scale.
Indicative number of lessons
Teaching Method
 Intro phase (lectures)  38 hours
 Training phase: 38 hours
In the intro phase, concepts, theories and models are introduced and put into perspective.
In the training phase, students train their skills through exercises and dig deeper into the subject matter.
Educational activities
 Self study of the teaching materials
 Solving weekly assignments in order to discuss these at the tutorials
 Written assignments as part of the exam
 Selfguided followup on the intro and tutorial classes
 Review for the exam
Timetable
5 
Monday
30012023

Tuesday
31012023

Wednesday
01022023

Thursday
02022023

Friday
03022023


08  09  
09  10  
10  11  
11  12  
12  13 


13  14 


14  15  
15  16 