Lecturer	Elias Koutsoupias
Degrees	Schedule S1(CS&P)(3rd years) — Computer Science and Philosophy Schedule S1(3rd years) — Computer Science Schedule B1 — Computer Science Schedule B1(M&CS) — Mathematics and Computer Science
Term	Hilary Term 2014  (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 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.