Module Information
Course Delivery
Assessment
| Assessment Type | Assessment length / details | Proportion |
|---|---|---|
| Semester Assessment | Assignment (60 hours) | 40% |
| Semester Exam | 2 Hours Exam | 60% |
| Supplementary Assessment | Assignment (60 hours) | 40% |
| Supplementary Exam | 2 Hours Exam | 60% |
Learning Outcomes
On successful completion of this module students should be able to:
Recognise potentially difficult problems, compare and analyse different ways for solving them.
Develop an appropriate model for a problem as a linear program
Classify types of difficult problems and propose appropriate ways to solve them
Describe efficient algorithms for different difficult problems together with their performance
Design and implement an algorithm to solve a significant problem
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 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.
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 |
|---|---|
| Application of Number | N/A |
| Communication | Writing of a professional report is part of the assignment. |
| Improving own Learning and Performance | Designing and implementing an advanced algorithm for a difficult problem and overcoming the difficulties when learning how to do that. |
| Information Technology | Learn about a software package for linear programming. |
| Personal Development and Career planning | Learning about a `real world’ software package to solve optimisation problems. Comparison of different methods to solve problems and selection of an appropriate method. |
| Problem solving | Topic of the whole module |
| Research skills | Required to model a problem as LP. |
| Subject Specific Skills | Implicit in all algorithms. |
| Team work | N/A |
Notes
This module is at CQFW Level 6