Computing

Program Analysis

Module code: G6017
Level 5
15 credits in autumn semester
Teaching method: Lecture
Assessment modes: Coursework, Unseen examination

This module is split into two parts:

Foundations
In the first part of the module, you are introduced to the idea of the asymptotic analysis of algorithms. In particular, you consider the following:

• specifying a problem
• the notion of an algorithm and what it means for an algorithm to solve a problem
• the upper, lower and tight asymptotic bounds associated with an algorithm
• the best-, worst- and expected-case analysis of an algorithm
• the lower bound for a problem.

You also consider a number of important data structures, with particular emphasis on priority queues and the generic graph data structure. You look at several basic graph algorithms, in particular:

• depth-first search of graphs
• topological sorting of directed acyclic graphs.

In the second part of the module, you consider four of the most important methods used as the basis for algorithm design:

• greedy methods
• divide and conquer approaches
• dynamic programming
• network flow.

In considering these generic design paradigms, you look at a number of well-known problems, including:

• interval scheduling
• single source shortest path
• minimum spanning tree
• Huffman codes construction
• weighted interval scheduling
• subset sum
• sequence alignment
• network flow
• bipartite matching.

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.