BSc Computer Science with Industrial Experience

The Unit constitutes a self-contained introduction to the theory of Computational Complexity. It assumes no pre-requisites other than a knowledge of basic algorithms and mathematical notation. The teaching will be exclusively by means of traditional lectures, supported by the prescribed course text.

COMP26120, COMP11212, and COMP11120 are pre-requisites. For CM students, MATH11121 or equivalent is required.

The unit aims to make students familiar with the basic concepts and techniques of the theory of Computational Complexity. 

ILO 1: implement and analyse basic algorithms encountered in Computer Science (graph processing, string searching, flow networks, matching etc.)

ILO 2: recite the standard hierarchy of commonly-encountered complexity classes defined in relation to the Turing model of computation.

ILO 3: determine the computational complexity of a range of problems.

ILO 4: define the concepts of (problem-) reduction and computational hardness, and to develop familiarity with techniques for establishing lower complexity bounds---especially, NPTime-hardness.

ILO 5: prove the most important and central theorems in Complexity Theory (Cook's theorem, Ladner's theorem, Savitch's theorem the Immerman-Szelepcsényi theorem).

Directed graphs---topological ordering and Kosaraju's algorithm; undirected graphs--- union find; the Grzegorczyk hierarchy; flow networks---optimal flows, min-cost max-flow; 2D matching; string-processing algorithms; Turing Machines and computability; the Entscheidungsproblem; measuring computational complexity; separation theorems; SAT, k-SAT, Horn-SAT and QBF-SAT; hardness and reductions---Cook's theorem; graph-theoretical problems---3-colouring, Hamiltonian and Eulerian circuits; the TSP; integer linear programming; Savitch's theorem and the Immerman-Szelepcsényi theorem.

Two 1-hour lectures per week; coursework to provide practice for examination; final lecture on how to pass the examination.

Through coursework in weeks 4, 7 and 10

1. Sipser, Michael. (2013). Introduction to the theory of computation. Cengage Learning. ISBN: 9781133187813
    
2. Arora, Sanjeev. (2009). Computational complexity: a modern approach. Cambridge University Press. ISBN: 9780511804090
    
3. Goodrich, Michael T. (2015). Algorithm design and applications. Wiley. ISBN: 9781119028482
    
4. Roughgarden, Tim. (2022). Algorithms illuminated. Soundlikeyourself Publishing. ISBN: 9780999282984 

Tuition fees for home students commencing their studies in September 2027 will be £10,050 per annum. Tuition fees for international students will be £39,700 per annum.

For general information please see the undergraduate finance pages.

All students should normally be able to complete their programme of study without incurring additional study costs over and above the tuition fee for that programme. Any unavoidable additional compulsory costs totalling more than 1% of the annual home undergraduate fee per annum, regardless of whether the programme in question is undergraduate or postgraduate taught, will be made clear to you at the point of application. Further information can be found in the University's Policy on additional costs incurred by students on undergraduate and postgraduate taught programmes (PDF document, 91KB).

The University of Manchester is committed to attracting and supporting the very best students. We have a focus on nurturing talent and ability and we want to make sure that you have the opportunity to study here, regardless of your financial circumstances.

For information about scholarships and bursaries please visit our  undergraduate student finance pages .