# Advanced Data Structures and Algorithms: 2013-2014

| |

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

| Hilary Term 2014 (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.## Learning outcomes

On successful completion of the course students will:

- Be able to understand and analyse some fundamental data structures, such as binary search trees, disjoint sets, and self-adjusting lists
- Understand the implementation and complexity analysis of fundamental algorithms such as RSA, primality testing, max flow, discrete Fourier transform
- Have been exposed to algorithmic issues in a variety of areas, including linear programming and game-theory
- Have some familiarity with randomised algorithms and approximation algorithms

## Syllabus

- Amortised analysis
- Disjoint sets / union-find
- Binary search trees (Red-Black trees)
- Splay trees
- Self-adjusting lists
- Number theoretic algorithms + RSA
- Primality testing
- Fast Fourier transform
- Linear programming
- Max flow in networks
- Randomized algorithms
- Approximation algorithms
- Stable matching and game theory

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