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

81%: Lecture
19%: Practical (Workshop)

Assessment

25%: Coursework (Problem set)
75%: Examination (Computer-based examination)

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 5X社区视频 may make minor variations to the contact hours for operational reasons, including timetabling requirements.

We regularly review our modules to incorporate student feedback, staff expertise, as well as the latest research and teaching methodology. We鈥檙e planning to run these modules in the academic year 2024/25. However, there may be changes to these modules in response to feedback, staff availability, student demand or updates to our curriculum.

We鈥檒l make sure to let you know of any material changes to modules at the earliest opportunity.