This module is offered in 2020-21.

## Aims

The aims of this module are:

• To explain the theoretical limits of computation, the concepts of complexity classes, and the practical evaluation of the complexities of specific algorithms.

## Learning Outcomes

On successful completion of this module, the student should:

• Be familiar with the limits of models of computation under the Church-Turing hypothesis.
• Be familiar with the complexity classes P, NP, co-NP, NP-hard, and others.
• Be able to evaluate specific algorithms in terms of worst- and average-case complexity of performance.

## Syllabus

• Introduction to machine models of computation and languages:
• Review finite state machines; Equivalence with regular-expression languages by example.
• Review context-free grammars; Equivalence with push-down automata by example.
• Introduce non-determinism.
• The Turing Machine (TM) model of computation:
• Definition of TM; Examples of problems solvable with TMs but not with Context-Free Grammars/Regular Expressions.
• Computable languages; Invariance under varying number of tapes/alphabet/random access machines.
• Decidability:
• Example of languages unsolvable with TMs; Undecidability; Introduction to diagonalisation as a proof method.
• Resource-bounded computation.
• Review big O notation; Time and space bounds on TMs; Defining complexity classes (including at least P, PSPACE, EXP, EXPSPACE).
• Simple results on time and space classes
• Hierarchy theorems (just statements) and their implications; Inclusion of time and space classes; Determinism and non-determinism.
• The P vs NP question
• Nondeterminism and the NP complexity class; the concept of NP-hard and NP-complete problems.
• The SATisfiability problem and Cook’s theorem; reductions between NP-complete problems (Graph Isomorphism/Hamilton Cycle/Clique).
• Practical complexity
• Best case/average case/worst case; Approximate algorithms; Quick overview of linear programming and integer linear programming.
• Complexity analysis of algorithms
• Common sorting/search problems; maximum matching; simple graph algorithms.

## Compulsory Elements

This module has no compulsory elements beyond those common to all modules (mark of 4 in each assessment component).