Program Analysis (G6017)

15 credits, Level 5

Autumn teaching

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.

Teaching