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)

Tutorial 3: Fast Fourier Transform, Average-Case Analysis

Tutorial 3 (pdf)