Apply through UCAS
- UCAS course code
- G405
- UCAS institution code
- M20
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 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.
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 Foundation & Analysis | MATH11121 | Pre-Requisite | Compulsory |
| Foundations of Pure Mathematics B | MATH10111 | Pre-Requisite | Compulsory |
| Foundations of Pure Mathematics A | MATH10101 | Pre-Requisite | Compulsory |
Students who are not from the Department of Computer Science must have permission from both Computer Science and their home School to enrol.
Pre-requisites
To enrol students are required to have taken COMP26120 and one of the following: COMP11120, MATH10101 or MATH10111 or MATH11121.
Aims
The units aims to make students familiar 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 Tarjan's algorithm
Undirected graphs: union find, the Grzegorczyk hierarchy, complexity of union find
Flow networks: optimal flows, 2D matching, min-cost max-flow.
Turing Machines and computability
Measuring computational complexity
Separation theorems
Propositional logic and complexity: SAT, k-SAT, Horn-SAT and QBF-SAT (part 1)
Hardness and reductions: Cook's theorem
Graph-theoretical problems: 3-colouring, Hamiltonian and Eulerian circuits, the TSP
Savitch's theorem and the Immerman-Szelepcsényi theorem
Propositional logic and complexity: SAT, k-SAT, Horn-SAT and QBF-SAT (part 2)
Ladner's Theorem
If we get there: First-order logic and complexity: the Entscheidungsproblem.
Teaching and learning methods
Lectures
Turing Machines and computability
Measuring computational complexity
Separation theorems
Propositional logic and complexity: SAT, k-SAT, Horn-SAT and QBF-SAT (part 1)
Hardness and reductions: Cook's theorem
Graph-theoretical problems: 3-colouring, Hamiltonian and Eulerian circuits, the TSP
Savitch's theorem and the Immerman-Szelepcsényi theorem
Propositional logic and complexity: SAT, k-SAT, Horn-SAT and QBF-SAT (part 2)
Ladner's Theorem
Dichotomy theorems
First-order logic and complexity: the Entscheidungsproblem.
How to pass the exam.
Employability skills
- Analytical skills
- Innovation/creativity
- Problem solving
Assessment methods
| Method | Weight |
|---|---|
| Written exam | 80% |
| Written assignment (inc essay) | 20% |
Feedback methods
Through coursework in weeks 4, 7 and 10
Recommended reading
COMP36111 reading list can be found on the Department of Computer Science website for current students.
Sanjeev Arora and Boaz Barak: Computational Complexity, a modern approach, Cambridge, 2016
Michael Sipser: Introduction to the Theory of Computation, Third ed., Ceenage Learning, 2012
Michael Goodrich, Roberto Tamassia: Algorithm design and applications, John Wiley, 2015
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.