CS60086 Selected Topics in Algorithms

Instructor:

Palash Dey

Teaching Assistants:

Ishan Goel

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

Classes:
Venue: CSE-120.
Timings: Wednesday 11-11:55 AM, Thursday 12-12:55 PM, Friday 8-8:55 AM,
Extra slot for class tests and tutorial: Thursday 6:15-7:15 PM.

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

Announcements: Lectures:
Week 1 Jan 3 Introduction to Linear Programming (reference: Appendix A from WS book)
Mincost Perfect Bipartite Matching (reference)
Jan 4
Jan 5
Week 2 Jan 10 Mincost Flow: Primal Algorithm (reference)
Primal-dual Algorithm (reference)
Jan 11
Jan 12
Week 3 Jan 17 Totally Unimodular Matrix (reference)
Matroid (reference: CCPS Book)
Jan 18
Jan 19
Week 4 Jan 24 Matroid Intersection Algorithm (reference: CCPS Book)
First Class Test
Jan 25
Week 5 Jan 31 Primal-dual technique for approximation algorithm:
Set cover, feedback vertex set (reference: WS Book)
Feb 1
Feb 2
Week 6 Feb 7 Primal-dual technique for approximation algorithm:
Generalized Steiner Tree (reference: WS Book)

Deterministic rounding technique:
Prize Collecting Steiner Tree (reference: WS Book)
Feb 8
Feb 9
Week 7 Feb 28 Deterministic rounding technique:
Facility Location
Derandomization using Conditional Expectation
Randomized rounding technique: Max-SAT (reference: WS Book)
Feb 29
Mar 1
Week 8 Mar 6 Randomized rounding technique:
Max-SAT, Prize-Collecting Steiner Tree, Facility Location
(reference: WS Book)
Mar 7
Mar 8
Week 9 Mar 13 Institute Class Suspension
Mar 14 Polynomial Identity Testing, Karger's Min-Cut Algorithm
(reference: here)
Mar 15
Week 10 Mar 20 Second Class Test
Mar 21 Introduction of Fixed Parameter Tractability
Kernelization: Quadratic and Linear Kernels for Vertex Cover
(Crown Decomposition and LP based)
Half Integrality of Vertex Cover Polytope
Mar 22
Week 11 Mar 27 Kernelization: Feedback Arc Set on Tournaments

Bounded search for Designing FPT Algorihtms: Vertex Cover
Mar 28
Mar 29 Institute Holiday (Good Friday)
Week 12 Apr 3 Vertex Cover Parameterized by above LP, MM

Odd Cycle Transversal
Apr 4
Apr 5
Week 13 Apr 10 Almost 2SAT

Closest String
Apr 11 Institute Holiday
Apr 5 Doubt Clearing Session and Tutorial


Practice Problems:
  1. Practice problem set (week 1): here.
  2. Practice problem set (week 2): here.
  3. Practice problem set (week 3): here.
  4. Practice problem set (week 4): here.
  5. Practice problem set (week 5): here.
  6. Practice problem set (week 6-8): here.
  7. Practice problem set (week 9): here.
  8. Practice problem set (week 10): here.


References:
  1. Combinatorial Optimization by Korte and Vygen.
  2. Combinatorial Optimization: Polyhedra and Efficiency by Alexander Schrijver.
  3. Combinatorial Optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver.
  4. The Design of Approximation Algorithm by David P. Williamson David B. Shmoys. You can download free version here.
  5. Approximation Algorithms by Vijay V Vazirani. You can download free version here.
  6. 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.