- UCAS course code
- UCAS institution code
BSc Computer Science and Mathematics / Course details
Year of entry: 2024
- View tabs
- View full page
Course unit details:
Algorithms and Complexity
|Available as a free choice unit?
The Unit consitites 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.
|Mathematical Techniques for Computer Science
|Fundamentals of Computation
|Algorithms and Data Structures
|Mathematical Foundation & Analysis
|Foundations of Pure Mathematics B
|Foundations of Pure Mathematics A
To enrol students are required to have taken COMP26120 and one of the following: COMP11120, MATH10101 or MATH10111 or MATH11121.
- 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.
Teaching and learning methods
- Analytical skills
- Problem solving
|Written assignment (inc essay)
Through coursework in weeks 4, 7 and 10
COMP36111 reading list can be found on the Department of Computer Science website for current students.
|Scheduled activity hours
|Independent study hours
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.