Accessibility statement

Theory 3 - COM00023I

« Back to module search

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

Module summary

Computability and Complexity

Related modules

Co-requisite modules

  • None

Prohibited combinations

  • None

Module will run

Occurrence Teaching cycle
A Autumn Term 2020-21

Module aims

The aim of this module is to introduce basic concepts and results in computability theory and complexity theory. In particular, students will learn the concepts of Turing-recognizable languages and Turing-computable functions, and the difference between solvable and unsolvable problems. They will be able to prove unsolvability by reduction. They will understand the time and space complexity of Turing machines, and complexity classes such as P, NP, PSpace, NPSpace and NPC. They will be able to prove NP-completeness by reduction.

Module learning outcomes

 

T301

Determine a language’s place in the Chomsky hierarchy (regular, context-free, context-sensitive or recursively enumerable).

T302

Provide examples of unsolvable problems.

T303

Prove that a problem is unsolvable by reducing a known unsolvable problem to it.

T304

Explain the Church-Turing thesis and its significance.

T305

Define the classes P and NP, and explain their relation to the class ExpTime.

T306

Explain the significance of NP-completeness and provide examples of NP-complete problems.

Assessment

Task Length % of module mark
Online Exam
Theory 3 (THE3)
N/A 100

Special assessment rules

None

Reassessment

Task Length % of module mark
Online Exam
Theory 3 (THE3)
N/A 100

Module feedback

Feedback is provided through work in practical sessions, revision classes, and after the final assessment as per normal University guidelines.

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.

Coronavirus (COVID-19): changes to courses

The 2020/21 academic year will start in September. We aim to deliver as much face-to-face teaching as we can, supported by high quality online alternatives where we must.

Find details of the measures we're planning to protect our community.

Course changes for new students