ADA W2012


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