DM553: Complexity and Computability (10 ECTS)

STADS: 15016101

Level
Bachelor course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: joan@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. Fælles med DM508 Algoritmer og datastrukturer.

Prerequisites:
None

Academic preconditions:
The topics from Algorithms & Data Structures and Algorithms & Probability assumed known.

Course introduction
To introduce the theory of finite automata, formal language formalism, decidability of languages, methods for developing and analysing approximation algorithms, the complexity of algorithms and certain aspects of complexity theory.

Qualifications
The students will gain detailed insight into the formalisms in formal languages, the complexity of problems, including approximability for optimization problems, and undecidability, and will be able to apply the obtained knowledge in relevant situations to:

• apply techniques such as closure properties and pumping lemmas for regular (context free) languages in order to demonstrate that a given language is not regular (context-free)
• give an account of those steps which are involved in proofs that a language is not regular (context-free) when one applies the corresponding pumping lemmas
• transform a given non-deterministic automaton into an equivalent deterministic finite automaton
• describe context free grammars and pushdown automatas for simple context-free languages and describe a pushdown automaton accepting an arbitrary context-free language, provided this is given by a context-free grammar
• describe Turing machines in words or using diagrams
• describe Turing machines deciding/accepting typical languages which are decidable respectively, Turing acceptable
• choosing, among the many different Turing machine models, one which is most suitable for a given decidable language and be able to argue for this choice
• give simple proofs for undecidability of languages and properties of languages for Turing machines
• apply Rice's theorem to prove undecidability of languages
• prove lower bounds on the complexity of problems using information theoretic arguments
• prove lower bounds on the complexity of problems and algorithms using adversary arguments
• formally define the classes P and NP, explain Cook's Theorem and prove that various problems are NP-Complete
• explain and analyze approximation algorithms

Expected learning outcome
After the course the students are expected to be able to:

• Construct finite automata and regular expressions for simple languages
• Construct pushdown automata and context-free grammars for simple languages
• Apply theorems and algorithms for regular and context-free languages within the scope of the course´s syllabus
• Prove that certain languages are not regular or context-free using e.g. closure properties and pumping lemmas
• Construct deterministic and non-deterministic Turing machines that decide a given language or compute a given function
• Prove the undecidability of certain languages using Rice´s theorem and reductions
• prove lower bounds on the complexity of problems using information theoretic arguments
• prove lower bounds on the complexity of problems and algorithms using adversary arguments
• modify known algorithms and analyses to special cases of known problems and to new problems
• explain and analyze approximation algorithms from the course
• design and analyze new approximation algorithms to solve problems which resemble problems from the course
• formally define the classes P and NP
• explain Cook's Theorem, which shows that SAT is NP-Complete
• prove that various problems are NP-Complete

Subject overview
Finite automata, pushdown automata, Turing machines, regular languages, context- free languages, grammars, decidability, lower bounds (information theoretic and adversary arguments), complexity classes, P and NP, NP-completeness, approximation algorithms.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Obligatory assignments. Evaluated internal on a pass/fail basis by the teacher. (15016112)

Assessment and marking:

1. Oral exam, lasting about 30 minutes, with 30 minutes preparation. The exam is evaluated by external censorship according to the Danish 7-mark scale (10 ECTS). (15016102)

Expected working hours
The teaching method is based on three phase model.
Intro phase: 38 hours
Skills training phase: 38 hours, hereof:
 - Tutorials: 38 hours

Educational activities Study phase: 30 hours

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.