Algorithms
Instructor: Manoj Gupta

Assessment

Syllabus

The tentative list of topics covered are as follows:

Thanks to Jaskirat Singh Maskeen for the code in the last column

Topic	SubTopic	Resource	Problems	Practice	Code
Greedy	Interval Scheduling	KT, Section 4.1	Problem Set 1	LeetCode	code
	Exchange Argument
	Example of Exchange Argument:Boat				code
	Candy		Problem Set 2	LeetCode	code
	Metro-I	KT, Section 4.5			code
	Metro-II		Problem Set 3	Leetcode	code
Disjoint Set Union	Introduction	KT Section 4.6			code
	Path Compression	JeffE, Chapter 17	Problem Set 4	LeetCode	code
Divide and Conquer	Maximum Overlap		Problem Set 5		code
	Majority			LeetCode	code
	Median of Medians	JeffE, Section 1.8		LeetCode	code
	Closest Pair	KT, Section 5.4			code
	Master's theorem
Fast Fourier Transform	FFT Part 1	KT, Section 5.6, Jeff Erickson FFT notes		LeetCode	code
	FFT, Part 2				code
	FFT, Part 3
	FFT, Part 4
	Applications of FFT		Jeff Erickson FFT notes		code
Dynamic Programming	Pingala	JeffE, Section 5.1	Problem Set 6		code
	Weighted Scheduling	KT, Section 6.2		LeetCode	code
	Edit Distance	KT, Section 6.6			code
	Marathon Runner				code
	Negative Weight Shortest Path	KT, Section 6.10			code
Flow	Introduction	KT, Section 7.1	Problem Set 7		code
	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	Pdf

Please read the IIT Gandhinagar Honor Code.

Algorithm Design, Kleinberg and Tardos. 1st Ed, Pearson.
Algorithms Notes, Jeff Erickson.
Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Vijay Vazirani, McGraw Hill.
The Design of Approximation Algorithms by David P. Williamson and David B. Shmoy