Program Analysis (G6017)

15 credits, Level 5

Autumn teaching

This module is split into two parts:

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
  • breadth-first search of graphs
  • topological sorting of directed acyclic graphs.

Generic Design Paradigms
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.

Teaching and assessment

We’re currently reviewing teaching and assessment of our modules in light of the COVID-19 situation. We’ll publish the latest information as soon as possible.

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.

This module is running in the academic year 2020/21. We also plan to offer it in future academic years. It may become unavailable due to staff availability, student demand or updates to our curriculum. We’ll make sure to let our applicants know of such changes to modules at the earliest opportunity.