CS60086 Selected Topics in Algorithms 2025

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-119.
Timings: Wednesday 11-11:55 AM, Thursday 12-12:55 PM, Friday 8-8:55 AM,
Extra slot: Wednesday 5:30-6:30 PM in CSE-119.

Grading:
Two Class tests: 10% each, Mid-term: 30%, Final: 50%

Announcements:

First class test is scheduled on Jan 31 from 8 AM in CSE-119.
We will assume knowledge of Algorihtms II.
First class will be on January 8, 2024 in CSE-120.

Lectures:

Week 1	Jan 8	Edmond's Blossom Algorithm (reference)
	Jan 9
	Jan 10
Week 2	Jan 15	Gomory-Hu Tree (reference: part 1, part 2; this; CCPS book) Matroid (reference: CCPS book)
	Jan 16
	Jan 17

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