Advanced Data Structures and Algorithms: 2009-2010
Information
|
Lecturer |
|
|
Degrees |
Part A Options — Honour School of Computer Science Schedule B1 — Honour School of Computer Science Schedule B1 — Honour School of Mathematics and Computer Science |
|
Term |
Hilary Term 2010 (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 core course, the style of the presentation is rigorous but not formal.Learning outcomes
On successful completion of the course students will:- Be able to determine the time complexity of algorithms using amortised analysis
- Be able to design and analyse simple randomised algorithms
- Understand the implementation, complexity analysis and some applications of classical algorithms for string matching, primality testing, and the Discrete Fourier transform
- Be able to formulate and solve max-flow problems
- Be able to formulate and solve linear programs
- Understand the implementation, complexity analysis and some applications of splay trees, binomial heaps, Fibonacci heaps and disjoint sets
Synopsis
- Amortised analysis (1 lecture)
- Binomial and Fibonacci heaps (1.5 lectures)
- Disjoint sets / Union-find (2 lectures)
- Splay trees (1.5 lectures)
- Fast Fourier transform (1.5 lectures)
- 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 (2.5 lectures)
Syllabus
Amortised analysis.
Splay trees.
Mergable heaps.
Disjoint sets / Union-find: complexity analysis and applications
Primality testing: the Miller-Rabin algorithm and its probabilistic correctness
String matching: the Rabin-Karp and Knuth-Morris-Pratt algorithms
Max-flow: the Edmonds-Karp algorithm; some applications in optimisation and graph theory
Linear programming: formulating optimisation problems as linear programs; the simplex method; duality.
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.
- Dexter Kozen, The Design and Analysis of Algorithms, Springer 1992