Module overview
This module bridges the gap between theoretical algorithm design and solving real-world, typically intractable, problems. Moving beyond standard textbook proofs, the focus is on Algorithm Engineering: the process of implementing, analysing, and optimising complex algorithms in a production-like environment where an exact solution may not be feasible.
Aims and Objectives
Learning Outcomes
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Use polynomial time reductions to prove NP-completeness
- Use various approximation methods to solve NP-Complete problems
Subject Specific Practical Skills
Having successfully completed this module you will be able to:
- Work as a group to build robust DevOps pipelines (GitHub Actions) to automate algorithm testing and performance regression analysis.
- Implement numerical methods (LP, Gradient Descent, SGD) to solve discrete optimization problems using relaxation and rounding.
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- Git and Github actions
- Dynamic programming for graph problems.
- Solution of optimisation problems using Linear programming, gradient descent, and other numerical methods
- The complexity classes P and NP and NP-Completeness
Syllabus
1. Algorithm Engineering: Asymptotic Analysis, Git & Github actions
2. Graphs: Vertex cover, TSP, k-coloring, shortest paths.
3. Dynamic Programming: Bellman-Ford, Floyd-Warshall, TSP.
4. Intractability: Complexity classes, P vs NP, Reductions, 3-SAT.
5. Linear Programming: Duality, Simplex
6. Gradient Descent: Convexity, Gradients, Newton, Momentum.
7. Approximation Algorithms: α-approximation, greedy
8. Relaxation & Rounding: Relaxing Integer constraints, solving via LP & GD.
9. SAT Solvers: Encoding of Vertex Cover,k-colouring, clique
10. Heuristics & Local Search: Simulated Annealing, Hill Climbing.
Learning and Teaching
Teaching and learning methods
The module consists of
1. Lectures
2. Substantial group software development using CI/CD
| Type | Hours |
|---|---|
| Assessment tasks | 58 |
| Lecture | 36 |
| Revision | 12 |
| Guided independent study | 44 |
| Total study time | 150 |
Assessment
Summative
This is how we’ll formally assess what you have learned in this module.
| Method | Percentage contribution |
|---|---|
| Exam | 60% |
| Computing assignment | 40% |
Referral
This is how we’ll assess you if you don’t meet the criteria to pass this module.
| Method | Percentage contribution |
|---|---|
| Exam | 100% |
Repeat
An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.
| Method | Percentage contribution |
|---|---|
| Exam | 100% |