CS60086 Selected Topics in Algorithms 2026

CS60086 Selected Topics in Algorithms

Instructor:

Palash Dey

Teaching Assistants:

Ashlesha Hota

Course overview:

This will cover some advanced algorithms including combinatorial optimization, approximation algorithms, randomized algorithms, parameterized algorithms, etc.

Classes:

Venue: CSE-107.

Timings: Wednesday 11-11:55 AM, Thursday 12-12:55 PM, Friday 8-8:55 AM,

Extra slot: Thursday 6-7 PM.

Grading:

Attendance: 10%, Assignments: 10%, Class tests: 20%, Mid-term: 30%, Final: 30%

Announcements:

First class test will be on January 30, 2026. The question paper with solution sketch is here.
Midsem question paper: here.
Second class test will be on March 27, 2026 during class hours. The question paper is here.
For registering in this subject, (i) you should be a CS student, (ii) your current CGPA should be at least 8.7, and (iii) you should apply for this subject in erp by December 30.
We will assume knowledge of Algorihtms II.
First class will be on January 7, 2026 in CSE-107.

Assignments:

Practice Problems on Gomory-Hu tree. Deadline: January 15, 2026.
Practice Problems on Maximum Matching and Matroid. Deadline: January 22, 2026.
Practice Problems on Polytope, LP Duality, and Complementary Slackness. Deadline: February 20, 2026.
Practice Problems on Total Dual Integrality and Total Unimodularity. Deadline: March 20, 2026.
Practice Problems on Primal Dual Approximation Algorithms. Deadline: March 30, 2026.
Practice Problems on FFT and Dynamic Programming. Deadline: April 11, 2026.

Lectures: lecture notes

Week 1	Gomory-Hu Tree (reference: lecture notes)
Week 2	Edmond's Blossom Algorithm (reference: lecture notes) Introduction to Matroid Equivalence of Matroid and Greedy Algorithm (reference: CCPS book)
Week 3	Matroid Intersection Problem: Algorithm and Application (reference: CCPS book)
Week 4	Doubt-Clearing Class Introduction to Polytope First Class Test
Week 5	Bipartite Matching Polytope Matching Polytope LP Duality Complementary Slackness (reference: lecture notes and CCPS book)
Week 6	Total Dual Integrality (reference: lecture notes and CCPS book)
Week 7	Total Unimodilarity Min Cost Flow to Transshipment Reduction Primal Algorithm for Transshipment (reference: lecture notes and CCPS book)
Week 8	Primal-Dual Algorithm for Transshipment Scaling Trick Primal-Dual Approximation Algorithm: Set Cover, Feebdack Vertex Set (reference: WS book)
Week 9	Primal-Dual Approximation Algorithm for Generalized Steiner Forest and Facility Location Problem (reference: WS book)
Week 10	DFT and FFT (reference: CLRS book) Branching Technique for Designing Exact Exponential Algorithms: Independent Set, k-SAT Dynamic-Programming for Designing Exact Exponential Algorithms: Job Scheduling, Chromatic Number, Set Cover (reference: FK book)

References:

Combinatorial Optimization by Korte and Vygen.
Combinatorial Optimization: Polyhedra and Efficiency by Alexander Schrijver.
Combinatorial Optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver.
The Design of Approximation Algorithm by David P. Williamson David B. Shmoys. You can download free version here.
Approximation Algorithms by Vijay V Vazirani. You can download free version here.
Exact Exponential Algorihtms by Fedor V. Fomin and Dieter Kratsch.
Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. You can download free version here.