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