skip to content

Department of Computer Science and Technology

Principal lecturer: 
John Fawcett
Students: 
Part IA
Term: 
Lent term
Course code: 
Algorithm2
Hours: 
12
Suggested hours of supervisions: 
3

Aims

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

Lectures

  • 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]

Objectives

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.