Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

COMP36111 Algorithms and Complexity syllabus 2020-2021

COMP36111 materials

COMP36111 Algorithms and Complexity

Level 3
Credits: 10
Enrolled students: 68

Course leader: Ian Pratt-Hartmann


Additional staff: view all staff

Requisites

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

Additional requirements

  • 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
Timetable
SemesterEventLocationDayTimeGroup
Sem 1 w2-12 ONLINE Lecture Wed 10:00 - 11:00 -
Sem 1 w2-12 INDEPENDENT STUDY Mon 11:00 - 12:00 -
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)
    Ladner's Theorem
    If we get there: First-order logic and complexity: the Entscheidungsproblem.

Deadlines

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)
    Ladner's Theorem
    Dichotomy theorems
    First-order logic and complexity: the Entscheidungsproblem.
    How to pass the exam.

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%

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. 

Reading list

TitleAuthorISBNPublisherYear
Computational complexity : a modern approach Arora, Sanjeev.0521424267 (hbk.) :; 9780521424264 (hbk.) :Cambridge University Press2009.
Introduction to the theory of computation Sipser, Michael.9781133187813Cengage Learningc2013.
Algorithm design and applications Goodrich, Michael T., author.9781119028482John Wiley Inc.2015

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.