# COMP36111 Algorithms and Complexity syllabus 2021-2022

COMP36111 Algorithms and Complexity

Level 3
Credits: 10
Enrolled students: pending

Requisites

• Pre-Requisite (Compulsory): COMP11120
• Pre-Requisite (Compulsory): COMP11212
• Pre-Requisite (Compulsory): COMP26120
• Pre-Requisite (Compulsory): MATH10111

• 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.

Assessment methods

• 80% Written exam
• 20% Coursework
Themes to which this unit belongs
• Programming and Algorithms

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

This course unit detail provides the framework for delivery in 20/21 and may be subject to change due to any additional Covid-19 impact.  Please see Blackboard / course unit related emails for any further updates.

## Aims

The units aims to make students familiar with the basic concepts and techniques of the theory of Computational Complexity.

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

36111-cwk1-F-Formulating Arguments; Out of 20; Deadline End Wk II Oct 4th 14:00 36111-cwk2-S-exercisesA; Out of 20; Deadline End Wk IV Oct 18th 14:00 36111-cwk3-S-exercisesB; Out of 20; Deadline End Wk IX Nov 22nd 14:00

## Teaching 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.

## Feedback methods

Through coursework in weeks 4, 7 and 10

## Study hours

• Lectures (22 hours)

## Employability skills

• Analytical skills
• Innovation/creativity
• Problem solving

## Learning outcomes

On successful completion of this unit, a student will be able to:

• 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.