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)

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

Video:
Lecture 9 - Network Flows

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 - 17 October 2024
Topics: The Edmonds-Karp Algorithm for Maximum Flow

Slides: 
Lecture 10 - The Edmonds-Karp Algorithm (pdf)
Lecture 10 - The Edmonds-Karp Algorithm (key)

References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.2. ("The Edmonds-Karp algorithm").

 

Week 6: 21 October-25 October 2024

Lecture 11 - 21 October 2024
Topics: Minimum Cuts, The Correctness of the Ford-Fulkerson Algorithm

Slides: 
Lecture 11 - Minimum Cuts and the Correctness of Ford-Fulkerson (pdf)
Lecture 11 - Minimum Cuts and the Correctness of Ford-Fulkerson (key)

References:
Kleinberg and Tardos (KT) - Chapter 7.2.
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapter 24.2. ("Cuts of flow networks")

Lecture 12 - 24 October 2024
Topics: Modelling with Flows, Polynomial-time Reductions, Maximum Bipartite Matching, Baseball Elimination, Open-pit Mining

Slides: 
Lecture 12 - Modelling with Flows (pdf)
Lecture 12 - Modelling with Flows (key)

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: 28 October-1 November 2024

Lecture 13 - 28 October 2024
Topics: Introduction to Linear Programming

Slides: 
Lecture 13 - Introduction to Linear Programming (pdf)
Lecture 13 - Introduction to Linear Programming (key)

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 - 31 October 2024
Topics: The Simplex Method

Slides: 
Lecture 14 - The Simplex Method (pdf)
Lecture 14 - The Simplex Method (key)

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

 

Week 8: 4 November-8 November 2024

Lecture 15 - 4 November 2024
Topics: Degeneracy, Geometry, and Duality

Slides: 
Lecture 15 - Degeneracy, Geometry, and Duality (pdf)
Lecture 15 - Degeneracy, Geometry, and Duality (key)

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.

Lecture 16 - 7 November 2024
Topics: Modelling with Linear Programs

Slides: 
Lecture 16 - Modelling with Linear Programs (pdf)
Lecture 16 - Modelling with Linear Programs (key)

References:
Vanderbei - Linear Programming Foundations and Extensions (accessible via this link), Chapter 1.1., Chapters 23.1, 23.2.

 

Week 9: 11 November-15 November 2024

Lecture 17 - 11 November 2024
Topics: Introduction to Dynamic Programming, Chain Matrix Multiplication

Slides: 
Lecture 17 - Dynamic Programming, Chain Matrix Multiplication (pdf)
Lecture 17 - Dynamic Programming, Chain Matrix Multiplication (key)

References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 14.2, 14.3. (pp. 382-383, 387-390).

Lecture 18 - 14 November 2024
Topics: Chain Matrix Multiplication (memoization), Longest Common Subsequence

Slides: 
Lecture 18 - Chain Matrix Multiplication (memoization) and Longest Common Subsquence (pdf)

References:
Cormen, Leiserson, Riverst, and Stein (CLRS) - Chapters 14.3, 14.4.

 

Week 10: 18 November-22 November 2024

Lecture 19 - 21 November 2024 (NON EXAMINABLE)
Topics: NP-completeness

Slides: 
Lecture 18 - NP-completeness (pdf)
Lecture 18 - NP-completeness (key)

References:
Kleinberg and Tardos - Chapter 8.

License
All rights reserved