# Algorithms and Data Structures: 2020-2021

| |

| Part A — Computer Science and Philosophy |

| Hilary Term 2021 (16 lectures) |

## Overview

**The lectures for this course will be pre-recorded and ****released on the Algorithms and Data Structures folder on Weblearn each week****. ****There will be two lectures/week, released by Tuesday and Thursday, respectively.**

**The lectures will be supported by discussion on Piazza , as well as weekly online sessions (from week 2 onwards). See Course Materials for the link and sign up details.**

This course builds on the first-year Design and Analysis of Algorithms course. It introduces students to a number of highly efficient algorithms and data structures for fundamental computational problems across a variety of areas. Students are also introduced to techniques such as amortised complexity analysis. As in the first-year course, the style of the presentation is rigorous but not formal.

## Learning outcomes

On successful completion of the course students will:

- Understand the implementation, complexity analysis and applications of fundamental algorithms such as max flow and linear programming
- Be able to analyse and use some fundamental data structures, such as binary search trees and disjoint sets
- Have some familiarity with randomised algorithms, approximation algorithms, and fixed parameter algorithms

## Syllabus

- Amortised analysis
- Disjoint sets / union-find
- Binary search trees (Red-Black trees, splay trees)
- Max flow and min cut in networks; applications
- Linear programming
- NP-hardness
- Approximation algorithms
- Fixed-parameter tractability
- Exponential algorithms

## Reading list

The main text used in the course is:

- Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein,
*Introduction to Algorithms*, MIT Press, 2009 (third edition).

Other useful textbooks that cover some of the material are

- S. Dasgupta, C.H. Papadimitriou, and U. V. Vazirani,
*Algorithms*, Mcgraw-Hill, 2006. - J. Kleinberg and E. Tardos,
*Algorithm Design,*Addison-Wesley*,*2006. - V. Vazirani,
*Approximation Algorithms*, Springer, 2001