CS3052: Computational Complexity
This module is offered in 2020-21.
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.
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.
- 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.
- 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.
This module has no compulsory elements beyond those common to all modules (mark of 4 in each assessment component).