Computing
Design and Analysis of Algorithms
Module code: G6017
Level 5
15 credits in autumn semester
Teaching method: Lecture, Seminar
Assessment modes: Coursework, Unseen examination
In this module we’ll delve into the design of algorithms. We’ll see five powerful strategies for dealing with wide classes of algorithmic problems:
- divide and conquer
- randomised algorithms
- dynamic programming
- greedy algorithms
- network flow algorithms.
By looking at examples, we’ll see how to apply these strategies to write fast solutions to new problems, in terms of asymptotic complexity.
We'll also look at when each strategy should be applied. For example, dynamic programming is a useful hammer for solving lots of problems in polynomial time, but typically a greedy algorithm is faster when it exists.
Module learning outcomes
- Given a novel problem specification, determine an appropriate style of algorithm to deploy for that problem.
- Analyse the asymptotic efficiency of an algorithm, distinguishing best-, worst- and expected-cases.
- Design and implement algorithmic solutions to problems based on greedy, dynamic programming and network flow approaches.
- Express an algorithm using abstract pseudo-code rather than using a particular programming language.