Gwybodaeth Modiwlau

Module Identifier
CS31920
Module Title
Advanced Algorithms
Academic Year
2020/2021
Co-ordinator
Dr Thomas Jansen
Semester
Semester 1
Pre-Requisite
CC21120 or CS21120
Other Staff
 

Course Delivery

 

Assessment

Due to Covid-19 students should refer to the module Blackboard pages for assessment details

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