BSc Computer Science and Mathematics
Year of entry: 2022
- View tabs
- View full page
Course unit details:
Algorithms and Complexity
|Unit level||Level 3|
|Teaching period(s)||Semester 1|
|Offered by||Department of Computer Science|
|Available as a free choice unit?||No|
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.
|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|
|Foundations of Pure Mathematics B||MATH10111||Pre-Requisite||Compulsory|
To enrol students are required to have taken COMP26120 and one of the following: COMP11120, MATH10101 or MATH10111.
- 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)||20%|
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|
|Ian Pratt-Hartmann||Unit coordinator|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.