MM850: Complexity and Computability

Comment

The course is co-read with: DM553: Complexity and Computability (10 ECTS).

The course is elective for students in mathematics, applied mathematics, and math-economy.

Entry requirements

The course cannot be chosen by students who: have passed DM553

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 logic 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 possibility to develop an approximation or fixed parameter 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 course MM541 Combinatorial mathematics.

The course forms the basis for taking 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.

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
Regular languages and context-free languages
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

See itslearning for syllabus lists and additional literature references.

Examination regulations

Prerequisites for participating in the exam a)

Timing

Spring

Tests

Written assignment

EKA

N310053112

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

Exam element a)

Timing

June

Prerequisites

Type	Prerequisite name	Prerequisite course
Examination part	Prerequisites for participating in the exam a)	N310053101, MM850: Complexity and Computability

Tests

Oral exam

EKA

N310053102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Full name and SDU username

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

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

76 hours per semester

Teaching Method

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.

Intro phase (lectures) - 40 hours
Training phase: 30 hours, including 30 hours tutorials

Note that part of the lectures will be given as video lectures. The participants will watch these and prepare themselves for dicussion about the topics in class.

Activities during the study phase:

Even degree programme of the textbook and other teaching material
The completion of weekly assignments with a view to discussing them at the examiners.
Written take-home assignments as part of the exam
Independent summary of the intro and training phases
Repetition up for exams

Teacher responsible

Name	E-mail	Department
Jørgen Bang-Jensen	jbj@imada.sdu.dk	Algoritmer

Timetable

Odense

Show full time table

Administrative Unit

Institut for Matematik og Datalogi (matematik)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile	Education	Semester	Offer period

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.