Teaching assistants: Sushant Agarwal, Apoorva Vijay Tamaskar

- Problem set 3 by Sushant and solutions
- Problem set 2 by Sushant and solutions
- Problem set 1 by Sushant and solutions
- Problem set 1 by Apoorva

- Aug 3: Introduction, insertion sort, merge sort
- Aug 5: Asymptotic notation, recurrences, binary heaps
- Aug 10: Heapsort, Quicksort, O(nlog n) lower bound for comparison sort, counting sort, radix sort (Ref. CLRS) Applications of divide-and-conquer: integer multiplication, Strassen's matrix multiplication (Ref: Dasgupta, Papadimitriou, Vazirani)
- Aug 12: Selection in worst-case linear time (Ref: CLRS) Greedy and dynamic programming techniques: fractional knapsack, 0/1 knapsack problems
- Aug 17: 0/1 knapsack continued, interval scheduling (unweighted and weighted) (Ref: Kleinberg, Tardos), the traveling salesman problem (Ref: Dasgupta, Papadimitriou, Vazirani)
- Aug 19: Huffman codes, Independent sets in trees (Dasgupta et al.), Graph algorithms: DFS in undirected and directed graphs (Ref: CLRS, Dasgupta et al.)
- Aug 24: BFS, topological sort, strongly connected components, Shortest path: Dijskstra's algorithm (Ref: CLRS)
- Aug 26: Dijkstra's algorithm continued, Bellman-Ford, All-pairs shortest paths (Ref: CLRS)
- Aug 31: Quiz 1
- Sep 2: All-pairs shortest paths: Floyd-Warshall algorithm, transitive closure, spanning trees (Ref: CLRS)
- Sep 7: Minimum spanning trees: Prim's and Kruskal's algorithms (Ref: CLRS, Dasgupta, Papadimitriou, Vazirani)
- Sep 9: Disjoint-set data structure (union-find) (Ref: Dasgupta et al., wikipedia)
- Sep 14: Network flows: Ford-Fulkerson method, max-flow min-cut theorem, applications: bipartite matchings (Ref: CLRS), edge-disjoint paths in graphs (Ref: KT)
- Sep 16: Network flows: Edmonds-Karp algorithm (Ref. CLRS)
- Sep 28: Linear programming, duality, max-flow min-cut theorem by LP duality (Ref: Dasgupta et al.)
- Sep 30: Fast Fourier Transform (Ref: Dasgupta et al.)
- Oct 5: Binomial heaps (Ref: Kozen)
- Oct 7: Fibonacci heaps (Ref: Kozen)
- Oct 12: Stable matchings (Ref: Kleinberg-Tardos)
- Oct 14: Hashing (Ref. Sections 11.1-11.3 of CLRS)
- Oct 17: NP-completeness: Introduction, decision and optimization problems, reductions among minimum vertex cover, maximum independent set, and max-clique problems (Ref: Kleinberg-Tardos), NP-completeness of Integer linear programming by reduction from minimum vertex cover problem
- Oct 19: Circuit-SAT problem, Cook-Levin theorem (a.k.a. Cook's theorem) (Ref: Kleinberg-Tardos)
- Oct 21: NP-completeness of 3SAT from Circuit-SAT, reduction from 3SAT to independent set (Ref: Kleinberg-Tardos)
- Oct 24: Reduction to Hamiltonian cycle from 3SAT and to Traveling Salesman Problem from Hamiltonian cycle problem (Ref: Kleinberg-Tardos)
- Oct 26: Midsem discussion
- Nov 4: NP-completeness of subset-sum and 0-1 knapsack (Ref: CLRS), Introduction to approximation algorithms, 2-approximation for vertex cover problem (Ref: CLRS)
- Nov 14: 2-approximation for TSP with triangle inequality, inapproximability of general TSP, randomized 8/7-approximation for Max-3-SAT (Ref: CLRS), derandomization using conditional expectation (Ref: this)
- Nov 16: Randomized algorithms: success probability amplification, Miller-Rabin primality test (Ref:this)
- Nov 18: Miller-Rabin test continued, 2-approximation for Max-Cut by conditional expectation (Ref: Section 1.1 and 1.1.1 of this)