DM553: Complexity and Computability
The Study Board for Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N330048112, N330048102
Assessment: Second examiner: None, Second examiner: External
Grading: Pass/Fail, 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Bachelor
STADS ID (UVA): N330048101
ECTS value: 10
Date of Approval: 01-11-2022
Duration: 1 semester
Version: Archive
Comment
Entry requirements
Academic preconditions
Students taking the course are expected to:
- 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
The aim of the course is to enable the student to:
- Apply formalisms of formal languages in order to formulate decision problems precisely.
- Work with finite automata, regular expressions, push-down automata and context-free 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 NP-complete.
- Judge the possibilities for developing an approximation or fixed parameter algorithm for a given NP-hard optimization problem.
- Give lower bounds for the complexity of problems that are similar in nature to those studied in the course.
These competencies are important both when one wishes to develop new algorithms for a given problem and when one wants to judge whether a given problem may be possible to solve efficiently (possibly only approximately) by a computer.
The course builds on the knowledge acquired in the courses DM507 Algorithms and data structures and DM565 Formal languages and data processing, or on MM541 Combinatorial mathematics.
The course forms the basis for doing a bachelor project as well as elective masters level courses containing one or more of the following elements: complexity of algorithms, approximation algorithms and computability.
Together with courses as above this course also provides a basis for doing a masters thesis on algorithmic and complexity theoretic subjects.
In relation to the competence profile of the degree it is the explicit focus of the course to:
- 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 push-down automata and context-free grammars for simple languages.
- Equip the students with important tools to prove that a given language cannot be recognized by a finite automation, a push-down 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 NP-complete or undecidable.
Expected learning outcome
The learning objectives of the course is that the student demonstrates the ability to:
- Judge the complexity of (decision) problems.
- Judge the computational power of various models of computation.
- Construct push-down automata and context-free 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 push-down 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 NP-complete or undecidable.
- Define fixed parameter tractability and explain an example of this.
- Give clear, precise definitions and proofs for the above.
Content
The following main topics are contained in the course:
- Finite automata and push-down automata
- Context-free languages and grammars
- Turing machines
- Decidability
- Problem reductions
- Lower bounds (information theoretical and adversary arguments)
- The complexity classes P and NP
- The theory of NP-completeness
- Approximation algorithms
- Parameterized complexity
Literature
Examination regulations
Prerequisites for participating in the exam a)
Timing
Spring
Tests
Written assignment
EKA
N330048112
Assessment
Second examiner: None
Grading
Pass/Fail
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Examination aids
To be announced during the course.
ECTS value
0
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
June
Prerequisites
| Type | Prerequisite name | Prerequisite course |
|---|---|---|
| Examination part | Prerequisites for participating in the exam a) | N330048101, DM553: Complexity and Computability |
Tests
Oral exam
EKA
N330048102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Duration
30 minutes per student and 30 minutes for preparation
Examination aids
To be announced during the course
ECTS value
10
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 re-exam is an oral exam. External examiner, Danish 7 mark scale.
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.These teaching activities are reflected in an estimated allocation of the workload of an average student as follows:
- 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
Administrative Unit
Team at Educational Law & Registration
Offered in
Recommended course of study
Transition rules
Transitional arrangements describe how a course replaces another course when changes are made to the course of study.
If a transitional arrangement has been made for a course, it will be stated in the list.
See transitional arrangements for all courses at the Faculty of Science.