Advanced Algorithms

Module Identifier: CSM1920
Module Title: Advanced Algorithms
Academic Year: 2026/2027
Semester: Semester 1
Co-ordinator: Dr Thomas Jansen
Reading List: View on Aspire
Pre-Requisite: The module requires an understanding of algorithms and their complexity on a level of any UG Computer Science degree. It is not suitable for students on a study scheme that is open to students from different fields (G480).
Exclusive (Any Acad Year): CS31920
Other Staff

Assessment

Assessment Type	Assessment details	Proportion
Semester Assessment	Essay: Essay based on a critical literature review about a novel algorithm to solve a difficult problem 3000 Words	40%
Semester Exam	Written Exam: 2 Hours	60%
Supplementary Assessment	Essay: Essay based on a critical literature review about a novel algorithm to solve a difficult problem 3000 Words	40%
Supplementary Exam	Written Exam: 2 Hours	60%

Learning Outcomes

On successful completion of this module students should be able to:

Recognise potentially difficult problems, demonstrate a comprehensive understanding of different methods for solving them and critically evaluate their potential for solving them
Develop an appropriate model for a problem as a linear program
Classify types of difficult problems, analyse novel problems and make an informed judgement about their classification
Describe efficient algorithms for different difficult problems together with their performance
Research novel ways of solving a difficult problem, synthesise published information and critically analyse how it fits in the existing frameworks

Brief description

The module introduces the concept of difficult problems in a principled way and concentrates on algorithms to deal with them. It presents linear programming as an important general method to deal with many optimisation problems, and covers advanced algorithms, picking from different areas, such as graph algorithms, randomised algorithms, approximation algorithms, online algorithms, algorithms using dynamic programming, and others. The specific choice of advanced algorithms will be driven by current developments and the research interests of the staff teaching the module.

Aims

The module aims at equipping students with an increased knowledge of advanced algorithms.

Content

The module starts with a general introduction to difficult problems and ways of dealing with them, followed by an introduction to linear programming as a generally useful technique. This is followed by a discussion of selected advanced algorithms to solve specific problems.
1. Introduction: difficult problems and how to deal with them (NP-hardness; approximation; heuristics; special cases; small instances; ‘efficient’ exponential time algorithms); about 2 weeks
2. Linear programming: introduction, modelling, simplex algorithm, duality, LP solvers; about 1 week
3. Selected advanced algorithms for specific problems, covering at least two different types of problems, including at least one advanced randomised algorithm; at least 6 weeks

Module skills

Skills type	Skills details
Critical and analytical thinking	Critical analysis of difficult problems and different ways of solving them
Subject Specific Skills	Knowledge of algorithms and algorithmic techniques

Notes

This module is at CQFW Level 7