Department of Computer Science and Technology

Course pages 2021–22

# Algorithms 2

Principal lecturer: Dr Damon Wischik
Taken by: Part IA CST
Term: Lent
Hours: 12
Format: Video lectures and in-person Q&A sessions
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, timetable

## Aims

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

## Lectures

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

## 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.