Instructor: Keerti Choudhary
Lecture Timing: Tues, Wed, Fri 10:00-11:00 AM
Tutorial Timing: Mon, Tues, Thurs, Fri 1:00-2:00 PM
Textbooks:
Algorithm Design by Jon Kleinberg and Eva Tardos
Algorithms by Dasgupta, Papadimitriou, and Vazirani
TAs: Prashant Agrawal (2018CSZ8011), Prashant Kumar (2020ANZ8488), Rahul Kanyal (2020CSZ8506), Harkirat Singh Dhanoa (2017CS50408), Siddhant Mago (2017CS50419), Sachin Singh (2021MCS2147), Kashish Jain (2021JCS2259), Animesh Singh Parihar (2021JCS2235).
Evaluation: The course evaluation policy is:
Acadmic Honesty: Cheating or allowing anyone to copy in quizzes, exams, or assignments would lead to strict disciplinary action.
| Lec. No. | Date | Topic |
|---|---|---|
| 01 | 10 August | O(), Omega(), Graphs, Course Policy |
| 02 | 11 August | Job Scheduling – Greedy Algorithm |
| 03 | 13 August | Minimum Spanning Tree |
| 04 | 17 August | Minimum Spanning Tree (contd..) |
| 05 | 18 August | Union Find and its application in computing MST |
| 06 | 21 August | Hufmann Encoding |
| 07 | 24 August | Hufmann Encoding (contd..) + BFS |
| 08 | 25 August | DFS and Bi-connectivty |
| 09 | 27 August | DFS and Bi-connectivty |
| 10 | 31 August | Quiz 1 + Strong-connectivity |
| 11 | 01 September | DFS and Strong-connectivity |
| 12 | 03 September | SCC (contd..) + Longest common subsequence |
| 13 | 07 September | LCS + Edit distance |
| 14 | 08 September | Floyd-Warshall Algorithm + Edit distance |
| 15 | 10 September | String Matching (Knuth-Morris-Pratt Algorithm) |
| 16 | 14 September | String Matching (contd..) |
| 17 | 15 September | Quiz 2 + Bellman-Ford Algorithm |
| 18 | 17 September | Quiz 1 and 2 discussion |
| 19 | 24 September | Computing Majority |
| 20 | 28 September | Computing Median, Deterministic Quick Sort (Divide and Conquer) |
| 21 | 29 September | Closest Pair of Points (Divide and Conquer) |
| 22 | 01 October | Matrix multiplication, Transitive closure |
| 23 | 05 October | Polynomial product |
| 24 | 06 October | Polynomial product (contd..) + DFT and FFT |
| 25 | 12 October | Master Theorem + Integer Product |
| 26 | 13 October | Universal Hashing |
| 27 | 20 October | Universal Hashing (contd..) |
| 28 | 22 October | Rabin-Karp Algorithm for Pattern Matching |
| 29 | 23 October | Max-Flow, Residual Graph |
| 30 | 26 October | Ford-Fulkerson Algorithm for Max-Flow |
| 31 | 27 October | Max-Flow Min-Cut Theorem, Applications of Max-Flow |
| 32 | 29 October | Quiz 3 + P and NP classes |
| 33 | 02 November | NP-Completeness, Polynomial time reductions |
| 34 | 03 November | NP-Completeness (contd..) |
| 35 | 09 November | Approximation Algorithms |
| 36 | 10 November | Approximation Algorithms (contd..) |