Advanced Data Structures and Algorithms: 2011-2012
Information
|
Lecturer |
|
|
Degrees |
Part A Options — Computer Science |
|
Term |
Hilary Term 2012 (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 carry out amortised analysis of data structures, including meggable heaps and disjoint sets.
- Understand the implementation, complexity analysis and applications of algorithms including RSA and primality testing, max flow and the discrete Fourier transform.
- Have an idea of applications of algorithms in a variety of areas.
Synopsis
- Amortised analysis
- Mergeable heaps
- Disjoint sets / union-find
- Number theoretic algorithms
- RSA key encryption
- Primality testing: Miller-Rabin algorithm
- Fast Fourier transform
- Linear programming
- Max flow in networks
- Quantum Fourier transform
Syllabus
- Amortised analysis
- Mergeable heaps
- Disjoint sets / union-find
- Number theoretic algorithms
- RSA key encryption
- Primality testing: Miller-Rabin algorithm
- Fast Fourier transform
- Linear programming
- Max flow in networks
- Quantum 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).
For the lectures later in the course the following text may be useful.
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, Mcgraw-Hill, 2006.