| Part 1 (Seg 12) | |
|---|---|
| Class 1: 02/01/25 |
Intro to divide-and-conquer.
Finding min and max with less than 2n-2 comparisons. |
| Class 2: 06/01/25 |
Finding min and max using 3n/2 comparisons.
Review of asymptotic notation. Merge Sort and its analysis using recursion tree method. Master theorem. |
| Class 3: 09/01/25 |
Recap of master theorem and caveats.
The stock buy-and-sell problem using divide-and-conquer. Brief history of integer multiplication. |
| Class 4: 13/01/25 |
Karatsuba's algorithm for integer multiplication.
Lower bound of Omega(n log n) for sorting using comparisons. |
| Class 5: 16/01/25 | Selection algorithm assuming algorithms that can find an exact/approximate median. |
| Class 6: 20/01/25 |
Selection algorithm using median of medians.
Recurrences of the form T(n)=T(an)+T(bn)+O(n). Randomized selection. |
| Class 7: 23/01/25 |
Quick Sort Practice problems |
| Class 8: 27/01/25 |
Linear time sorting: Count sort and radix sort
Discussion of practice problems |
| Class 9: 30/01/25 | Polynomial multiplication; Fast Fourier Transform |
| Part 2 (Seg 34) | |
|---|---|
| Class 10: 03/02/25 | Dynamic Programming: Rod Cutting problem |
| Class 11: 06/02/25 | Dynamic Programming: Edit Distance |
| Class 12: 10/02/25 | Dynamic Programming: Practice Problems |
| Class 13: 18/02/25 | Dynamic Programming: Optimizing space, Trees |
| Class 14: 24/02/25 | Dynamic programming on trees |
| Class 15: 27/02/25 | Greedy Algorithms: Activity selection, Fractional Knapsack, Maximum Independent Set on Trees |
| Class 16: 03/03/25 | Greedy Algorithms: Huffman Codes |
| Class 17: 06/03/25 | Practice Problems: Dynamic programming and greedy algorithms |
| Class 18: 17/03/25 |
Longest Increasing Subsequence
[Guest lecture by Dr Rogers Mathew] |
| Class 19: 20/03/25 | Quiz 2 |
| Part 3 (Seg 56) | |
|---|---|
| Class 20: 24/03/25 | Graph Algorithms: Recap, Breadth-first search |
| Class 21: 27/03/25 | Eccentrities of a tree in linear time; maximum matching in bipartite graphs |
| Class 22: 03/04/25 |
Algorithm for maximum bipartite matching
Definition of DAGs, strongly connected components |
| Class 23: 07/04/25 |
Finding strongly connected components
Shortest paths, intro to Dijkstra's algorithm |
| Class 24: 17/04/25 | Dijkstra's algorithm, Bellman-Ford algorithm, two dynamic programming algorithms for all-pairs shortest paths |
| Class 25: 21/04/25 | Johnson's algorithm, Maximum flow problem: Ford-Fulkerson method |
| Class 26: 24/04/25 | Edmonds-Karp algorithm: Analysis of running time and correctness |
| Class 27: 28/04/25 | Practice problems |