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.
Three different types of slides are provided for each lecture, namely slides in keynote format "key" (Mac's native editor), "pdf", as well as "pdf condensed". The difference between "pdf" and "pdf condensed" is that "pdf" includes the slides as presented in the lectures, where each stage of the builts is a different slide. The "pdf condensed" version includes all the builts in the same slide, which however may result in clutter on the slide.
Week 1: 15-19 September 2025
Lecture 1 - 15 September 2025
Topics: Introduction to the course and practical information, content and basic notions.
Slides:
Lecture 0 - Introduction to the Course (key)
Lecture 0 - Introduction to the Course (pdf)
Lecture 0 - Introduction to the Course (pdf condensed)
Lecture 1 - Content and Basic Notions (key)
Lecture 1 - Content and Basic Notions (pdf)
Lecture 1 - Content and Basic Notions (pdf condensed)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 1, Chapters 2.1., 2.2.
Lecture 2 - 18 September 2025
Topics: Asymptotic notation, basics of the Divide and Conquer paradigm.
Slides:
Lecture 2 - Asymptotic Notation and Divide and Conquer Fundamentals (pdf)
Lecture 2 - Asymptotic Notation and Divide and Conquer Fundamentals (pdf condensed)
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: 22-26 September 2025
Lecture 3 - 22 September 2025
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 (key)
Lecture 3 - Upper and Lower Bounds for Sorting and Matrix Multiplication (pdf)
Lecture 3 - Upper and Lower Bounds for Sorting and Matrix Multiplication (pdf condensed)
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 - 26 September 2025
Topics: Strassen's algorithm for matrix multiplication, the Selection problem.
Slides:
Lecture 4 - Matrix Multiplication and Selection (key)
Lecture 4 - Matrix Multiplication and Selection (pdf)
Lecture 4 - Matrix Multiplication and Selection (pdf condensed)
References:
Cormen, Leiserson, Riverst and Stein (CLRS) - Chapter 4.2., 9.2.
Week 3: 29 September-3 October 2025
Lecture 5 - 29 September 2025
Topics: Multiplying two polynomials, the Fast Fourier Transform (FFT), the Discrete Fourier Transform (DFT).
Slides:
Lecture 5 - Fast Fourier Transform (key)
Lecture 5 - Fast Fourier Transform (pdf)
Lecture 5 - Fast Fourier Transform (pdf condensed)
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 - 2 October 2025
Topics: Average-case analysis for Quicksort, Average-case lower bounds for sorting.
Slides:
Lecture 6 - Average Case Analysis (key)
Lecture 6 - Average Case Analysis (pdf)
Lecture 6 - Average Case Analysis (pdf condensed)
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: 6 October-10 October 2024
Lecture 7 - 6 October 2025
Topics: Greedy Algorithms, Minimum Spanning Trees.
Slides:
Lecture 7 - The Greedy Approach and Minimum Spanning Trees (key)
Lecture 7 - The Greedy Approach and Minimum Spanning Trees (pdf)
Lecture 7 - The Greedy Approach and Minimum Spanning Trees (pdf condensed)
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 - 9 October 2025
Topics: Running time analysis for Kruskal's algorithm and Prim's algorithm.
Slides:
Lecture 8 - Minimum Spanning Trees Greedy Running Time (key)
Lecture 8 - Minimum Spanning Trees Greedy Running Time (pdf)
Lecture 8 - Minimum Spanning Trees Greedy Running Time (pdf condensed)
Video:
Lecture 8 - Union Find Video Complement
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: 13 October-17 October 2024
Lecture 9 - 13 October 2025
Topics: Network Flows, Maximum Flow, The Ford-Fulkerson Algorithm
Slides:
Lecture 9 - Maximum Flow and the Ford-Fulkerson Algorithm (key)
Lecture 9 - Maximum Flow and the Ford-Fulkerson Algorithm (pdf)
Lecture 9 - Maximum Flow and the Ford-Fulkerson Algorithm (pdf condensed)
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 - 16 October 2025
Topics: The Edmonds-Karp Algorithm for Maximum Flow
Slides:
Lecture 10 - The Edmonds-Karp Algorithm (key)
Lecture 10 - The Edmonds-Karp Algorithm (pdf)
Lecture 10 - The Edmonds-Karp Algorithm (pdf condensed)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.2. ("The Edmonds-Karp algorithm").
Week 6: 20 October-24 October 2025
Lecture 11 - 20 October 2025
Topics: Minimum Cuts, The Correctness of the Ford-Fulkerson Algorithm
Slides:
Lecture 11 - Minimum Cuts and the Correctness of Ford-Fulkerson (key)
Lecture 11 - Minimum Cuts and the Correctness of Ford-Fulkerson (pdf)
Lecture 11 - Minimum Cuts and the Correctness of Ford-Fulkerson (pdf condensed)
References:
Kleinberg and Tardos (KT) - Chapter 7.2.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.2. ("Cuts of flow networks")
Lecture 12 - 23 October 2025
Topics: Modelling with Flows, Polynomial-time Reductions, Maximum Bipartite Matching, Baseball Elimination, Open-pit Mining
Slides:
Lecture 12 - Modelling with Flows (key)
Lecture 12 - Modelling with Flows (pdf)
Lecture 12 - Modelling with Flows (pdf condensed)
References:
Kleinberg and Tardos (KT) - Chapters 7.5., 7.12.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.3.
Note on Open Pit Mining (pdf)
Week 7: 27 October-31 October 2025
Lecture 13 - 27 October 2025
Topics: Introduction to Linear Programming
Slides:
Lecture 13 - Introduction to Linear Programming (key)
Lecture 13 - Introduction to Linear Programming (pdf)
Lecture 13 - Introduction to Linear Programming (pdf condensed)
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 - 30 October 2025
Topics: The Simplex Method
Slides:
Lecture 14 - The Simplex Method (key)
Lecture 14 - The Simplex Method (pdf)
Lecture 14 - The Simplex Method (pdf condensed)
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).