BSc Computer Science with Industrial Experience / Course details

Year of entry: 2024

Course unit details:
Algorithms and Complexity

Course unit fact file
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.

Return to course details