# Algorithms: 2018-2019

| |

| Part A — Computer Science and Philosophy |

| Hilary Term 2019 (16 lectures) |

## Overview

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. The lectures for this course are recorded, and the recordings will be released at the end of term.## 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