Algorithms: 20182019
Lecturer 

Degrees 
Schedule B1 (CS&P) — Computer Science and Philosophy Part A — Computer Science and Philosophy Part A Core — Computer Science Schedule B1 — Computer Science 
Term 
Hilary Term 2019 (16 lectures) 
Overview
This course builds on the firstyear 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 firstyear course, the style of the presentation is rigorous but not formal.Learning outcomes
On successful completion of the course students will:
 Understand the implementation, complexity analysis and applications of fundamental algorithms such as max flow and linear programming
 Be able to analyse and use some fundamental data structures, such as binary search trees and disjoint sets
 Have some familiarity with randomised algorithms, approximation algorithms, and fixed parameter algorithms
Syllabus
 Amortised analysis
 Disjoint sets / unionfind
 Binary search trees (RedBlack trees, splay trees)
 Max flow and min cut in networks; applications
 Linear programming
 NPhardness
 Approximation algorithms
 Fixedparamter tractability
 Exponential algorithms
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, McgrawHill, 2006.
 J. Kleinberg and E. Tardos, Algorithm Design, AddisonWesley, 2006.
 V. Vazirani, Approximation Algorithms, Springer, 2001