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).

Module Delivery

Back to top

Last Published: 19 Oct 2020.