Kursussøgning, efter- og videreuddannelse – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Kursussøgning, efter- og videreuddannelse

Computability and Complexity (CoCo)

Practical information
Study year 2016/2017
Block 3
Programme level Full Degree Master
Course responsible
  • Christian Wulff-Nilsen (7-6d71716e71717c42666b306d7730666d)
  • Department of Computer Science
Course number: NDAA09007U

Course content

In computing, there is continual tension between time usage and space usage, and what can be computed and what cannot be computed at all.  The purpose of this course is to explore these issues.


  • Regular languages
  • Context-free languages
  • Turing machines
  • Decidability
  • Reducibility
  • Complexity
  • Complexity classes (P, NP, PSPACE, EXPSPACE, L, and NL)
  • Intractability

Learning outcome

At course completion, the successful student will have:

Knowledge of:

  • Computational models such as finite automata, pushdown automata, and Turing machines, the languages recognized by some of these models, and techniques for showing their limitations, such as the pumping lemmas for regular and for context-free languages.
  • The power and limits of algorithmic solvability, with focus on the computationally unsolvable Halting problem.
  • The reducibility method for proving that additional problems are computationally unsolvable.
  • How to analyze algorithms and their time and space complexity and how to classify problems according to the amount of time and space required to solve them.
  • Known computational problems that are solvable in principle but not in practice, i.e., intractable problems.

Skills in:

  • Reading and writing specifications of languages using computational models and grammars.
  • Classifying given languages according to type (regular, context-free, etc.) and algorithmic problems according to complexity (time and space).
  • Showing the equivalence between certain machine models.
  • Presenting the relevant constructions and proofs in writing, using precise terminology and an appropriate level of technical detail.

Competences to:

  • Reason reliably about language classes and computational models and their strengths and limitations, and about the complexity of algorithms and algorithmic problems.
  • Communicate effectively about the theory of computation, both for accessing advanced topics from the research literature, and convincingly presenting the results of own work.


Recommended prerequisites

Basic algorithms and discrete mathematics course(s). The course "Logic in Computer Science" would be useful, but are not essential.

Sign up

As an exchange, guest and credit student - click here!

Continuing Education - click here!


MSc programme in Computer Science


Study Board of Mathematics and Computer Science

Course type

Single subject courses (day)


1 block


---- SKEMA LINK ----

Teaching and learning methods

Lectures and exercise classes.


No limit




Is expected to be: Introduction to the Theory of Computation, Michael Sipser, International third edition. See Absalon when the course is set up.


Category Hours
Theory exercises 9
Lectures 36
Exam 4
Preparation 157
English 206


Type of assessment

Written examination, 4 hours under invigilation
All books and notes may be brought to the exam.


Written aids allowed

Marking scale

7-point grading scale

Criteria for exam assessment

See learning outcome.

Censorship form

No external censorship
Several internal examiners


If student is not qualified then qualification can be achieved by hand-in and approval of equivalent assignments.

The re-exam will also be a 4 hours written exam, unless there are 10 or fewer students signed up, in which case it will be an oral exam (25 minutes oral exam without preparation).

Mere information om kurset
Er du BA- eller KA-studerende?
Er du bachelor- eller kandidat-studerende, så find dette kursus i kursusbasen for studerende:

Kursusinformation for indskrevne studerende