Advanced Data Structures and Algorithms: 2012-2013
|
Lecturer |
|
|
Degrees |
Schedule S1 — Computer Science |
|
Term |
Hilary Term 2013 (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 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, game-theory
Synopsis
- Amortised analysis
- Disjoint sets / union-find
- 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 / union-find
- 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, Mcgraw-Hill, 2006.
- J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2006.