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

On this module, you’ll explore the design of algorithms.

You’ll examine strategies for dealing with wide classes of algorithmic problems, such as:

• divide and conquer
• randomised algorithms
• dynamic programming
• greedy algorithms
• network flow algorithms.

You’ll apply these strategies to write solutions to new problems of asymptotic complexity.

You’ll also explore when each strategy should be applied. For example, in polynomial time, you’ll learn:

• dynamic programming is a useful tool for solving problems
• a greedy algorithm is typically faster.

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.