ADS: Course Materials
Notes
For each week, the slides of the lectures will be provided, as well as the appropriate references to the textbooks. Usually the slides follow one or more of the textbooks very closely. As such, when studying or revising, they should be used primarily as a reference to the textbook(s), which explain the topics in appropriate detail and rigour.
I am gradually updating the slides as the course progresses. Old slides from the previous year are given before they got updated. The current system does not allow me to upload the html presentation or files that are big, so only pdf printouts are given.
Week 1: 21-25 September 2026
Lecture 1 - 21 September 2026
Topics: Introduction to the course and practical information, content and basic notions.
Slides:
Lecture 0 - Introduction to the Course (pdf)
Lecture 1 - Content and Basic Notions (pdf)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 1, Chapters 2.1., 2.2.
Lecture 2 - 24 September 2026
Topics: Asymptotic notation, basics of the Divide and Conquer paradigm.
Slides:
Lecture 2 - Asymptotic Notation and Divide and Conquer Fundamentals (pdf)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 2.3.2, Chapters 3.1, 3.2, Chapter 7.1.
Kleinberg and Tardos (KT) - Chapters 2.1., 2.2., 2.4., Chapter 4.1. (up to the end of page 117).
Week 2: 28 September-2 October 2026
Lecture 3 - 28 September 2026
Topics: Solving recurrence relations, upper and lower bounds for sorting, matrix multiplication (introduction and naive approaches).
Slides:
Lecture 3 - Upper and Lower Bounds for Sorting and Matrix Multiplication (pdf)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 4(intro), 4.1., 4.3., 4.4., 4.5., Chapter 7.2. (worst case partitioning), Chapters 8.1.
Kleinberg and Tardos (KT) - Chapter 4.1.
Additional reading (if you are interested):
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 8.2 (Counting Sort)
Lecture 4 - 1 October 2026
Topics: Strassen's algorithm for matrix multiplication, the Selection problem.
Slides:
Lecture 4 - Matrix Multiplication and Selection (pdf)
References:
Cormen, Leiserson, Riverst and Stein (CLRS) - Chapter 4.2., 9.2.
Week 3: 5 October-9 October 2026
Lecture 5 - 5 October 2026
Topics: Multiplying two polynomials, the Fast Fourier Transform (FFT), the Discrete Fourier Transform (DFT).
Slides:
Lecture 5 - Fast Fourier Transform (pdf)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 30.1, 30.2.
Kleinberg and Tardos (KT) - Chapter 4.6.
Further Reading:
Applications of the Discrete Fourier Transform
Lecture 6 - 8 October 2026
Topics: Average-case analysis for Quicksort, Average-case lower bounds for sorting.
Slides:
Lecture 6 - Average Case Analysis (pdf)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 7.1., 7.3., 7.4.
Kleinberg and Tardos (KT) - Chapter 12.5 (only the part about Quicksort)
Additional reading (if you feel you need a refresher on discrete probabilities):
Cormen, Leiserson, Riverst, and Stein (CLRS) - Appendix C
Kleinberg and Tardos (KT) - Chapter 12.1.
Week 4: 12 October-16 October 2026
Lecture 7 - 12 October 2026
Topics: Greedy Algorithms, Minimum Spanning Trees.
Slides:
Lecture 7 - The Greedy Approach and Minimum Spanning Trees (pdf)
References:
Kleinberg and Tardos (KT) - Chapter 5.5. (up to "Implementing Prim's Algorithm on pp. 191).
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 21.1, 21.2. (exlcuding the material about the running time of the algorithms).
Additional reading (graph theory basics and search algorithms on graphs):
Kleinberg and Tardos (KT) - Chapter 3.1., 3.2.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 20.1, 20.2, 20.3
Lecture 8 - 15 October 2026
Topics: Running time analysis for Kruskal's algorithm and Prim's algorithm.
Slides:
Lecture 8 - Minimum Spanning Trees Greedy Running Time (pdf)
References:
Kleinberg and Tardos (KT) - Chapters 5.5. (from "Implementing Prim's Algorithm on pp. 191), 5.6.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 21.2. (the material about the running time of the algorithms).
Additional reading (implementation of Priority Queues via Heaps):
Kleinberg and Tardos (KT) - Chapter 2.5.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 6.1., 6.2., 6.3., and 6.5.
2023/24 IADS Slides: Heapsort slides (introduces the heap data structure), Heap Operations and Priority Queues slides
Week 5: 19 October-23 October 2026
Lecture 9 - 19 October 2025
Topics: Network Flows, Maximum Flow, The Ford-Fulkerson Algorithm
Slides:
Lecture 9 - Maximum Flow and the Ford-Fulkerson Algorithm (pdf)
References:
Kleinberg and Tardos (KT) - Chapter 7.1.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 24.1., 24.2. (up to "The Edmonds-Karp algorithm", and excluding "Cuts of flow networks").
Lecture 10 - 22 October 2025
Topics: The Edmonds-Karp Algorithm for Maximum Flow
Slides:
Lecture 10 - The Edmonds-Karp Algorithm (pdf)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.2. ("The Edmonds-Karp algorithm").
Week 6: 26 October-30 October 2026
Lecture 11 - 26 October 2026
Topics: Minimum Cuts, The Correctness of the Ford-Fulkerson Algorithm
Slides:
Lecture 11 - Minimum Cuts and the Correctness of Ford-Fulkerson (pdf)
References:
Kleinberg and Tardos (KT) - Chapter 7.2.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.2. ("Cuts of flow networks")
Lecture 12 - 29 October 2026
Topics: Modelling with Flows, Polynomial-time Reductions, Maximum Bipartite Matching, Baseball Elimination, Open-pit Mining
Slides:
Lecture 12 - Modelling with Flows (pdf)
References:
Kleinberg and Tardos (KT) - Chapters 7.5., 7.12.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.3.
Week 7: 2 November - 6 November 2026
Lecture 13 - 2 November 2026
Topics: Introduction to Linear Programming
Slides:
Lecture 13 - Introduction to Linear Programming (pdf)
References:
Vanderbei - Linear Programming Foundations and Extensions (accessible via this link), Chapter 1.
Matoušek and Gärtner - Understanding and Using Linear Programming (accessible via this link), Chapter 1, Chapter 2.1., Chapter 3.1.
Additional reading:
Chvatal, Linear Programming, 1983 (available in paper copies via the library).
Lecture 14 - 5 November 2026
Topics: The Simplex Method
Slides:
Lecture 14 - The Simplex Method (pdf)
References:
Vanderbei - Linear Programming Foundations and Extensions (accessible via this link), Chapter 2.
Additional reading:
George B. Dantzig - Origins of the Simplex Method (interesting read about the history of the algorithm).
======= Old notes from last year below =======
Week 8: 3 November-7 November 2025
Lecture 15 - 3 November 2025
Topics: Degeneracy, Geometry, and Duality
Slides:
Lecture 15 - Degeneracy, Geometry, and Duality (key)
Lecture 15 - Degeneracy, Geometry, and Duality (pdf)
Lecture 15 - Degeneracy, Geometry, and Duality (pdf condensed)
References:
Vanderbei - Linear Programming Foundations and Extensions (accessible via this link), Chapters 3.1, 3.2. 3.4 (without the proof for Bland's rule), 3.5., 3.6., Chapter 4.1-4.4, Chapters 5.1 to 5.4.
Notes:
Kat Molinet - Geometry of the Simplex Method (pdf)
Lecture 16 - 6 November 2025
Topics: Modelling with Linear Programs
Slides:
Lecture 16 - Modelling with Linear Programs (key)
Lecture 16 - Modelling with Linear Programs (pdf)
Lecture 16 - Modelling with Linear Programs (pdf condensed)
References:
Vanderbei - Linear Programming Foundations and Extensions (accessible via this link), Chapter 1.1., Chapters 23.1, 23.2.
Week 9: 10 November-14 November 2025
Lecture 17 - 10 November 2025
Topics: Introduction to Dynamic Programming, Chain Matrix Multiplication
Slides:
Lecture 17 - Dynamic Programming, Chain Matrix Multiplication (pdf)
Lecture 17 - Dynamic Programming, Chain Matrix Multiplication (pdf condensed)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 14.2, 14.3.
Lecture 18 - 13 November 2025
Topics: Longest Common Subsequence, Subset Sum
Slides:
Lecture 18 - Longest Common Subsquence and Subset Sum (key)
Lecture 18 - Longest Common Subsquence and Subset Sum (pdf)
Lecture 18 - Longest Common Subsquence and Subset Sum (pdf condensed)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 14.3, 14.4.
Kleinberg and Tardos (KT) - Chapter 6.4.
Week 10: 17 November-21 November 2025
Lecture 19 - 20 November 2025 (NON EXAMINABLE)
Topics: NP-completeness
Slides:
Lecture 19 - NP-completeness (key)
Lecture 19 - NP-completeness (pdf)
Lecture 19 - NP-completeness (pdf condensed)
References:
Kleinberg and Tardos - Chapter 8.