Skip to main content

Advanced Data Structures and Algorithms:  2012-2013

Lecturer

Degrees

Schedule AComputer Science

Schedule B1Computer Science

Schedule B1Mathematics and Computer Science

Term

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.