ADS: Course Materials
Week 1: 16-20 September 2024
Lecture 1 - 16 September 2024
Topics: Introduction to the course and practical information, content and basic notions.
Slides:
Lecture 0 - Introduction to the Course (pdf)
Lecture 0 - Introduction to the Course (key)
Lecture 1 - Content and Basic Notions (pdf)
Lecture 1 - Content and Basic Notions (key)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 1, Chapters 2.1., 2.2.
Lecture 2 - 19 September 2024
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: 23-27 September 2024
Lecture 3 - 23 September 2024
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)
Lecture 3 - Upper and Lower Bounds for Sorting and Matrix Multiplication (key)
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 2024
Topics: Strassen's algorithm for matrix multiplication, the Selection problem.
Slides:
Lecture 4 - Matrix Multiplication and Selection (pdf)
Lecture 4 - Matrix Multiplication and Selection (key)
References:
Cormen, Leiserson, Riverst and Stein (CLRS) - Chapter 4.2., 9.2.
Week 3: 30 September-4 October 2024
Lecture 5 - 30 September 2024
Topics: Multiplying two polynomials, the Fast Fourier Transform (FFT), the Discrete Fourier Transform (DFT).
Slides:
Lecture 5 - Fast Fourier Transform (pdf)
Lecture 5 - Fast Fourier Transform (key)
References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 30.1, 30.2.
Kleinberg and Tardos (KT) - Chapter 4.6.
Lecture 6 - 3 October 2024
Topics: Average-case analysis for Quicksort, Average-case lower bounds for sorting.
Slides:
Lecture 6 - Average Case Analysis (pdf)
Lecture 6 - Average Case Analysis (key)
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: 7 October-11 October 2024
Lecture 7 - 7 October 2024
Topics: Greedy Algorithms, Minimum Spanning Trees.
Slides:
Lecture 7 - The Greedy Approach and Minimum Spanning Trees (pdf)
Lecture 7 - The Greedy Approach and Minimum Spanning Trees (key)
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 - 10 October 2024
Topics: Running time analysis for Kruskal's algorithm and Prim's algorithm.
Slides:
Lecture 8 - Minimum Spanning Trees Greedy Running Time (pdf)
Lecture 8 - Minimum Spanning Trees Greedy Running Time (key)
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: 14 October-18 October 2024
Lecture 9 - 14 October 2024
Topics: Network Flows, Maximum Flow, The Ford-Fulkerson Algorithm
Slides:
Lecture 9 - Maximum Flow and the Ford-Fulkerson Algorithm (pdf)
Lecture 9 - Maximum Flow and the Ford-Fulkerson Algorithm (key)
References:
Kleinberg and Tardos (KT) - Chapter 7.1.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 24.1., 24.2. (up to "The Endmonds-Karp algorithm", and excluding "Cuts of flow networks").