Gwybodaeth Modiwlau

Module Identifier
CS31710
Module Title
Advanced Algorithms
Academic Year
2018/2019
Co-ordinator
Dr Thomas Jansen
Semester
Semester 1
Pre-Requisite
CS21120 or CC21120
Other Staff
 

Course Delivery

Delivery Type Delivery length / details
Lecture 20 x 1 Hour Lectures
 

Assessment

Assessment Type Assessment length / details Proportion
Semester Exam 2 Hours   60%
Semester Assessment 40 Hours   Assignment  40%
Supplementary Assessment 40 Hours   Assignment  Students should resit failed components  40%
Supplementary Exam 2 Hours   Students should resit failed components  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.

Aims

The module extends the algorithmic aspects of CC/CS21120. It introduces students to significant algorithms that are connected to different fields of research, each field aligned with an active research group in the department. This makes it an ideal preparation for major projects in Semester 2.

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 (2 lectures): difficult problems and how to deal with them (NP-hardness; approximation; heuristics; special cases; small instances; ‘efficient’
exponential time algorithms).

2. Linear programming (2 lectures): introduction, modelling, simplex algorithm, duality, LP solvers.

3. Selected topics from Advanced Reasoning (4 lectures): e.g., flow algorithms, streaming algorithms.

4. Selected topics from Bioinformatics (4 lectures): e.g., string algorithms (sequence alignment), hidden Markov models.

5. Selected topics from Intelligent Robotics (4 lectures): e.g., Kalman filters, particle filters.

6. Selected topics from Vision, Graphics and Visualisation (4 lectures), e.g., fast Fourier transform, scan line algorithm, morphing algorithms.

Module Skills

Skills Type Skills details
Application of Number Inherent to linear programming.
Communication Written communication skills as part of the assignment.
Improving own Learning and Performance Usage of a significant software package as part of the assignment.
Information Technology Inherent to the subject matter.
Personal Development and Career planning
Problem solving Explicit in first topic; implicit in all algorithms.
Research skills Usage of a significant software package as part of the assignment.
Subject Specific Skills As laid out in the learning outcomes.
Team work

Notes

This module is at CQFW Level 6