Home
Courses

Data-Structures and Algorithms-II
Instructor: Manoj Gupta

Assessment

  • 60% :Exams

  • 40% : 4 Quiz (Max 3 out of 4)

Syllabus

The tentative list of topics covered are as follows:

  • Graph Algorithms

  • Divide and Conquer

  • Greedy

  • Dynamic Programming

  • Network Flow

  • NP Completeness

Schedule

Topic SubTopic Resource Problems Coding Tutorial
Greedy Interval Scheduling KT, Section 4.1 Problem Set 1 LeetCode
Exchange Argument
Example of Exchange Argument:Boat
Candy Problem Set 2 LeetCode
Metro-I KT, Section 4.5
Metro-II Problem Set 3 Leetcode
Disjoint Set Union Introduction KT Section 4.6
Path Compression JeffE, Chapter 17Problem Set 4 LeetCode
Divide and Conquer Maximum Overlap Problem Set 5
Majority LeetCode
Median of Medians JeffE, Section 1.8 LeetCode
Closest Pair KT, Section 5.4
Fast Fourier Transform FFT Part 1 KT, Section 5.6, Jeff Erickson FFT notes LeetCode
FFT, Part 2
FFT, Part 3
FFT, Part 4
Applications of FFT Jeff Erickson FFT notes
Dynamic Programming Pingala JeffE, Section 5.1 Problem Set 6
Weighted Scheduling KT, Section 6.2 LeetCode
Edit Distance KT, Section 6.6
Marathon Runner
Negative Weight Shortest Path KT, Section 6.10
Flow Introduction KT, Section 7.1 Problem Set 7
Implementation KT, Section 7.1
Proofs KT, Section 7.2
Improving Running Time KT, Section 7.3
Strongly Polynomial Time Algorithm JeffE, Section 23.6.2
Flow Applications Bipartite Matching, Mobile Towers, Menger's Theorem KT, Section 7.5,7.6 Problem Set 8
Circulation and its applications KT, Section 7.7,7.8
NP-Completeness P and NP KT, Section 8.1,8.2 Problem Set 9
More Reductions
NP Complete Problems KT, Section 8.3,8.4

Assignment

Assignment

Please read the IIT Gandhinagar Honor Code.

References

  • Algorithm Design, Kleinberg and Tardos [KT]

  • Algorithms Notes, Jeff Erickson. [JeffE]

  • Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Vijay Vazirani, McGraw Hill.

  • The Design of Approximation Algorithms by David P. Williamson and David B. Shmoy