Classes: Mondays and Wednesdays 09:20-11:05
Previous years question papers: Midterm- 2023, EndTerm-2023, Midterm-2024, Endterm-2024
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 06): Introduction. Sorting: Insertion Sort. Running Time. RAM Model. Asymptotic Notations. Computing Fibonnaci Numbers [Read CLRS 2.1, 2.2, 3.1, DPV 0.1, 0.2 ]
Class 02 (Jan 08): Algorithms to Add, Multiply, Divide. Modular arithmetic. Modular exponentiation, GCDs: Euclid's Algorithm, Extended Euclid's Algorithm, Multiplicative inverses modulo n [ Read DPV 1.1, 1.2, 1.3]
Class 03 (Jan 13): Motivation for Randomization. Fermat's Primality Test, Miller Rabin Test [Read DPV 1.2, 1.3]
Class 04 (Jan 15): Divide and Conquer: Karatsuba Multiplication, Merge Sort [Read DPV 2.1, CLRS 2.3.1, KT 5.1]
Class 05 (Jan 20): Divide and Conquer: Counting Inversions, Closest pair of points [ KT 5.3, KT 5.4]
Class 06 (Jan 27): Divide and Conquer: The selection problem [Read KT 13.5]
Class 07 (Jan 29): Worst case linear time select [Read CLRS 9.3]
Class 08 (Feb 03): Quicksort and its analysis [Read CLRS 7]
Class 09 (Feb 05): Introduction to lower bounds: Lower bounds for sorting in the comparison and exchange models. Lower bound for finding Max. [Read Notes by Arvim Blum 2.1-2.5, read notes by Jeff Erricson 12.2-12.6 ]
Class 10 (Feb 10): More lower bounds: Finding min and max. Linear time sorting: counting sort [ Read notes by Jeff Erricson 13.7. Read CLRS 8.2]
Class 11 (Feb 12): Linear time sorting: Bucket sort. Back to Divide and Conquer: Stassen's Matrix Multiplication. Polynomial evaluation: Horner's rule. Randomized algorithm to check if AB=C, for matrices A,B,C. [ Read CLRS 8.4, DPV 2.5, Class Notes]
Class 12 (Feb 17): Polynomial Multiplication and Fast Fourier Transform [ Read CLRS 30.1, 30.2]
Class 13 (Feb 19): Revision and some problem solving
Class 14 (Mar 03): Graph Representations; Breadth First Search. [Read CLRS 22.1, 22.2, KT 3,2, 3.3, 3.4 ]
Class 15 (Mar 05): Depth First Search; Topological Sorting. [CLRS 22.3, 22.4, DPV 3.2, 3.3 ]
Class 16 (Mar 10): Strongly connected components [CLRS 22.5, Notes by David Wagner]
Class 17 (Mar 12): Shortest Paths in Graphs: Dijkstra's Algorithm [Read KT 4.4, DPV 4.4]
Class 18 (Mar 17): Greedy Algorithms: Interval Scheduling [Read KT 4.1]
Class 19 (Mar 19): Greedy Algorithms: Interval Partitioning, Scheduling to minimize lateness [Read KT 4.1, 4.2]
Class 20 (Mar 24): Greedy Algorithms: Huffman Code [Read KT 4.8]
Class 21 (Apr 26): Greedy Algorithms: Finishing Huffman Codes. Minimum Spanning Trees: Cut property; Kruskal's and Prims Algorithms [Read KT 4.5, 4.6]
Class 22 (Apr 02): Greedy Algorithms: Finishing Minimum Spanning Trees: Implementing Kruskal's and Prims Algorithms [Read KT 4.5, 4.6]
Class 23 (Apr 07): Maximum separating clustering; Introduction to Dynamic Programing: Weighted Interval Scheduling [Read KT 4.7, 6.1, 6.2]
Class 24 (Apr 09): Dynamic Programing: Matrix Chain Multiplication, Subset sum and Knapsack problems [Read KT 6.4; DPV 6.4, 6.52; CLRS 15.2]
Class 25 (Apr 09): Dynamic Programing: Sequence alignment and edit distance, DP formulation of shortest paths: Bellman Ford Algorithm [Read KT 6.6, 6.8; DPV 6.3]
Class 26 (Apr 12): Bellman Ford; All Pairs Shortest Path: DP formulation, Matrix Multiplication, Ford Warshall, Johnson [Read KT 6,8; CLRS 24.1. 25.1, 25.2, 25.3 ]
Class 27 (Apr 16): NP Completeness: Decision problems, P, NP, polynomial time reducibility, NP hard, NP Complete [Read Class Notes; relevant portions from CLRS 34.1, 34.2, 34.3]
Class 28 (Apr 18): NP Completeness: Proving NP Completeness. Cook-Levin Theorem (statement only), SAT, 3SAT, INDEPENDENT SET, VERTEX-COVER, colorability [Read Class Notes; relevant portions from CLRS 34.1, 34.2, 34.3, KT 8.1, 8.2]
Programing Assignment.: Submit within May 27, 2025. Strictly follow the submission instructions.