CS31005 Algorithms II

CS31005 Algorithms II - Spring 2023

Instructor: Sudeshna Kolay and Palash Dey

Teaching Assistants: Ashutosh Kumar Singh, Ishan Goel, Parth Tusham, Akshat Singh Rathore, Pranav Rajput

Course overview:
This is a second level algorithms course. We will cover the following topics: amortized analysis, Fibonacci heap, network flow, computational geometry, NP-completeness, approximation algorithms, randomized algorithms, and parameterized algorithms

Classes: Venue: NC442 (for odd roll numbers) and NC443 (for even roll numbers) for regular classes and tutorials. CSE-107 for Saturday's doubt-clearing sessions.
Timings: Thursday (3-4:55 PM), Friday (2-3:55 PM) [slot V4], Saturday (10-11 AM) for doubt-clearing.

Students having doubts in understanding the concepts covered in the week are strongly encouraged to clear their doubts in Saturday's doubt-clearing sessions. No new problem or material will be discussed in Saturday's classes. If you have crystal-clear understanding of the concepts covered, then you may not come.

Grading: Class test: 20%, Mid-term: 30%, Final: 50%

Announcements:

First class will be on August 3.
First class test will be on September 8 from 6 PM in CSE department. Seating arrangement: here. Question paper: here.
Mid-semester examination will be on September 26. Question paper: here.
Second class test will be on October 17 from 6:30 PM in CSE department. Seating arrangement: here. Question paper: here.

Lectures:

Week 1	Aug 3	Amortized Analysis Fibonacci Heap	Reference: CLRS book
	Aug 4
Week 2	Aug 10	Fibonacci Heap Network Flow Ford Fulkerson Method Edmond Karp Algorithm Tutorial on amortization and Fibonacci heap	Reference: CLRS, KT books
	Aug 11
Week 3	Aug 17	Push-Relabel Algorithm	Reference: CLRS book Tim Roughgarden's Notes
	Aug 18	No Class (Institute Foundation Day)
Week 4	Aug 24	Application of Max-flow: Bipartite Matching, Hall's Theorem, Konig's Theorem. Blossom Algorithm Stable Matching Tutorial on maximum flow	Reference: CLRS, KT, JE books Blossom Algorithm Notes Notes on Hall's Theorem and Konig's Theorem Notes on Stable Matching (Chapter 11)
	Aug 25
Week 5	Aug 31	Computational Geometry: Line Segment, Convex Hull, Triangulation Tutorial on maximum flow	Reference: CLRS, BCKO books
	Sep 1
Week 6	Sep 7	No Class (Jasmasthami)
	Sep 8	Order Statistics, String Matching	Reference: CLRS book
Week 7	Sep 21	Randomized Algorithms: Karger's Algorithm Karger-Stein Algorithm Doubt-clearing session Tutorial on computational geometry	Section 2.5 from here
	Sep 22
Week 8	Sep 28	No Class (Institute Holiday)
	Sep 29	Lower Bound on Sorting NP-completeness	Reference: CLRS, KT books
Week 9	Oct 5	NP-completeness Self reduction Tutorial on NP-completeness	Reference: CLRS, KT books
	Oct 6
Week 10	Oct 12	Approximation Algorithms Tutorial on NP-completeness and Approximation Algorithm	Reference: CLRS, KT, Vazirani books
	Oct 13
Week 11	Oct 19	Doubt Clearing Session Tutorial on Approximation Algorithm	Reference: CLRS, KT books
	Oct 20
Week 12	Nov 2	Rancomized Approximation Algorithm for 3SAT Color Coding Technique: Longest Path FPT Algorithms Bounded Search Technique: Vertex Cover Iterative Compression Technique: Vertex Cover	Reference: CLRS, KT, and MFLDDMMS books
	Nov 3

Practice Problems:

Practice problem set on amortized analysis
Practice problem set on Fibonacci heap
Practice problem set on maximum flow
Practice problem set on push relabel algorithm
Practice problem set on computational geometry
Practice problem set on intractability
Practice problem set on more intractability and some approximation
Practice problem set on approximation algorithms
Practice problem set on FPT algorithms

References:

Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms.
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
Jeff Erickson, Algorithms, 2019.
Vijay V Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry, Springer, 2008.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Parameterized Algorithms. You can download from here.
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms
Eli Upfal and Michael Mitzenmacher, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis