Schedule

Instructors		Abhijit Das and Arobinda Gupta
Timing		Lecture hours: Mon 03:00pm–05:00pm †, Tue 02:00pm–04:00pm [Slot U4] † (Doubt-clearance and tutorial sessions)
Venue		Online
Teaching Assistants		Atrayee Majumder, Bajaru Sashank Srivardhan, Dewang Modi, Praagy Rastogi, Sanket Rajendra Meshram

Notices and Announcements

August 08, 2021

The two theory teachers will handle mutually disjoint topics. The recorded videos will be posted, and the links will be supplied in this page. Meeting details for doubt clearance and tutorials will be sent to the students before the sessions.

Coverage

Amortization	Week 1 (Aug 10 – Aug 13)
	Analysis techniques with examples: Aggregate method, accounting method, and potential method.	Part 1 | Part 2 [slides]
	Query form
Amortization Graph Algorithms	Week 2 (Aug 16 – Aug 20)
	Amortized data structures: Fibonacci heaps. Network flow: Definition, applications, Ford–Fulkerson algorithm. (First 24 minutes of Part 2)	Part 1 | Part 2 [slides] Part 1 | Part 2 [slides]
	Query form
Graph Algorithms	Week 3 (Aug 23 – Aug 27)
	Network flow: Edmonds–Karp algorithm, push-relabel algorithm. Applications. (Last 24 minutes of Part 2)	Part 2 | Part 3 | Part 4 [slides]
	Query form
Graph Algorithms	Week 4 (Aug 30 – Sep 03)
	Weighted Bipartite Matching (Hungarian Algorithm) Stable Matching: Gale–Shaply algorithm	Part 1 | Part 2 [slides] Single part [slides]
	Query form
Geometric Algorithms	Week 5 (Sep 06 – Sep 10)
	Representation of points, lines, segments, and polygons. Basic calculations.	Single part
	Query form
Geometric Algorithms	Week 6 (Sep 13 – Sep 17)
	Convex hulls: Definition, lower bound, naive algorithms, Jarvis' march, Graham's scan, Preparata–Hong algorithm. Sweep paradigm: Line sweep (line-segment intersection).	Part 1 | Part 2 Part 1
	Query form
Geometric Algorithms NP-completeness	Week 7 (Sep 20 – Sep 24)
	Sweep paradigm: Ray sweep (visibility polygon). Voronoi diagrams: Definition, applications, size, naive algorithm, Fortune's line-sweep algorithm. Complexity classes P and NP, nondeterministic algorithms.	Part 2 Single part Single Part
	Query form
NP-completeness	Week 8 (Sep 27 – Oct 01)
	Polynomial-time verifiabiity, polynomial-time reduction. NP-hard and NP-complete problems, SAT, CNFSAT. Examples of NP-complete problems	Single part Single part Part 1
	Query form
NP-completeness	Week 9 (Oct 04 – Oct 08)
	Examples of NP-complete problems. Miscellaneous topics: Easy instances and easy problems, the class NP-Hard.	Part 2 Single part
	Query form
Approximation Algorithms	Week 10 (Oct 18 – Oct 22)
	Basic concepts, approximation ratio, minimum vertex cover. Minimum set cover. Euclidean TSP. Inapproximability. Use of linear programming. Polynomial-time approximation schemes.	Single part Single part Single part
	Query form
Randomized Algorithms	Week 11 (Oct 25 – Oct 29)
	Monte Carlo algorithms. Primality testing. Karger and Karger–Stein algorithms. Las Vegas algorithms. Randomized data structures.	Single part Single part Single part [slides]
	Query form
Branch-and-bound Algorithms	Week 12 (Nov 01 – Nov 05)
	Backtracking, Pruning, Examples.	Part 1 | Part 2 [slides]
	Query form

Books and References

• Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, MIT Press/McGraw-Hill, 2009.
• Juraj Hromkovič, Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, Second Edition, Springer-Verlag, 2004.

Tests

• First Test: 07-Sep-2021
• Second Test: 05-Oct-2021
• Third Test: 16-Nov-2021

Previous course page: 2020