Classes: Tuesdays and Thursdays 09:40-11:20
References
1. Algorithms: Dasgupta, Papadimitriou, Vazirani [DPV]
2. Introduction to Algorithms: Cormen, Leiserson, Rivest, Stein (CLRS)
3. Algorithm Design: Kleinberg, Tardos (KT)
Grading: Home works and Class tests (20%), Mid Term (30%), End Term (50%)
Class 01 (Jan 10): Introduction. Sorting: Insertion Sort. Discussion on upper bounds and Lower bounds. Comparison model for sorting. Lower bound of sorting, lower bound for finding maximum [Read Notes by Arvim Blum 1.1- 1.3, 2.1-2.3, 2.5.1; CLRS 2.1]
Class 02 (Jan 12): Proving correctness of algorithms: Loop Invariants, correctness of Insertion sort. More on lower bounds: Exchange model for sorting, lower bound for sorting in the exchange model [ Read Notes by Arvim Blum 2.4, CLRS 2.1]
Class 03 (Jan 17): Linear time sorting algorithms: Counting Sort, Radix Sort, Bucket Sort [Read CLRS Chapter 8]
Class 04 (Jan 19): Divide and Conquer: Revisiting Merge Sort, iterative version of merge sort, Divide and Conquer Recurrences [Read DPV 2.2, 2.3, KT 5.1]
Class 05 (Jan 24): Divide and Conquer: Binary Search, Finding Inversions, Unimodal Max (Read class notes and KT 5.3)
Class 06 (Feb 2): Selection and Median Finding (Read CLRS 9.1, 9.2, KT 13.5)
Class 07 (Feb 07): Worst case linear time selection (Read CLRS 9,3)
Class 08 (Feb 09): Quicksort and its analysis (Read CLRS 7, KT 13.5)
Class 09 (Feb 14): Karatsuba Multiplication, Strassens Method of Matrix Multiplication, Polynomials: Evaluation, Multiplication, Addition; Polynomial representations [Read Notes, KT 5.5, CLRS 30]
Class 10 (Feb 16): Fast Fourier Transform and polynomial multiplication [Read class notes and CLRS 30]
Class 11 (Feb 21): Introduction to Graph Algorithms: Graph representations [Read CLRS 22.1, 22.2]
Class 12 (Feb 22): Breadth First Search, Testing Bipartiteness [Read CLRS 22.2, KT 3,2, 3.3, 3.4]
Class 13 (Feb 23): revision [ Practice Problems]
Class 14 (Mar 9): Depth first search [CLRS 22.3, DPV 3.2, 3.3]
Class 15 (Mar 14): Topological Sort, Strongly connected components [CLRS 22.4. 22.5]
Class 16 (Mar 16): Shortest Paths in Graphs: Dijkstra's Algorithm [Read KT 4.4, DPV 4.4]
Class 17 (Mar 21): Greedy Algorithms: Interval Scheduling, Huffman Codes[Read KT 4.1, 4.8]
Class18 (Mar 23): Greedy Algorithms: Huffman Codes, Minimum spanning trees, Cut property [Read KT 4.8, KT 4.5 ]
Class 19 (Mar 28): Kruskal's Algorithm, Disjoint set data structure [Read KT 4.5, 4.7; DPV 5.1; CLRS 23.2]
Class 20 (Mar 30): Analysis of disjoint set data structure [DPV 5.1.4, Wikipedia]
Class 21 (April 6): Prim's algorithm, Clustering. Introduction to Dynamic programing [Read KT 4.5, 4.7; DPV 5.1; CLRS 23.2]
Class 22 (April 11): Dynamic Programing: Weighted Interval Scheduling, Matrix Chain Multiplication [Read KT 6.1, 6.5]
Class 23 (April 11): Dynamic Programing: Subset sum and Knapsack Problems, Alignment and Edit Distance [Read KT 6.4, 6.6; DPV 6.3, 6.4]
Class 24 (April 13): Dynamic Programing: Shortest paths, Bellman Ford, Shortest Paths in DAGs [Read CLRS 24.1, 24.2, DPV 4.6, 4.7, 6.6]
Class 25 (April 14): All pairs shortest paths: Basic DP formulation, Matrix Multiplication, Floyd Warshall's Algorithm, Johnson's Algorithm [Read CLRS 25]
Class 26(April 18): (online class due to heatwave)NP Completeness [ boardwork,]