COMP0017 Computability and Complexity Theory
This database contains the 201819 versions of syllabuses.
Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).
Academic session  201819 
Module  Computability and Complexity Theory 
Code  COMP0017 
Module delivery  1819/A6U/T1/COMP0017 Undergraduate 
Related deliveries  None 
Prior deliveries  
Level  Undergraduate 
FHEQ Level  L6 
FHEQ credits  15 
Term/s  Term 1 
Module leader  Hirsch, Robin 
Contributors  Hirsch, Robin Zanasi, Fabio 
Module administrator  Ball, Louisa 
Aims
The module addresses the theoretical and practical limitations of computation and provides a theoretical framework for modelling computation. The concepts of undecidability and intractability are introduced through a number of examples. The module will convey the proof techniques that are used to classify problems and it is intended that students learn how to apply them in order to classify unfamiliar problems for themselves.
Learning outcomes
On successful completion of the module, a student will be able to:
 analyse the complexity of a variety of problems and algorithms;
 reduce one problem to another;
 prove that a problem is undecidable;
 find a polynomial time reduction from one problem to another;
 determine the complexity class of a decidable problem;
 categorise the complexity of a language.
Availability and prerequisites
This module delivery is available for selection on the belowlisted programmes. The relevant programme structure will specify whether the module is core, optional, or elective.
In order to be eligible to select this module as optional or elective, where available, students must meet all prerequisite conditions to the satisfaction of the module leader. Places for students taking the module as optional or elective are limited and will be allocated according to the department’s module selection policy.
Programmes on which available: 

Prerequisites: 
In order to be eligible to select this module, student must have:

Content
Models of Computation
 Deterministic Turing machines.
 Equivalent Turing machines.
 Register machines.
Languages
 Language recognition.
 Language acceptance.
 Recursive languages.
 Recursively enumerable languages.
Undecidability
 The Halting Problem.
 Problem reduction.
 Undecidability of the tiling problem.
 Undecidability of firstorder logic.
 Other unsolvable problems.
Nondeterminism
 Nondeterministic Turing machines.
 Polynomialtime reduction.
 Elementary properties of polynomial time reduction.
 The complexity classes P, NP, NPcomplete.
 Cook's theorem.
 How to prove NPhardness of various problems.
Probabilistic Algorithms
 Examples of probabilistic algorithms.
 How to make 'almost sure' your algorithm is correct.
 Complexity analysis of probabilistic algorithms.
The complexity classes PP and BPP.
Other Complexity Classes
 Space complexity.
 Savitch’s theorem.
 Exponential time.
 Nonelementary problems.
An indicative reading list is available via http://readinglists.ucl.ac.uk/departments/comps_eng.html.
Delivery
The module is delivered through a combination of lectures and problem classes.
Assessment
This module delivery is assessed as below:
#  Title  Weight (%)  Notes 
1  Written examination (2hrs 30 mins)  90 

2  Coursework  10 

In order to pass this Module Delivery, students must:
 achieve an overall weighted Module mark of at least 40.00%;
AND, when taken as part of BSc Computer Science; MEng Computer Science, and MEng Mathematical Computation:
 achieve a mark of at least 30.00% in any Components of assessment weighed ≥ 30% of the module.
Where a Component comprises multiple Assessment Tasks, the minimum mark applies to the overall component.