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

• Notes - ADS HT24, Amortized analysis^U
• Notes - ADS HT24, Binary search trees^U
• Notes - ADS HT24, Splay trees^U
• Notes - ADS HT24, Red-black trees^U
• Notes - ADS HT24, Disjoint sets^U
• Notes - ADS HT24, Flow networks^U
• Notes - ADS HT24, Circulations^U
• Notes - ADS HT24, Kernelisation^U
• Notes - ADS HT24, NP-hardness and NP-completeness^U
• Notes - ADS HT24, Linear programming^U
• Notes - ADS HT24, Matching^U
• Notes - ADS HT24, Zero-sum games^U
• Notes - ADS HT24, Approximation algorithms^U
• Notes - ADS HT24, Colour coding^U
• Notes - ADS HT24, Randomised rounding^U
• Notes - ADS HT24, Parameterised complexity^U

Other relevant notes

• Notes - Computational Complexity HT25, Index of reductions^U

Problem Sheets

• Sheet 1
• Sheet 2
• Sheet 3
• Sheet 4
• Sheet 5
• Sheet 6
• Sheet 7, solutions

Slides

• Slides 0
• Slides 1
• Slides 2
• Slides 3
• Slides 4
• Slides 5
• Slides 6
• Slides 7
• Slides 8
• Slides 9
• Slides 10
• Slides 11
• Slides 12
• Slides 13
• Slides 14
• Slides 15
• Slides 16

---

Related posts

• 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)