Computing
Program Analysis
Module code: G6017
Level 5
15 credits in autumn semester
Teaching method: Lecture, Workshop
Assessment modes: Computer based exam, Coursework
On this module you’ll be taught in two parts: foundations and generic design paradigms.
Part 1: Foundations
You’ll be introduced to the idea of the asymptotic analysis of algorithms. In particular, you’ll explore:
- 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
- data structures with particular emphasis on:
- priority queues
- generic graph data structure
- basic graph algorithms
- depth-first search of graphs
- breadth-first search of graphs
- topological sorting of directed acyclic graphs.
Part 2: Generic Design Paradigms
You’ll study four of the most important methods used as the basis for algorithm design:
- greedy methods
- divide and conquer approaches
- dynamic programming
- network flow.
Considering these generic design paradigms, you’ll look at 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.