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:
Assignments: 20%, Mid-term: 30%, Final: 50%

Announcements:

We will assume knowledge of Algorihtms II.
First class will be on January 8, 2024 in CSE-120.

Assignments:

Assignment 1. Deadline: February 3, 2025. Submit your solution here
Assignment 2. Deadline: February 13, 2025. Submit your solution here
Mid-semester examination is scheduled on February 18 from 9 AM to 11 AM in CSE-107
Assignment 3. Deadline: March 21, 2025. Submit your solution here
Assignment 4. Deadline: March 28, 2025. Submit your solution here
Assignment 5. Deadline: April 4, 2025. Email your solution to the TA.
Assignment 6. Deadline: April 11, 2025. Email your solution to the TA.
Assignment 7. Deadline: April 18, 2025. Email your solution to the TA.

Lectures: lecture notes

Week 1	Jan 8	Edmond's Blossom Algorithm (reference: lecture notes)
	Jan 9
	Jan 10
Week 2	Jan 15	Gomory-Hu Tree (reference: part 1, part 2; this; CCPS book) Introduction to Matroid (reference: CCPS book)
	Jan 16
	Jan 17
Week 3	Jan 22	Matroid Intersection problem (reference: CCPS book) Introduction to Polytope
	Jan 23
	Jan 24
Week 4	Jan 29	Perfect Bipartite Matching Polytope Half-Integral Perfect Matching Polytope Max-weight Matching to Max-weight Perfect Matching Reduction Perfect Matching Polytope Separation Oracle for Perfect Matching Polytope (reference: CCPS book; this)
	Jan 30
	Jan 31
Week 5	Feb 5	Totally Unimodular Matrix (reference: CCPS book; this and this) LP-Duality, Complementary Slackness (reference: WS book)
	Feb 6
	Feb 7
Week 6	Feb 12	Min-Cost Flow Primal Algorithm Primal-Dual Algorithm (reference: lecture notes)
	Feb 13
	Feb 14
Week 7	Mar 5	Scaling Technique Primal-Dual Approximation Algorithm: Set Cover Feedback Vertex Set Generalized Steiner Tree (reference: lecture notes, WS book)
	Mar 6
	Mar 7
Week 8	Mar 12	Uncapacitated Metric Facility Location (reference: WS book) Exact Exponential Algorithm: Dynamic Programming Algorithm for TSP (reference: FK book)
	Mar 13
	Mar 14
Week 9	Mar 19	Dynamic Programming Algorithm for Job Scheduling, Chromatic Number, Set Cover, Dominating Set. Branching Algorithm for Independent Set (reference: FK book)
	Mar 20
	Mar 21
Week 10	Mar 26	Inclusion-Exclusion Based Algorithm for Hamiltonian Path, Counting Number of Perfect Bipartite Matching Bin Packing, Covering, Partition, Chromatic Number (reference: FK book)
	Mar 27
	Mar 28
Week 11	Apr 2	Fast Subset Convolution Partition, Chromatic Number, Chromatic Polynomial (reference: FK book)
	Apr 3
	Apr 4
Week 12	Apr 9	Fast Fourier Transform (reference: CLRS book) Streaming Algorithms: Misra-Gries Algorithm Reference: this
	Apr 11
Week 13	Apr 16	Markov Inequality Chebyshev Inequality Chernoff Bound (reference: this) Frequency Estimation in Turnstile Model: Count-Median Sketch Reference: this
	Apr 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.
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.