Computing

Program Analysis

Module code: G6017
Level 5
15 credits in autumn semester
Teaching method: Lecture, Workshop
Assessment modes: Coursework, Computer based exam

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.