Instructor Debajyoti Bera  dbera@iiitd.ac.in Office hours: stop by if door is open OR take appointment by email TA Abhishek Kumar  Abhishek1101@iiitd.ac.in Office hours: Friday 3:45 to 5:45pm Komal Kochar  komal1006@iiitd.ac.in Komal Sachdeva  komal1007@iiitd.ac.in Praful Agrawal  prafula@iiitd.ac.in Lecture Monday 11:20 - 12:50  (CR4) Thursday 2:00 - 3:30 (CR4) Labs Wednesday 9:00 - 11:00

#### Textbook

• [KT] "Algorithm Design" by Kleinberg, Tardos
([KTY] denotes Chapter Y of this book.)
Though I do not teach using slides, I use them and you may refer to them. Slides.
• [SS] Lecture notes by Sandeep Sen
([SSZ] denotes Chapter Z of these notes.)
• [CLRS] "Introduction to Algorithms" by CLRS
([CLRSY] denotes Chapter Y of this book.)

#### Lecture Schedule

 Lec. Date Chapter/Source Topic 1. 2/1 KT1.1 Stable Marriage Problem 2. 5/1 KT2.1 SS1.3 Model of computation and analysis 3. 9/1 KT2.2 SS1 Model of computation and analysis 4. 12/1 (recap) Analysis and Recurrences 5. 16/1 (recap) Recurrence Relations 6. 19/1 KT2.5 Heaps, Priority Queue 7. 23/1 KT3.1 KT3.2 Graphs, BFS 8. 30/1 KT3.2-3.3 DFS, Connected Component 1/2 Quiz 1 9. 2/2 KT3.5-3.6 Directed graph, Topological sort 10. 6/2 KT3.6 CLRS12.1 Topological sort Binary Search tree 11. 9/2 CLRS12.2 12.3 Binary Search tree 12. 13/2 CLRS13.1 13.2, 14.1 Red Black tree Augmented Data Structure 13. 16/2 CLRS13.3 KT3.4 Red Black tree insertion Testing bipartiteness 22/2 Midsem exam 14. 27/2 KT4.1,4.2 Greedy algorithm 15. 1/3 KT4.4 Shortest Paths (Kruskal) 16. 12/3 KT4.5 Minimum Spanning Tree 17. 15/3 MST - Reverse Delete MST - Boruvka Shortest Path in DAG 18. 19/3 KT6.1 CLRS Dynamic Programming Longest Common Subseq 19. 22/3 KT6.8 Bellman Ford All pairs shortest path 20. 26/3 KT6.10 Negative cycles in a graph 28/3 Quiz 2 21. 28/3 KT5.3,5.5 Divide and conquer 22. 2/4 KT8.1 Reduction 23. 5/4 KT8.1 Reduction 24. 9/4 KT8.2 3SAT <= IS 25. 12/4 KT8.3,8.4 P, NP and NP-Complete 26. 16/4 KT Ch-8 NP-Completeness