Advanced Algorithms

Wedi cwblhau'r modiwl dylai'r myfyrwyr fedru:

1. Recognise potentially difficult problems, demonstrate a comprehensive understanding of different methods for solving them and critically evaluate their potential for solving them
2. Develop an appropriate model for a problem as a linear program
3. Classify types of difficult problems, analyse novel problems and make an informed judgement about their classification
4. Describe efficient algorithms for different difficult problems together with their performance
5. Research novel ways of solving a difficult problem, synthesise published information and critically analyse how it fits in the existing frameworks

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 aims at equipping students with an increased knowledge of advanced algorithms.

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 7