Classes: Tuesday 14:15-16:00, Thursday 11:15-13:00
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 09): Introduction. Sorting: Insertion Sort. Running Time. Proving Correctness of Algorithms: Loop Invariants. RAM Model. Asymptotic Notations. [Read CLRS 2.1, 2.2, 3.1]
Class 02 (Jan 11): Algorithms to Add, Multiply, Divide. Modular arithmetic. Modular exponentiation [ Read DPV 1.1, 1.2]
Class 03 (Jan 16): Euclid's Algorithm, Extended Euclid's Algorithm. Modular Inverse. Motivation for Randomization. Fermat's Primality Test [Read DPV 1.2, 1.3]
Class 04 (Jan 19): Divide and Conquer: Karatsuba Multiplication, Merge Sort [Read DPV 2.1, CLRS 2.3.1, KT 5.1]
Class 05 (Jan 23): Divide and Conquer: Divide and Conquer Recurrences, Masters Theorem, Binary Search, Finding Inversions (Read class notes, DPV 2.2, KT 5.3)
Extra Class(Jan 24): Implementation Issues in Arithmetic. Miller Rabin Test. [Read HBoAC Sec 14.2.2, 14.2.3]
Class 06 (Jan 25): The selection problem [Read KT 13.5]
Class 07 (Jan 30): Linear time select [Read CLRS 9.3]
Class 08 (Feb 01): Quicksort and its analysis [Read CLRS 7]
Class 09 (Feb 06): Heapsort and its analysis. Heap as a priority queue [Read CLRS 6]
Class 10 (Feb 08): Lower Bounds: Lower bounds for comparison based sorting, sorting in the exchange model, lower bound for finding maximum, Adversary arguments for lower bounds [Read Notes by Arvim Blum 2.1-2.5, read notes by Jeff Erricson 12.2-12.6 ]
Class 11(Feb 13): Adversary argument for lower bound on Sorting. Linear time sorting: Counting Sort, Bucket Sort [Read Class Notes and CLRS Chapter 8]
Class 12 (Feb 15): Strasen's method for Matrix Multiplication. Polynomials: Representation, Evaluation, Addition, Multiplication [Read Class Notes, DPV 2.5, 2,6, CLRS 30]
Class 13 (Feb 20): The Fast Fourier Transform. Fast polynomial multiplication [Read class notes and CLRS 30]
Class 14 (Feb 21): Revision and problem solving.
Class 15 (Mar 05): Graph Representations; Breadth First Search. [Read CLRS 22.1, 22.2, KT 3,2, 3.3, 3.4 ]
Class 16 (Mar 07): Depth First Search; Topological Sorting. [CLRS 22.3, 22.4, DPV 3.2, 3.3 ]
Class 17 (Mar 14): Strongly connected components [CLRS 22.5, Notes by David Wagner]
Class 18 (Mar 21): Shortest Paths in Graphs: Dijkstra's Algorithm [Read KT 4.4, DPV 4.4]
Class 19 (Mar 22): Greedy Algorithms: Interval Scheduling and Interval Partitioning Problems [Read KT 4.1]
Class 20 (Mar 28): Greedy Algorithms: Huffman Code [Read KT 4.8]
Class 21 (Apr 02): Greedy Algorithms: Minimum Spanning Trees: Kruskal's and Prims Algorithms [Read KT 4.5, 4.6]
Class 22 (Apr 05): Implementing Kruskal's Algorithm; Disjoint Set Data Structures [Read DPV 5.1; CLRS 23.2 ]
Class 23 (Apr 09): Analysis of Disjoint Set Data Structures; Maximum spacing Clustering [Read Class notes DPV 5.1.4, Wikipedia; KT 4.7 ]
Class 24 (Apr 12): Dynamic Programming: Weighted interval scheduling, matrix chain multiplication [Read KT 6,1,CLRS 15.2]
Class 25 (Apr 16): Dynamic Programming: Knapsack problem. Edit distance, longest common sub-sequence [Read KT 6,4, 6.6, DPV 6.3, 6.4; CLRS 15.4]
Class 26 (Apr 18): Dynamic Programming: Shortest Paths: Bellman Ford, All pair shortest paths: Matrix Multiplication, Floyd Warshall, Johnson[Read KT 6,8; CLRS 24.1. 25.1, 25.2, 25.3]
Class 27 (Apr 19):Review of P, NP, NP-complete, NP-hard. Introduction to approximation algorithms [Read class notes, relevant parts of Gomes, Williams]
Programing Assignment: Submit within June 5, 2024. Submission instructions in the document.