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