Assessment

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
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 17	Problem 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

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