skip to primary navigationskip to content

Department of Computer Science and Technology



Course pages 2023–24

Algorithms 2

Principal lecturer: Dr Damon Wischik
Taken by: Part IA CST
Term: Lent
Hours: 12
Format: In-person lectures
Suggested hours of supervisions: 3
Prerequisites: Algorithms 1
This course is a prerequisite for: Artificial Intelligence, Complexity Theory, Prolog, Randomised Algorithms
Past exam questions, Moodle, timetable


The aim of this course is to provide an introduction to computer algorithms and data structures, with an emphasis on foundational material.


  • Graphs and path-finding algorithms. Graph representations. Breadth-first and depth-first search. Single-source shortest paths: Bellman-Ford and Dijkstra algorithms. All-pairs shortest paths: dynamic programming and Johnson’s algorithms. [About 4 lectures]
  • Graphs and subgraphs. Maximum flow: Ford-Fulkerson method, Max-flow min-cut theorem. Matchings in bipartite graphs. Minimum spanning tree: Kruskal and Prim algorithms. Topological sort. [About 4 lectures]
  • Advanced data structures. Binomial heap. Amortized analysis: aggregate analysis, potential method. Fibonacci heaps. Disjoint sets. [About 4 lectures]


At the end of the course students should:

  • have a thorough understanding of several classical algorithms and data structures;
  • be able to analyse the space and time efficiency of most algorithms;
  • have a good understanding of how a smart choice of data structures may be used to increase the efficiency of particular algorithms;
  • be able to design new algorithms or modify existing ones for new applications and reason about the efficiency of the result.

Recommended reading

* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction to Algorithms, Fourth Edition ISBN 9780262046305 Published: April 5, 2022.

Sedgewick, R., Wayne, K. (2011). Algorithms. Addison-Wesley. ISBN 978-0-321-57351-3.

Kleinberg, J. and Tardos, É. (2006). Algorithm design. Addison-Wesley. ISBN 978-0-321-29535-4.

Knuth, D.A. (2011). The Art of Computer Programming. Addison-Wesley. ISBN 978-0-321-75104-1.