Gwybodaeth Modiwlau
Course Delivery
Assessment
| Assessment Type | Assessment length / details | Proportion |
|---|---|---|
| Semester Assessment | Essay Essay based on a critical literature review about a novel algorithm to solve a difficult problem 3000 Words | 40% |
| Semester Exam | 2 Hours Written Exam | 60% |
| Supplementary Assessment | Essay Essay based on a critical literature review about a novel algorithm to solve a difficult problem 3000 Words | 40% |
| Supplementary Exam | 2 Hours Written Exam | 60% |
Learning Outcomes
On successful completion of this module students should be able to:
Recognise potentially difficult problems, demonstrate a comprehensive understanding of different methods for solving them and critically evaluate their potential for solving them
Develop an appropriate model for a problem as a linear program
Classify types of difficult problems, analyse novel problems and make an informed judgement about their classification
Describe efficient algorithms for different difficult problems together with their performance
Research novel ways of solving a difficult problem, synthesise published information and critically analyse how it fits in the existing frameworks
Brief description
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.
Aims
The module aims at equipping students with an increased knowledge of advanced algorithms.
Content
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
Module Skills
| Skills Type | Skills details |
|---|---|
| Critical and analytical thinking | Critical analysis of difficult problems and different ways of solving them |
| Subject Specific Skills | Knowledge of algorithms and algorithmic techniques |
Notes
This module is at CQFW Level 7