Design and Analysis of Algorithms (G6017)

15 credits, Level 5

Autumn teaching

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:

  1. divide and conquer
  2. randomised algorithms
  3. dynamic programming
  4. greedy algorithms
  5. 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.

Teaching

77%: Lecture
23%: Seminar

Assessment

25%: Coursework (Problem set)
75%: Examination (Unseen examination)

Contact hours and workload

This module is approximately 150 hours of work. This breaks down into about 44 hours of contact time and about 106 hours of independent study. The University may make minor variations to the contact hours for operational reasons, including timetabling requirements.

We regularly review our modules to incorporate student feedback, staff expertise, as well as the latest research and teaching methodology. We’re planning to run these modules in the academic year 2026/27. However, there may be changes to these modules in response to feedback, staff availability, student demand or updates to our curriculum.

We’ll make sure to let you know of any material changes to modules at the earliest opportunity.

Courses

This module is offered on the following courses: