Algorithms and Data Structures: 2021-2022
Lecturer | |
Degrees | Part A — Computer Science and Philosophy |
Term | Hilary Term 2022 (16 lectures) |
Links |
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 analyse and use some fundamental data structures, such as binary search trees and disjoint sets
- Understand the implementation, complexity analysis and applications of fundamental algorithms such as max flow and linear programming
- Have 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