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

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.