Advanced Data Structures and Algorithms: 2010-2011
Information
|
Lecturer |
|
|
Degrees |
Part A Options — Computer Science |
|
Term |
Hilary Term 2011 (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 such as primality testing, linear optimisation and string matching. Students are also introduced to randomised algorithms and to techniques of 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 carry out amortised analysis of data structures, including splay trees and disjoint sets
- Understand the implementation, complexity analysis and applications of algorithms for string matching, primality testing, max flow, linear programming and the discrete Fourier transform
Synopsis
- Amortised analysis (1.5 lectures)
- Disjoint sets / Union-find (2 lectures)
- Splay trees (1.5 lectures)
- Fast Fourier transform (1 lecture)
- String matching: Rabin-Karp and Knuth-Morris-Pratt algorithms (2 lectures)
- Primality testing: Miller-Rabin algorithm (2 lectures)
- Network flow: Edmonds-Karp algorithm (2 lectures)
- Linear programming (3 lectures)
- Mergeable heaps (1 lecture)
Syllabus
Amortised analysis
Splay trees
Mergable heaps (time permitting)
Disjoint sets / Union-Find
Primality testing (Miller-Rabin algorithm)
String matching (Rabin-Karp and Knuth-Morris-Pratt algorithms)
Max-flow (Edmonds-Karp algorithm)
Linear programming (Simplex method and duality)
Fast Fourier transform
Reading list
The main text used in the course is:
- Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2001 (second edition).
The following text is a useful alternative.
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms, Mcgraw-Hill, 2006.