CS411 – Theory of Computation

Credits 20
Level 4
Prerequisites CS208 Logic & Algorithms
Availability Semesters 1 and 2
Elective No
Contact Lectures: 22 | Tutorials: 11 | Labs: 0
Assignments: 88 | Self study: 79
Assessment 30% by coursework, 70% by written examination.
Lecturer Dr Sergey Kitaev

Aims and Objectives

Building on the previous material in software development, to extend and to formalise the student’s abilities in the area of computational complexity.

Learning Outcomes

On completion of the class, a student should be able:

  • to categorise abstract machines and to construct machines appropriate to specific problems
  • to display an understanding of the merits and limitations of the analytical techniques of software development
  • to recognise the significance of complexity classes and analysis and to deduce the complexity of certain types of algorithm
  • to demonstrate a deeper and broader understanding of classes of complexity and of the ability to deduce the complexity of specific algorithms
  • to display an extended ability to determine the complexity of software by the application of analytical techniques
  • to demonstrate practical competence in the range of issues associated with the class


Introduction: the need for formality in the analysis of problems in computation.

Computation by Abstract Machines: classification, finite automata, deterministic and non-deterministic machines, Turing Machines, the halting problem, solvable, semi-solvable and unsolvable problems.

Recursive functions: basic and primitive recursive functions, partial and total recursive functions.

Analysis of Algorithms: complexity of algorithms, divide and conquer, analysing certain algorithms, pairwise comparison problems, matrix multiplication problems, introduction to NP-completeness.

Complexity Theory & its Implications: towards more efficient software; divide and conquer revisited and dynamic programming; matrix multiplication, transitive closure, problems reducible to matrix multiplication; comparison problems – finding the nth largest; the Fast Fourier Transform; NP-completeness.

Students will be required to undertake, as private study, significant practical work associated with the issues of the class.

Indicative Reading*

* This list is indicative only – the class lecturer may recommend alternative reading material. Please do not purchase any of the reading material listed below until you have confirmed with the class lecturer that it will be used for this class.

Introduction to the Theory of Computation (Second Edition, International Edition). Michael Sipser. Thomson Course Technology 2006. ISBN 0-6192-1764.

Computers and Intractability: A Guide to the Theory of NP-Completeness. Michael R. Garey and David S. Johnson. W. H. Freeman and Company 1979. ISBN 0-7167-1045-5