- UCAS course code
- GG14
- UCAS institution code
- M20
Bachelor of Science (BSc)
BSc Computer Science and Mathematics
Duration: 3 years
Year of entry: 2025
UCAS course code: GG14 / Institution code: M20
- Key features:
Scholarships available
- Typical A-level offer: A*A*A including specific subjects
- Typical contextual A-level offer: AAA including specific subjects
- Refugee/care-experienced offer: AAB including specific subjects
- Typical International Baccalaureate offer: 38 points overall with 7,7,6 at HL, including specific requirements
Fees and funding
Fees
Tuition fees for home students commencing their studies in September 2025 will be £9,535 per annum (subject to Parliamentary approval). Tuition fees for international students will be £36,000 per annum. For general information please see the undergraduate finance pages.
Policy on additional costs
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).
Scholarships/sponsorships
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 .
Course unit details:
Algorithms and Complexity
| Unit code | COMP36111 |
|---|---|
| Credit rating | 10 |
| Unit level | Level 3 |
| Teaching period(s) | Semester 1 |
| Available as a free choice unit? | Yes |
Overview
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.
Pre/co-requisites
| Unit title | Unit code | Requirement type | Description |
|---|---|---|---|
| Mathematical Techniques for Computer Science | COMP11120 | Pre-Requisite | Compulsory |
| Fundamentals of Computation | COMP11212 | Pre-Requisite | Compulsory |
| Algorithms and Data Structures | COMP26120 | Pre-Requisite | Compulsory |
| Mathematical Foundations & Analysis | MATH11121 | Pre-Requisite | Compulsory |
| Foundations of Pure Mathematics B | MATH10111 | Pre-Requisite | Compulsory |
| Foundations of Pure Mathematics A | MATH10101 | Pre-Requisite | Compulsory |
Pre-requisites
To enrol students are required to have taken COMP26120 and one of the following: COMP11120, MATH10101 or MATH10111 or MATH11121.
Aims
The unit aims to explain how to analyse the complexity of a collection of well-known algorithms, and to familiarize students with the basic concepts and techniques of the theory of computational complexity.
Learning outcomes
- To understand the standard hierarchy of commonly-encountered complexity classes defined in relation to the Turing model of computation.
- To understand the concepts of (problem-) reduction and computational hardness, and to develop familiarity with techniques for establishing lower complexity bounds---especially, NPTime-hardness.
- To be familiar with the most important and central theorems in Complexity Theory (Cook's theorem, Ladner's theorem, Savitch's theorem the Immerman-Szelepcsenyi theorem).
- To be able to access and understand the scientific literature in regard to Complexity Theory.
- To be able to analyse the computational complexity of a range of problems.
Syllabus
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.
Teaching and learning methods
Two 1-hour lectures per week; coursework to provide practice for examination; final lecture on how to pass the examination.
Employability skills
- Analytical skills
- Innovation/creativity
- Problem solving
Assessment methods
| Method | Weight |
|---|---|
| Written exam | 80% |
| Set exercise | 20% |
Feedback methods
Through coursework in weeks 4, 7 and 10
Recommended reading
Michael Goodrich, Roberto Tamassia: Algorithm design and applications, John Wiley, 2015
Michael Sipser: Introduction to the Theory of Computation, Third ed., Ceenage Learning, 2012
Sanjeev Arora and Boaz Barak: Computational Complexity, a modern approach, Cambridge, 2016
Study hours
| Scheduled activity hours | |
|---|---|
| Lectures | 22 |
| Independent study hours | |
|---|---|
| Independent study | 78 |
Teaching staff
| Staff member | Role |
|---|---|
| Ian Pratt-Hartmann | Unit coordinator |
Additional notes
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.