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.
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.

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)

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.