DM553: Complexity and Computability (10 ECTS)

STADS: 15016101

Level
Bachelor course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: jbj@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None

Academic preconditions:
Students taking the course are expected to:

• Have knowledge of basic datastructures
• Have knowledge of basic algorithms for manipulating (representations of) sets of numbers and graphs as well as implementations of such in an imperative programming language.
• Be able to use basic mathematical argumentation, including
• proof by induction, proof by contradiction and logic expressions
• Be familiar with the use of combinatorial and probabilistic 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

Construct 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 possibility to develop an approximation algorithm for a given NP-hard optimization problem.

Give lower bounds for the complexity of problem 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 DM551 Algorithms and probability.

The course forms the basis for doing a bachelor project as well as elective candidate 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 finite automata and regular expressions for simple languages.

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 finite automata and regular expressions for simple languages.
• 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.

Subject overview


Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:


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

• 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
• Repetition for the exam

Educational form
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. 

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.

Remarks
The course cannot be chosen by students who have passed DM508.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.