Advanced Algorithms

Module Identifier: CS31920
Module Title: Advanced Algorithms
Academic Year: 2027/2028
Semester: Semester 1
Co-ordinator: Dr Thomas Jansen
Reading List: View on Aspire
Pre-Requisite: CC21120 or CS21120
Other Staff: Dr Fred Labrosse; Dr Amanda Clare; Dr Faisal Rezwan; Dr Arina Buzdalova; Professor Bernard Tiddeman; Dr Muhammad Aslam

Assessment

Assessment Type	Assessment details	Proportion
Semester Assessment	Assignment: (60 hours)	40%
Semester Exam	Exam: 2 Hours	60%
Supplementary Assessment	Assignment: (60 hours)	40%
Supplementary Exam	Exam: 2 Hours	60%

Learning Outcomes

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

Recognise potentially difficult problems, compare and analyse different ways for solving them.
Develop an appropriate model for a problem as a linear program
Classify types of difficult problems and propose appropriate ways to solve them
Describe efficient algorithms for different difficult problems together with their performance
Design and implement an algorithm to solve a significant problem

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 provides students with knowledge of advanced algorithms and enhances their problem solving skills, computational thinking, problem analysis, and an improved understanding of the limits of what algorithms can do. Students learn about different approaches to solve different kinds of difficult problems. It contributes to prepare students for careers in research and industry. The focus on modern algorithms lends the module to research-led teaching. The module is an ideal preparation for algorithm-focussed final year projects.

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
Application of Number	N/A
Communication	Writing of a professional report is part of the assignment.
Improving own Learning and Performance	Designing and implementing an advanced algorithm for a difficult problem and overcoming the difficulties when learning how to do that.
Information Technology	Learn about a software package for linear programming.
Personal Development and Career planning	Learning about a `real world’ software package to solve optimisation problems. Comparison of different methods to solve problems and selection of an appropriate method.
Problem solving	Topic of the whole module
Research skills	Required to model a problem as LP.
Subject Specific Skills	Implicit in all algorithms.
Team work	N/A

Notes

This module is at CQFW Level 6