Instructor: Keerti Choudhary
Lecture Timing: Mon, Thurs 8:00-9:30 AM (Slot A), LH 316
Tutorial Timing: Mon, Tues, Fri 1:00-2:00 PM, LH 612
Reference Books:
Algorithm Design by Jon Kleinberg and Eva Tardos
Algorithms by Dasgupta, Papadimitriou, and Vazirani
TAs: Abhay Pratap Singh (cs5190414@cse.iitd.ac.in), Swarupananda Dhua (csz238079@cse.iitd.ac.in), Anand N Warrier (mcs232477@cse.iitd.ac.in).
Evaluation: The course evaluation policy is:
Passing criteria: 30% in course total
Audit-pass criteria: 45% in course total
Acadmic Honesty: Cheating or allowing anyone to copy would lead to a penalty of one grade per quiz / exam.
| Lec. No. | Topic | Further reading |
|---|---|---|
| 01 | Introduction, Algorithmic paradigms (Divide and conquer, Dynamic programming, Greedy algorithms) | |
| 02 | Interval Selection Problem | |
| 03 | Job Scheduling with two servers, Quiz-0 | |
| 04 | Huffman Encoding | Length-limited Huffman encoding |
| 05 | Minimum Spanning Tree, Reverse Delete algorithm, Kruskal's MST algorithm, Union-Find data-structure | Union-Find in O(log* n) Time |
| 06 | Dijkstra's algorithm | |
| 07 | DFS, Computing Brdiges in a graph, Computing Topological ordering | |
| 08 | Randomized Search, Randomized Quick Sort | |
| 09 | Minimum Pairwise Distance, 2d-Dominating Set | |
| 10 | Polynomial Multiplication | |
| 11 | Polynomial Multiplication (contd.), Quiz-1 | |
| 12 | Order Satistics, Deterministic Quick Sort, Matrix Multiplication | |
| 13 | All-Pairs Reachability, All Pairs 2-Approximatie Distance Computation, Quiz-2 | |
| 14 | Dynamic programming, Edit Distance, 3-Partition problem | Approximate edit distance |
| 15 | Quiz-3 (Kanpsack Problem), Strategy games | |
| 16 | Longest Increasing Subsequence | |
| 17 | Bellman-Ford Algorithm, Floyd-Warshall Algorithm | Near linear time algorithm for SSSP |
| 18 | Rabin-Karp Algorithm | |
| 19 | Minor exam discussion, Hashing | |
| 20 | Perfect Hashing | |
| 21 | Network flows, Ford-Fulkerson Algorithm | |
| 22 | (s,t)-cuts, Max-Flow Min-Cut Theorem, Optimality of Ford-Fulkerson Algorithm | |
| 23 | Circulation Problem, Applications of Max-Flow Min-Cut Theorem | |
| 24 | Doubt clearing session: Flows, Circulation, Hashing | |
| 25 | Polynomial-Time Reductions | |
| 26 | Quiz-4 | |
| 27 | P, NP, and NP-Completeness, Cook-Levin's theorem | |
| 28 | Quiz-5, NP Completeness of 3SAT, Vertex Cover |