ADS: Schedule
| Week | Commencing | Key Topics | Lectures | Tutorials |
|---|---|---|---|---|
| 1 | 15-Sep-2025 | Monday: Introduction to the course, Thursday: Asymptotic Notation, Fundamentals of Divide and Conquer | Not on this week | |
| 2 | 22-Sep-2025 | Monday: Solving recurrence relations, upper and lower bounds for sorting, matrix multiplication (introduction and naive approaches). Thursday: Strassen's algorithm for matrix multiplication, the Selection problem. | Not on this week | |
| 3 | 29-Sep-2025 | Monday: Multiplying two polynomials, the Fast Fourier Transform (FFT), the Discrete Fourier Transform (DFT). Thursday: Average-case analysis for Quicksort, Average-case lower bounds for sorting. | Tutorial 1: Asymptotic Notation, Solving Recurrence Relations, Divide and Conquer
| |
| 4 | 06-Oct-2025 | Monday: Greedy Algorithms, Minimum Spanning Trees Thursday: Running time analysis of Kruskal's algorithm and Prim's algorithm | Tutorial 2: Matrix Multiplication, Strassen's Algorithm, the Selection Problem
| |
| 5 | 13-Oct-2025 | Monday: Flow Networks, Maximum Flow, The Ford-Fulkerson Algorithm Thursday: The Edmonds-Karp Algorithm for Maximum Flow | Tutorial 3: Fast Fourier Transform, Average-Case Analysis | |
| 6 | 20-Oct-2025 | Monday: Minimum Cuts, The Correctness of the Ford-Fulkerson Algorithm Thursday: Modelling with Flows, Polynomial-time Reductions, Maximum Bipartite Matching, Baseball Elimination, Open-pit Mining | Tutorial 4: Greedy Approach, Minimum Spanning Trees | |
| 7 | 27-Oct-2025 | Monday: Introduction to Linear Programming Thursday: The Simplex Method | Tutorial 5: Maximum Flows, Ford-Fulkerson Algorithm, Edmonds-Karp Algorithm, Modelling with Flows | |
| 8 | 3-Nov-2025 | Monday: Degeneracy, Geometry, and Duality | Tutorial 6: The Simplex Method | |
| 9 | 10-Nov-2024 | |||
| 10 | 17-Nov-2024 |