# Algorithms and Data Structures: 2016-2017

| |

| Schedule S1(CS&P)(3rd years) — Computer Science and Philosophy Schedule B1 (CS&P) — Computer Science and Philosophy Schedule S1(3rd years) — Computer Science |

| Hilary Term 2017 (16 lectures) |

Please note that the information about course delivery will be updated in accordance to current guidance nearer the start of Michaelmas Term.

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

On successful completion of the course students will:

- Understand the implementation, complexity analysis and applications of fundamental algorithms such as max flow, linear programming, and discrete Fourier transform
- 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-paramter tractability
- Exponential algorithms
- Stable matching

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