Skip to main content

Advanced Data Structures and Algorithms:  2013-2014

Lecturer

Degrees

Schedule S1(CS&P)(3rd years)Computer Science and Philosophy

Schedule S1(3rd years)Computer Science

Schedule B1Computer Science

Schedule B1(M&CS)Mathematics 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 analyse some fundamental data structures, such as binary search trees, disjoint sets, and self-adjusting lists
  • Understand the implementation and complexity analysis of fundamental algorithms such as RSA, primality testing, max flow, discrete Fourier transform
  • Have been exposed to algorithmic issues in a variety of areas, including linear programming and game-theory
  • Have some familiarity with randomised algorithms and approximation algorithms

Syllabus

  • Amortised analysis
  • Disjoint sets / union-find 
  • Binary search trees (Red-Black trees)
  • Splay trees
  • Self-adjusting lists
  • Number theoretic algorithms + RSA
  • Primality testing 
  • Fast Fourier transform
  • Linear programming 
  • Max flow in networks 
  • Randomized algorithms
  • Approximation algorithms
  • Stable matching and game theory

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.

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.