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