CS60007 Algorithm Design and Analysis


Instructors:

 Palash Dey and Swagato Sanyal

Teaching Assistants:

 Ayan Chandra, Umang Chaturvedi, Prashant Chauhan, Subhrangsu Mandal, Anamitra Mani

Office Hours:

 Palash Dey: Wednesday 7-8 PM. Location: A-204 (Please drop me an email before meeting me.)
 Swagato Sanyal: Monday 6-7 PM. Location: CSE-304

 TAs: Wednesday 5-7 PM. Location: Subhrangsu in A-208, Ayan in 309, Anamitra and Umang in Student Lab 1 in Takshashila

Course overview:
 In this course, we will begin with familiarizing you with algorithm design techniques like dynamic programming, greedy algorithms etc. Our stress will be on formally proving the correctness and running time of our algorithms. We will spend substantial amount of time on discussing important graph algorithms like finding a shortest path between two vertices, all pair shortest path, maximum flow, and cut. We will provide an introduction to linear programming and duality theorems. We will then move on to NP-completeness and spend few lectures each in approximation algorithms and randomized algorithms.

Classes:
 Venue: NC332. Timings: Monday (12:00-12:55), Tuesday (10:00-11:55), Thursday (08:00-08:55)

Grading:
 Assignments - 20%, Midterm - 30%, Final - 50%

Announcements:
Question Papers:
Assignments:
Assignment 1 Deadline: 13 August, 2018 in the class Solution
Assignment 2 Deadline: 4 September, 2018 in the class Solution
Assignment 3 Deadline: 25 October, 2018 in the class Solution
Solution for Questions 21 and 22
Assignment 4 Deadline: 12 November, 2018 in the class Solution

Lectures:
Lectures Supplemetary Material Reference Reading
1. Greedy Algorithms: Interval Scheduling, Structure of Minimum Spanning Tree Structure of MST Chapters on Greedy Algorithms from CLRS and KT books
2. Greedy Algorithms (continued): Prim's algorithm for computing Minimum Spanning Tree of weighted graphs Proof of Correctness of Prim's Algorithm Chapter on Minimum Spanning Tree from CLRS
3. Greedy Algorithms (continued): Running Time of Prim's algorithm. Kruskal's Algorithm Proof of Correctness of Kruskal's Algorithm
4. Dynamic programming: Fibonacci number and matrix chain multiplication -- Chapters on Dynamic Programming from CLRS and KT books
5. Dynamic programming: Matrix chain multiplication (continued from lecture 4) --
6. Median Finding -- Chapter on Medians and Order Statistics from CLRS book
7. Median Finding cont., Dijkstra's Algorithm Supplementary for Dijkstra's Algorithm
Supplementary for Median Finding
Chapter on Single-Source Shortest Paths from CLRS book. The BFS viewpoint of Dijkstra's Algorithm is from Reference 3.
8. Bellman-Ford Algorithm -- Chapter on Single-Source Shortest Paths from CLRS book
9. Floyd Warshall Algorithm -- Chapter on All-Pairs Shortest Paths from CLRS book
10. Johnson's Algorithm --
11. Ford Fulkerson Algorithm: Proof of Correctness -- Tim Roughgarden's lecture note 1
Tim Roughgarden's lecture note 2
Jeff Erickson's lecture note which includes an example where Ford Fulkerson algorithm does not terminate
12. Finish Proof of Correctness of Ford Fulkerson Algorithm, Max Flow - Min Cut Theorem, Overview of Edmond-Karp Algorithm --
13. Finishing Edmond-Karp Algorithm. Push - Relabel Algorithm -- Tim Roughgarden's lecture note 3
Chapters on Maximum Flow from CLRS and KT books. Solve Exercise Problems (Specially from KT Book)
Current Fastest Algorithm for Computing Maximum Flow: here and here
This is fastest for some regime of capacity values
This was fastest for 15 years.
14. Push - Relabel Algorithm cont. --
15. Finishing Push - Relabel Algorithm --
16. Maximum Bipartite Matching using Max Flow, Hall's Theorem,
Karger's Algorithm for Finding Minimum Cut
-- Applications of Maximum Flow from Tim Roughgarden's lecture note 4
Karger's Algorithm from Jeff Erickson's lecture note
17. Amortized analysis: aggregate analysis. -- Chapter on Amortized analysis in the CLRS book.
18. Amortized analysis: accounting method and potential method. --
19. Amortized analysis: disjoint sets and Kruskal's algorithm, Linear programming, LP formulation of maximum bipartite matching. -- Chapter on data structures for disjoint sets in the CLRS book.
Page 25 onwards from this. Feel free to skip the proof of the lemma stated in page 27.
20. Linear Programming: Definitions and examples. Maximum biparitite matching. --
21. Linear Programming: Maximum biparitite matching continued. --
22. Linear Programming: Duality. -- Luca Trevisan's blog post on LP duality..
23. Linear Programming: Max-flow min-cut theorem using duality
NP-completeness: Decision problems, Karp reduction.
-- Max-flow min-cut theorem using LP duality,
Chapter on NP-completeness in the CLRS book.
24. NP-Completeness: Classes P and NP, NP-complete problems. -- Chapter on NP-completeness in the CLRS book.
25. Reduction of SAT to 3SAT -- SAT to 3-SAT Reduction
26. Reduction of 3SAT to Vertex Cover -- Notes by TB Schardl (MIT)
27. Reduction of 3SAT to Subset Sum -- CLRS book.
28. Approximation Algorithm for TSP Supplemental Material Section 31.2, 31.6, and 31.7 from Prof. Jeff Erickson's lecture notes
29. Randomized Approximation Algorithm for MAX3SAT Section 7.1 from here
Also see this
30. FPTAS for Subset Sum CLRS book.
31. FPTAS for Subset Sum cont., FPTAS vs EPTAS vs PTAS, No FPTAS for Set Cover
32. Overview of Local Search, Parameterized Algorithms, and Algorithmic Game Theory -- --

References:
  1. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
  2. Algorithm Design by Jon Kleinberg, Eva Tardos
  3. Algorithms by Dasgupta, Papadimitriou, and Vazirani
  4. Approximation Algorithms by Vijay V. Vazirani
  5. Randomized Algorithms by Rajeev Motwani, Prabhakar Raghavan
  6. Probability and Computing by Michael Mitzenmacher and Eli Upfal