CS31005 Algorithms II - Spring 2025

Instructor: Sudeshna Kolay and Palash Dey

Teaching Assistants: Swapnil Ghosh, Ashlesha Hota, Saideep Pandey, Abhishek Shaw, Dip Rajeshbhai Shambhvani

Course overview:
This is a second level algorithms course. We will cover the following topics: amortized analysis, Fibonacci heap, network flow, computational geometry, NP-completeness, approximation algorithms, randomized algorithms, and parameterized algorithms

Classes:
Venue: NC442 (for odd roll numbers) and NC443 (for even roll numbers)
Timings: Thursday 3-4:55, Friday 2-3:55 [slot V4]. Optional doubt-clearing session: Saturday (11-12) online.

Grading: Class test: 20%, Mid-term: 30%, Final: 50%

Announcements:

Practice Problems:


References:
  1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms.
  2. Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
  3. Jeff Erickson, Algorithms, 2019.
  4. Vijay V Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
  5. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry, Springer, 2008.
  6. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Parameterized Algorithms. You can download from here.
  7. Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms
  8. Eli Upfal and Michael Mitzenmacher, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis