Course - Algorithms and Data Structures HT24

Created: January 11, 2024 | Updated: May 15, 2026 | Read markdown | About these notes | View in context | Study these flashcards

Follows on from Course - Design and Analysis of Algorithms HT23^U and explores some more advanced topics in the analysis of algorithms and data structures. Introduces amortised analysis (rather than viewing each operation on a data structure independently, how do they perform over a series of operations?). Formally defines $\mathbf P$ and $\mathbf{NP}$ and analyses some techniques for tackling $\mathbf{NP}$ problems; namely kernelisation, LP relaxation, and approximation algorithms.

Course Webpage
Lecture Slides
Successor to: Course - Design and Analysis of Algorithms HT23^U
Other courses from this term: Courses HT24^U

Notes

Other relevant notes

Notes - Computational Complexity HT25, Index of reductions^U

Problem Sheets

Slides

Notes - ADS HT24, Kernelisation^U

(incoming)
Notes - ADS HT24, Linear programming^U

(incoming)
Notes - ADS HT24, Circulations^U

(incoming)
Notes - ADS HT24, Approximation algorithms^U

(incoming)
Notes - ADS HT24, NP-hardness and NP-completeness^U

(incoming)
Notes - ADS HT24, Flow networks^U

(incoming)
Notes - ADS HT24, Parameterised complexity^U

(incoming)
Notes - ADS HT24, Splay trees^U

(incoming)
Notes - ADS HT24, Disjoint sets^U

(incoming)
Notes - ADS HT24, Binary search trees^U

(incoming)
Notes - ADS HT24, Randomised rounding^U

(incoming)
Notes - ADS HT24, Red-black trees^U

(incoming)
Notes - ADS HT24, Zero-sum games^U

(incoming)
Notes - ADS HT24, Colour coding^U

(incoming)
Notes - ADS HT24, Amortized analysis^U

(sim: 0.632)
Courses HT24^U

(incoming)
Part A^U

(incoming)
University Notes^U

(incoming)
Course - Computational Complexity HT25^U

(incoming)
Course - Design and Analysis of Algorithms HT23^U

(incoming)
Lecture - Design and Analysis of Algorithms HT23, III^U

(sim: 0.621)