ADS: Schedule

Monday: Introduction to the course,
content and basic notions

Thursday: Asymptotic Notation, Fundamentals of Divide and Conquer

Lecture 0 (pdf), Lecture 0 (key), Lecture 1 (pdf), Lecture 1 (key)

Lecture 2 (pdf)

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.

Lecture 3 (pdf), Lecture 3 (key)

Lecture 4 (pdf), Lecture 4 (key)

Lecture 5 (pdf), Lecture 5 (key)

Lecture 6 (pdf), Lecture 6 (key)

Tutorial 1: Asymptotic Notation, Solving Recurrence Relations, Divide and Conquer
 

Tutorial 1 (pdf)

Tutorial 1 solutions (pdf)

Monday: Greedy Algorithms, Minimum Spanning Trees

Thursday: Running time analysis of Kruskal's algorithm and Prim's algorithm

Lecture 7 (pdf), Lecture 7 (key)

Lecture 8 (pdf), Lecture 8 (key)

Tutorial 2: Matrix Multiplication, Strassen's Algorithm, the Selection Problem 

Tutorial 2 (pdf)

Tutorial 2 solutions (pdf)

Monday: Flow Networks, Maximum Flow, The Ford-Fulkerson Algorithm 

Thursday: The Edmonds-Karp Algorithm for Maximum Flow

Lecture 9 (pdf), Lecture 9 (key)

Lecture 10 (pdf), Lecture 10 (key)

Tutorial 3: Fast Fourier Transform, Average-Case Analysis

Tutorial 3 (pdf)

Tutorial 3 solutions (pdf)

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

Lecture 11 (pdf), Lecture 11 (key)

Lecture 12 (pdf), Lecture 12 (key)

Tutorial 4: Greedy Approach, Minimum Spanning Trees

Tutorial 4 (pdf)

Tutorial 4 solutions (pdf)

Monday: Introduction to Linear Programming

Thursday: The Simplex Method

Lecture 13 (pdf), Lecture 13 (key)

Lecture 14 (pdf), Lecture 14 (key)

Tutorial 5: Maximum Flows, Ford-Fulkerson Algorithm, Edmonds-Karp Algorithm, Modelling with Flows

Tutorial 5 (pdf)

Tutorial 6: The Simplex Method

Tutorial 6 (pdf)