Advanced Algorithms

Wedi cwblhau'r modiwl dylai'r myfyrwyr fedru:

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

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.

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.

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

Mae'r modiwl hwn yn cydymffurfio a FfCChC Lefel 6