Advanced Data Structures and Algorithms: 20122013
Lecturer 

Degrees 

Term 
Hilary Term 2013 (16 lectures) 
Overview
This course builds on the firstyear 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 firstyear 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 apply amortised analysis on data structures, including binary search trees, mergable heaps, and disjoint sets.
 Understand the implementation and complexity analysis of fundamental algorithms such as RSA, primality testing, max flow, discrete Fourier transform.
 Have an idea of applications of algorithms in a variety of areas, including linear programming and duality, string matching, gametheory
Synopsis
 Amortised analysis
 Disjoint sets / unionfind
 Binary search trees
 Mergeable heaps
 Number theoretic algorithms + RSA
 Fast Fourier transform
 Linear programming
 Max flow in networks
 String matching
 Approximation algorithms
 Stable matching
Syllabus
 Amortised analysis
 Disjoint sets / unionfind
 Binary search trees
 Mergeable heaps
 Number theoretic algorithms + RSA
 Fast Fourier transform
 Linear programming
 Max flow in networks
 String matching
 Approximation 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, McgrawHill, 2006.
 J. Kleinberg and E. Tardos, Algorithm Design, AddisonWesley, 2006.