Week 1 (Jul 27th to Jul 31st)
Introduction, Logistics, Administrivia.
Understanding Recursion with Tower of Hanoi (JE 1.3).
Mergesort (JE 1.4) and Quicksort (JE 1.5) and runtime analysis using recursion trees (JE 1.7).
Finding good pivots using randomization (Notes).
Week 2 (Aug 3rd to Aug 7th)
Finding median deterministically in linear time (JE 1.8).
Karatsuba's Multiplication (JE 1.9).
Exponentiation using duplation and mediation (JE 1.10)
Recursive backtracking for the n-Queens problem (JE 2.1)
Week 3 (Aug 10th to Aug 14th)
Subset Sum with recursive backtracking (JE 2.3)
Intro to Memorization (aka Dynamic Programming) using Fibonacci numbers as a working example (JE 3.1 and 3.2)
Text Segmentation (JE 2.5, 3.3, and 3.4)
Week 4 (Aug 17th to Feb Aug 21st)
Longest Increasing Subsequence (JE 2.6. 2.7. 3.6)
Optimal Binary Search Trees (JE 2.8, 3.9)
Week 5 (Aug 24th to Aug 28th)
Maximum Independent Set on Trees (JE 3.10)
Revisiting Subset Sum (JE 3.8)
How to reconstruct optimal solutions from the DP table.
Week 6 (Aug 31st to Sept 4th) Quiz 1 week
Graph Algorithms and graph traversals (JE 5.2, 5.3. 5.4, 5.5)
Important Variants (JE 5.6) and Flood Filling (JE 5.7)
Depth First Search (JE 6.1)
Topological sorting in DAGs (JE 6.2, 6.3)
Memorization order (JE 6.4)
Week 7 (Sept 7th to Sept 11th)
Properties of DFS traversals (JE Lemma 6.1)
Strong Connectivity (JE 6.5) and Linear time algorithms (JE 6.6)
Week 8 (Sept 14th to Sept 18th)
Minimum Spanning Tree Algorithms (JE 7.1, 7.2)
Boruvka's Algorithm (JE 7.3)
Week 9 (Sept 21st to Sept 25th)
Prims and Kruskals Algorithms (JE 7.4, 7.5)
Shortest Paths and Generic SSSP (JE 8.1, 8.2, 8.3)
Breadth First and Depth First SSSP (JE 8.4, 8.5)
Week 10 (Sept 28th to Oct 2nd)
Dijkstra's Algorithm (JE 8.6)
Bellman Ford (JE 8.7)
Week 11 (Oct 5th to Oct 9th) Quiz 2 week
APSP Algorithms (JE Chapter 9)
Network Flows (JE 10.1, 10.2)
Max Flow Min Cut Theorem and proof via Ford Fulkerson Algorithm (JE 10.3, 10.4)
Week 12 (Oct 12th to Oct 16th)
Flow Decompositions and Edmonds Karp (JE 10.5, 10.6)
Applications: Edge and Vertex Disjoint Paths (JE 11.1, 11.2)
Bipartite Matching (JE 11.3)
Exam Scheduling and Tuple Selection (JE 11.4)
Disjoint Path Covers (JE 11.5)
Week 13 (Oct 19th to Oct 23rd)
Week 14 (Oct 26th to Oct 30th)
Week 15 (Nov 2nd to Nov 6th)