Lecture schedule
| Date | Lecture | References | Misc |
|---|---|---|---|
| Lecture #1 Mon 16/01 | Introduction to the course; administrative details; algorithms for integer multiplication - what constitutes a good algorithm? [slides] |
| PS0 released |
| Lecture #2 Tue 17/01 | Stable marriage problem; Gale-Shapley algorithm and examples [slides] |
| |
| Lecture #3 Wed 18/01 | Gale-Shapley algorithm - proof of correctness; properties of the solution and proof of optimality [slides] |
| |
| Tutorial #1 Fri 20/01 | Based on Problem set 0 | | |
| Lecture #4 Mon 23/01 | Recall of asymptotic analysis; Divide-and-conquer - Karatsuba's algorithm, recurrence relations, recurrence trees, master theorem [slides] |
| PS1 released |
| Lecture #5 Tue 24/01 | Order statistics - finding the \(k^{th}\) smallest element; median-of-medians - recursive solution, analyzing the recurrence using recursion trees [slides] |
| |
| Lecture #6 Wed 25/01 | Convolution of vectors; equivalence with polynomial multiplication; evaluating polynomials on mulitple points; FFT algorithm [slides] |
| |
| Lecture #7 Mon 30/01 | FFT algorithm (contd.); Closest pair of points in 2D [slides] |
| PS2 released |
| Lecture #8 Tue 31/01 | Basic graph algorithms; adjacency matrices and lists; graph traversals - DFS [slides] |
| |
| Tutorial #2 Wed 01/02 | Discussion of Problem Sets 1 and 2 | | |
| Mini-quiz #1 Fri 03/02 | Based on material covered in Problem sets 0, 1, 2 | | |
| Lecture #9 Mon 06/02 | BFS; finding connected components in graphs; digraphs - classification of edges [slides] |
| PS3 released |
| Lecture #10 Tue 07/02 | DFS with clocks - classification of edges; Topological ordering of DAGs [slides] |
| |
| Lecture #11 Wed 08/02 | Digraphs and their strongly connected components; Finding and labelling the strongly connected components of a digraph [slides] |
| |
| Tutorial #3 Fri 10/02 | Discussion of Problem set 3 | | |
| Lecture #12 Mon 13/02 | Finding and labelling strongly connected components - Kosaraju-Sharir algorithm; Shortest paths in graphs - BFS [slides] |
| PS4 released |
| Lecture #13 Tue 14/02 | Shortest path in unweighed graphs - BFS (contd); Shortest paths in DAGs [slides] |
| |
| Lecture #14 Wed 15/02 | Shortest path in graphs - Dijkstra's algorithm [slides] |
| |
| Tutorial #4 Fri 17/02 | Discussion of Problem set 4 | | |
| Lecture #15 Mon 20/02 | Shortest path in graphs - Dijkstra's algorithm (contd), Bellman-Ford algorithm [slides] |
| |
| Quiz #1 Tue 21/02 | Based on material covered till Mon Feb 13 | | |
| Lecture #16 Wed 22/02 | Bellman-Ford algorithm (contd) [notes] |
| |
| Lecture #17 Fri 24/02 | Greedy algorithms - interval scheduling [notes] |
| |
| Lecture #18 Mon 27/02 | Greedy algorithms - scheduling jobs to minimize delays; exchange arguments |
| PS5 released |
| Lecture #19 Tue 28/02 | Greedy algorithms - scheduling jobs to minimize delays; exchange arguments; greedy vertex cover [notes] |
| |
| Lecture #20 Wed 01/03 | Huffman coding - optimal prefix codes and binary trees [notes] |
| |
| Tutorial #5 Fri 03/03 | Discussion of Problem set 5 | | |
| Lecture #21 Mon 06/03 | Huffman coding - algorithm and proof of correctness [notes] |
| PS6 released |
| Lecture #22 Tue 07/03 | Huffman coding - implementation details; Minimum spanning trees - cut property [notes] |
| |
| Mini-quiz #2 Fri 10/03 | Based on Problem sets 5 and 6 | | |
| Lecture #23 Mon 13/03 | Minimum spanning trees - proof of the cut property; Boruvka's algorithm [notes] |
| PS7 released |
| Lecture #24 Tue 14/03 | Prim's and Kruskal's algorithms - examples, implementation details, running time [notes] |
| |
| Lecture #25 Wed 15/03 | Kruskal's algorithm - amortized analysis; data structures for disjoint sets [notes] |
| |
| Tutorial #6 Fri 17/03 | Discussion of Problem set 7 | | |
| Quiz #2 Tue 21/03 | Based on material covered through Problems sets 5,6,7 | | |
| Lecture #26 Fri 24/03 | Union-by-rank with path compression; Amortized analysis - accounting method [notes] |
| |
| Lecture #27 Mon 27/03 | Union-by-rank with path compression - amortized analysis [notes] |
| |
| Lecture #28 Tue 28/03 | Dynamic programming - text segmentation [notes] |
| |
| Lecture #29 Wed 29/03 | Dynamic programming - text justification, edit distance [notes] |
| PS8 released |
| Tutorial #7 Fri 31/03 | Discussion of Problem set 8 | | |
| Lecture #30 Mon 03/04 | Dynamic programming - edit distance; saving space using divide-and-conquer [notes] |
| |
| Lecture #31 Wed 05/04 | Dynamic programming - edit distane (contd.); 0-1 Knapsack - pseudopolynomial-time algorithm [notes] |
| Online lecture - video link on Zulip |
| Lecture #32 Mon 10/04 | 0-1 Knapsack - pseudopolynomial-time algorithm (contd.); Dynamic programming on trees - independent sets [notes] |
| |
| Lecture #33 Tue 11/04 | All Pairs Shortest Paths (APSP) - Johnson's algorithm; Dynamic programming based algorithms [notes] |
| |
| Lecture #34 Wed 12/04 | Floyd-Warshall algorithm; APSP and matrix multiplication [notes] |
| |
| Lecture #35 Mon 17/04 | APSP and matrix multiplication - Seidel's algorithm; Introduction to computational intractability [notes] |
| PS9 released |
| Lecture #36 Tue 18/04 | Introduction to intractability - P and NP; poly-time solving versus poly-time verification [notes] |
| |
| Lecture #37 Wed 19/04 | Polynomial-time reductions - NP completeness, examples of reductions [notes] |
| |
| Mini-quiz #3 Fri 21/04 | Based on Problem set 8 | | |
| Lecture #38 Mon 24/04 | NP-completeness - examples of reductions [notes] |
| PS10 released |
| Lecture #39 Tue 25/04 | Beyond NP-completeness - brief overview; Wrap-up of the course | | |
| Mini-quiz #4 Wed 26/04 | Based on Problem set 9 | |