Computability & Complexity - COM00002I

« Back to module search

  • Department: Computer Science
  • Module co-ordinator: Dr. Detlef Plump
  • Credit value: 10 credits
  • Credit level: I
  • Academic year of delivery: 2016-17

Related modules

Co-requisite modules

  • None

Prohibited combinations

  • None

Module occurrences

Occurrence Teaching cycle
A Spring Term 2016-17

Module aims

The aim of this module is to introduce basic concepts and results in computability theory and complexity theory.

Module learning outcomes

  • Understanding of Turing-recognizable languages, Turing-computable functions, and the difference between solvable and unsolvable problems
  • Ability to prove unsolvability by reduction
  • Understanding the time and space complexity of Turing machines, the complexity classes P and NP, and NP-completeness
  • Ability to prove NP-completeness by reduction


Task Length % of module mark
University - closed examination
Computability & Complexity (COCO)
1.5 hours 100

Special assessment rules



Task Length % of module mark
University - closed examination
Computability & Complexity (COCO)
1.5 hours 100

Module feedback

Problem classes are used for working in groups on exercises. Groups and individual students get oral feedback by teaching assistants and the lecturer during problem classes. Model solutions are provided online for comparison.

There are two formative tests in

  • Spring Week 6
  • Spring Week 10

and after the tests model answers are provided.

Key texts

**** Martin, John C., Introduction to Languages and the Theory of Computation (4th ed.), McGraw Hill, 2010

** Rich, Elaine, Automata, Computability and Complexity, Pearson Education, 2008

** Sipser, Michael, Introduction to the Theory of Computation (3rd ed.), South-Western College Publishing, 2012

* Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D., Introduction to Automata Theory, Languages and Computation (3rd ed.), Pearson Education, 2013

* Arora, Sanjeev and Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge University Press, 2009

++ Garey, Michael R. and Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979

The information on this page is indicative of the module that is currently on offer. The University is constantly exploring ways to enhance and improve its degree programmes and therefore reserves the right to make variations to the content and method of delivery of modules, and to discontinue modules, if such action is reasonably considered to be necessary by the University. Where appropriate, the University will notify and consult with affected students in advance about any changes that are required in line with the University's policy on Approval of Modifications to Existing Taught Programmes of Study.