MEng Software Engineering

Year of entry: 2020

Course unit details:
Advanced Algorithms 1

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? Yes

Overview

This course unit has two objectives. The first is to introduce the student to a range of fundamental, non-trivial algorthms, and to the techniques required to analyse their correctness and running-time.  The second is to present a conceptual framework for analysing the intrinsic complexity of computational problems, which abstracts away from details of particular algorithms.

Pre/co-requisites

Unit title Unit code Requirement type Description
Mathematical Techniques for Computer Science COMP11120 Pre-Requisite Compulsory
Foundations of Pure Mathematics A MATH10101 Pre-Requisite Compulsory
Foundations of Pure Mathematics B MATH10111 Pre-Requisite Compulsory
Algorithms and Imperative Programming COMP26120 Pre-Requisite Compulsory
Students who are not from the School 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

This unit follows on from the material covered in COMP26111, focussing more particularly on mathematical analysis rather than on practical implementation. It is divided into two parts. The first considers a collection of important algorithms and analyses their complexity.

Topics considered include finding components in graphs, computing optimum flows in networks, matching in bi-partite graphs, solving the stable marriage problem, and string matching in text.

The second part considers the more general problem of analysing the intrinsic complexity of computational problems. Topics considered include the Turing model of computation and its associated complexity hierarchy, hardness and reductions, and both upper and lower complexity-bounds for various well-known problems from logic and graph theory.
There are two pieces of assessed coursework, and an exam at the end.

 

Learning outcomes

  • Reproduce a range of standard algorithms in Computer Science, and reason about their correctness and computational complexity.

  • Define the notions complexity class (such as PTIME and NPTIME), completeness and hardness, and compare complexity classes by reduction.

  • Show that some tasks are NP-complete and give a range of NP-complete problems.

  • Explain the hierarchy of complexity classes (including deterministic and non-deterministic classes, and time- and space-classes) and prove some of the key theorems concerning these classes.

Syllabus

Part I (up to reading week): Algorithms
    Directed graphs: Tarjan's algorithm and topological orderings
    Undirected graphs: union find and the inverse Ackerman function
    Flow optimization and matching
    The stable marriage problem and the Gale-Shapley algorithm
    String matching and the KMP algorithm.
 
Part II (after reading week): Complexity
    Turing Machines and computational complexity     
    Some problems from logic: upper bounds
    Hardness and reductions: Cook's theorem
    Some problems from graph theory: 3-colouring, Hamiltonian and Eulerian circuits, the TSP
    Some problems from logic: lower bounds
    Savitch's theorem and the Immerman-Szelepcsényi theorem
    How to pass the exam.

Coursework

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 and learning methods

Lectures

22 lecture course but some lectures will be cancelled to provide time for assessed exercises.

Employability skills

Analytical skills
Innovation/creativity
Problem solving

Assessment methods

Method Weight
Written exam 70%
Written assignment (inc essay) 30%

Feedback methods

Two pieces of assessed coursework during the course unit.

Recommended reading

COMP36111 reading list can be found on the School of Computer Science website for current students.

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