skip to primary navigationskip to content

Department of Computer Science and Technology



Course pages 2022–23

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
Exam: Paper 1 Question 9, 10
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.


  • Graph algorithms. Graph representations. Breadth-first and depth-first search. Topological sort. Minimum spanning tree. Kruskal and Prim algorithms. Single-source shortest paths: Bellman-Ford and Dijkstra algorithms. All-pairs shortest paths: matrix multiplication and Johnson’s algorithms. Maximum flow: Ford-Fulkerson method, Max-Flow Min-Cut Theorem. Matchings in bipartite graphs. [Ref: CLRS3 chapters 22, 23, 24, 25, 26] [about 7 lectures]
  • Advanced data structures. Binomial heap. Amortized analysis: aggregate analysis, potential method. Fibonacci heaps. Disjoint sets. [Ref: CLRS3 chapters 17, 19, 20, 21] [about 4 lectures]
  • Geometric algorithms. Intersection of segments. Convex hull: Graham’s scan, Jarvis’s march. [Ref: CLRS3 chapter 33] [about 1 lecture]


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

* Cormen, T.H., Leiserson, C.D., Rivest, R.L. and Stein, C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN 978-0-262-53305-8

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.