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: 2018-19

Module occurrences

Occurrence Teaching cycle
A Autumn Term 2018-19

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

Assessment

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

Special assessment rules

None

Reassessment

Task Length % of module mark
University - closed examination
Computability & Complexity (COCO) Exam
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

  • Week 6 and
  • Week 10

and after the tests model answers are provided.

Indicative reading

**** 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 the Approval of Modifications to Existing Taught Programmes of Study.