Skip to main content

Algorithms and Data Structures:  2020-2021

Lecturer

Degrees

Part AComputer Science and Philosophy

Part A CoreComputer Science

Part AMathematics and Computer Science

Term

Overview

The lectures for this course will be pre-recorded and released on the Algorithms and Data Structures folder on Weblearn each week. There will be two lectures/week, released by Tuesday and Thursday, respectively.

The lectures will be supported by discussion on Piazza , as well as weekly online sessions (from week 2 onwards). See Course Materials for the link and sign up details.

 

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:

  • 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 / union-find
  • Binary search trees (Red-Black trees, splay trees)
  • Max flow and min cut in networks; applications
  • Linear programming
  • NP-hardness
  • Approximation algorithms
  • Fixed-parameter 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 useful 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.
  • V. Vazirani, Approximation Algorithms, Springer, 2001