Schedule

Instructors		Abhijit Das and Arobinda Gupta
Timing		Lecture hours: Mon 03:00pm–05:00pm †, Tue 02:00pm–04:00pm [Slot U4], Wed 08:00pm–09:30pm [Slot U(A)] † (Doubt-clearance and tutorial sessions)
Venue		Online
Teaching Assistants		Aditya Rastogi, Aman Bansal, Kayastha Dhruv, Manthan Parashar, Nikhil Nayan Jha, Peruri V S L Hari Chandana

Notices and Announcements

August 16, 2020

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

Topic	Details	YouTube video
Week 1
Introduction	Course Introduction.	Single part (slides)
Amortization	Analysis techniques with examples: Aggregate method, accounting method, and potential method. Amortized data structures: Fibonacci heaps.	Amortized Analysis: Part 1 | Part 2 (slides) Fibonacci Heaps: Part 1 | Part 2 (slides)
Query form
Week 2
Graph Algorithms	Network flow: Definition, applications, Ford–Fulkerson, Edmonds–Karp, and push-relabel algorithms.	Part 1 | Part 2 | Part 3 | Part 4 (slides)
Query form
Week 3
Graph Algorithms	Weighted Bipartite Matching (Hungarian Algorithm) Stable Matching: Gale–Shaply algorithm	Part 1 | Part 2 (slides) Single part (slides)
Geometric Algorithms	Representation of points, lines, segments, and polygons. Basic calculations.	Single part
Query form
Week 4
Geometric Algorithms	Convex hulls: Definition, lower bound, naive algorithms, Jarvis' march, Graham's scan, Preparata–Hong algorithm.	Part 1 | Part 2
Query form
Week 5
Geometric Algorithms	Sweep paradigm: Line-segment intersection, visibility polygon.	Part 1 (scribes) | Part 2 (scribes)
	Voronoi diagrams: Definition, applications, size, naive algorithm, Fortune's line-sweep algorithm.	Single part (scribes)
Query form
Week 6
NP-completeness	Complexity classes P and NP, nondeterministic algorithms	Single part (scribes)
	Polynomial-time verifiabiity, polynomial-time reduction.	Single part (scribes)
	NP-hard and NP-complete problems, SAT, CNFSAT.	Single part (scribes)
Query form
Week 7
NP-completeness	Examples: 3CNFSAT, DHamPath, Vertex-Cover, Clique, TSP, Longest-Path, Independent-Set	Part 1 (scribes) | Part 2 (scribes)
	Miscellaneous topics: Easy instances and easy problems, the class NP-Hard	Single part (scribes)
Query form
Weeks 8 and 9
Approximation Algorithms	Basic concepts, approximation ratio, minimum vertex cover. Minimum set cover. Euclidean TSP. Inapproximability. Use of linear programming. Polynomial-time approximation schemes.	Part 1 | Part 2 | Part 3 (slides)
Query form
Week 10
Randomized Algorithms	Monte Carlo algorithms: Fermat and Miller–Rabin primality tests, Karger and Karger–Stein algorithms for minimum cut. Las Vegas algorithms: Randomized quicksort, graph coloring, bit-vector search Relation between Monte Carlo and Las Vegas algorithms Randomized data structures: Bloom filters	Part 1 | Part 2 | Part 3 (slides)
Query form
Week 11
Branch-and-bound Algorithms	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

• Short Test 1 (21-Sep-2020)
• Long Test 1 (28-Sep-2021) [Solution]
• Programming Assignment 1 (Deadline: 27-Oct-2020)
• Short Test 2 (12-Oct-2020)
• Short Test 3 (19-Oct-2020)
• Programming Assignment 2 (Deadline: 10-Nov-2020) [Solution]
• Long Test 2 (02-Nov-2020)
• Short Test 4 (16-Nov-2020)
• Long Test 3 (18-Nov-2020)