Coronavirus information for applicants and offer-holders

We understand that prospective students and offer-holders may have concerns about the ongoing coronavirus outbreak. The University is following the advice from Universities UK, Public Health England and the Foreign and Commonwealth Office.

Read our latest coronavirus information

MEng Computer Science with Industrial Experience

Year of entry: 2021

Course unit details:
Algorithms and Complexity

Unit code COMP36111
Credit rating 10
Unit level Level 3
Teaching period(s) Semester 1
Offered by Department of Computer Science
Available as a free choice unit? No

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

 
Coursework
 
Assessment task           Length      How and when feedback is provided  Weighting with in unit
 
36111-cwk1-F-travellingSalesman      5 hours    Week 4                             0%
36111-cwk2-S-linearProramming        5 hours    Week 7                             12%
36111-cwk3-S-crossingSequences       10 hours    Week 10                           13%

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