Module Information

Module Identifier

CS31920

Module Title

Advanced Algorithms

Academic Year

2024/2025

Co-ordinator

Professor Bernie Tiddeman

Semester

Semester 1

Pre-Requisite

CC21120 or CS21120

Reading List

View on Aspire

Other Staff

Course Delivery

Assessment

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

Learning Outcomes

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

1. Recognise potentially difficult problems, compare and analyse different ways for solving them.

2. Develop an appropriate model as a linear program for a problem and solve it with the help of an LP solver.

3. Describe significant algorithms from the area of Advanced Reasoning and apply them appropriately.

4. Describe significant algorithms from the area of Bioinformatics and apply them appropriately.

5. Describe significant algorithms from the area of Intelligent Robotics and apply them appropriately.

6. Describe significant algorithms from the area of Vision, Graphics and Visualisation and apply them appropriately.

Brief description

This module covers important, significant and non-trivial algorithms from different fields of research. The different fields covered are aligned with the research groups of the department, Advanced Reasoning, Bioinformatics and Computational Biology, Intelligent Robotics, and Vision, Graphics and Visualisation.

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 from selected topics that are aligned with the four different research groups in the department.

1. Introduction: difficult problems and how to deal with them (NP-hardness; approximation; heuristics; special cases; small instances; ‘efficient’ exponential time algorithms)
2. Linear programming: introduction, modelling, simplex algorithm, duality, LP solvers
3. Selected topics from Advanced Reasoning: e.g., flow algorithms, streaming algorithms
4. Selected topics from Bioinformatics: e.g., string algorithms (sequence alignment), hidden Markov models
5. Selected topics from Intelligent Robotics: e.g., Kalman filters, particle filters
6. Selected topics from Vision, Graphics and Visualisation: e.g., fast Fourier transform, scan line algorithm, morphing algorithms

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	Use of a complex software package and overcoming the difficulties when learning how to apply it.
Information Technology	Use of a significant software package for linear programming.
Personal Development and Career planning	Use of a `real world’ software package for a significant problem as part of the assignment. Comparison of different methods to solve problems and selection of an appropriate method.
Problem solving	Explicit in the first topic; implicit in all algorithms.
Research skills	Required to model a problem as LP.
Subject Specific Skills	Implicit in all algorithms from all areas.
Team work	N/A

Notes

This module is at CQFW Level 6