# BSc Computer Science and Mathematics / Course details

Year of entry: 2023

## Course unit details:Algorithms and Complexity

Unit code COMP36111 10 Level 3 Semester 1 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
Foundations of Pure Mathematics B MATH10111 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.

### 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)
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)
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

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