Winter 2013

Instructors

Debajyoti Bera
B204, Academic Block
Office Hours:
11:30-12:30 on T, Th
(by prior email appt.) 4-5 on W

Rajiv Raman
B202, Academic Block
Office Hours:
12-1 on M
10-11 on T

Availability outside these hours is not guaranteed. Take prior appointment over email if necessary.
 Teachings Assistants
  1. Monalisa Jena
    (lead TA)
    2nd Floor B-wing PhD Lab

  2. Parikshit Maini
  3. Shilpi Jain
  4. Aakarsha Agarwal
  5. Anil Sharma
  6. Garvita Bajaj
  7. Megha Gupta


Textbook (KT)
Algorithm Design

by

Jon Kleinberg, Éva Tardos

Reference (CLRS)
Introduction to Algorithms (3rd Ed.)
by
Thomas Cormen, Charles Leiserson, Ron Rivest, Clifford Stein
Lecture Hours
M 11-12 @ C11
T 9-10 @ C11
Th 2-3 @ C11
Tutorial Hours
W 9-10:30
Gp1 - C22
Gp2- C23
Gp3 - C24
Gp4 - C03
Lab Hours
Slot A - T 11-1
Slot B - T 2-4

All queries, discussions must happen on Piazza! Please sign up for Piazza account. For specific problems, you may email the lead TA (and CC one of the instructors).

Tests
  1. Test1 - 6th Feb 9-10:30
Lecture Schedule
(KT-x will mean Chapter x from the textbook, CLRS-y will mean Chapter y from Reference Book)
  1. Introduction. Stable Marriage Problem. (KT-1).
  2. Stable Marg.
  3. Stable Marg.
  4. Asymptotic Notation (KT-2)
  5. Asymp. Notn.
  6. Runtime Analysis (KT-2 Exercise)
  7. Heaps (KT-2.5)
  8. Heaps
  9. Graphs (KT-3)
  10. BFS, DFS
  11. Applications of BFS/DFS
  12. Connected components and runtime analysis of BFS/DFS
  13. Connectivity in directed graphs
  14. Topological Ordering
  15. Greedy algorithm (KT-4) - interval scheduling
  16. Interval scheduling
  17. Interval scheduling
  18. Shortest Path - Dijkstra
  19. (4/3) Binary search trees and red-black trees.(CLRS-12,13)
  20. (5/3) Insertion in Red-black trees. (CLRS 13)
  21. (7/3) Deletion in Red-black trees (CLRS 13)
  22. (11/3) Augmented Red-black trees (CLRS 14)
  23. (12/3) Augmented Red-black trees (CLRS 14)
  24. (14/3) Divide and Conquer: Recurrences + closest pair
  25. (18/3)Cancelled.
  26. (19/3) Divide and Conquer:Closest Pair
  27. (20/3) Divide and Conquer: Integer Multiplication
  28. (21/3) Dynamic Programming: Wt. Interval Scheduling
  29. (1/4) Dynamic Programming: Wt. Interval scheduling
  30. (2/4) Dynamic Programming: Knapsack
  31. (4/4) Dynamic Programming: Knapsack+Bellman-ford
  32. (8/4) Dynamic Programming: Bellman-ford
  33. (9/4) Dynamic Programming: Bellman-ford (potentials + intractability)
  34. (11/4) Reductions: introduction
  35. (15/4) Reductions: basic examples - indep. set to vertex cover, etc.
  36. (16/4) Reductions: SAT to Independent Set, NP-completeness.
  37. (18/4) NP-completeness.