CS31005 Algorithms II - Spring 2024

Instructor: Sudeshna Kolay and Palash Dey

Teaching Assistants: Ashlesha Hota, Aritra Mitra, Rohit Ranjan, Amit Kumar, Kushaz Sehgal

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) for regular classes and tutorials.
Timings: Thursday (3-4:55 PM), Friday (2-3:55 PM) [slot V4]. Optional doubt-clearing session: Saturday (11-12) in CSE-107.

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

Announcements:
Lectures:
Week 1 Jul 25 Amortized Analysis
Fibonacci Heap		 Reference: CLRS book
Jul 26
Week 2 Aug 1 Fibonacci Heap

Tutorial on amortization and Fibonacci heap

 Reference: CLRS, KT books
Aug 2
Week 3 Aug 8 Network Flow
Ford Fulkerson Method
Edmond Karp Algorithm
Reference: CLRS book
Aug 9
Week 4 Aug 15 Dinic's Algorithm

Tutorial on Max-flow
(up to Dinic's Algorithm)

 Reference: CLRS, KT, JE books
Aug 16
Week 5 Aug 22 Push-relabel Algorithm
Application of Max-flow:
Bipartite Matching, Hall's Theorem,
Konig's Theorem.		 Reference: CLRS, KT, JE books
Notes on Hall's Theorem and Konig's Theorem
Aug 23
Week 6 Aug 29 Stable Matching

Tutorial on max flow
(push relabel and applications)

 Reference: CLRS
Notes on Stable Matching (Chapter 11)
Aug 30
Week 7 Sep 5 Order Statistics
Sorting Lower Bound
String Matching		 Reference: CLRS, KT
Sep 6
Week 8 Sep 12 Doubt-clearing session

Tutorial on order statistics
and string matching

 Reference: CLRS
Sep 13
Week 9 Sep 26 Karger's Min cut
Karger-Stein Min cut		 Reference: here
Sep 27
Week 10 Oct 3 P vs NP, NP-completeness of
Circuit-SAT, CNF-SAT, 3SAT, Vertex Cover,
Clique, Independent Set		 Reference: CLRS, KT
Oct 4
Week 11 Oct 17 NP-completeness:
Hamiltonian Circuit, Subset Sum
Self reduction of SAT
Inapproximability of TSP
Oct 18
Week 12 Oct 24 No class due to anticipation of cyclone
Oct 25
Week 13 Oct 31 Institute holiday (Diwali)
Nov 1 Doubt-clearing session

Tutorial on NP Completeness
Week 14 Nov 8 Approx Algo for Vertex Cover
Approx Algo for Metric TSP
Approx Algo for Set Cover		 Reference: CLRS,

Vijay V Vazirani, Approximation Algorithms

David P. Williamson and David Shmoys,
The Design of Approximation Algorithms

Palash's notes (for method of conditional expectation): here
Palash's notes (Greedy set cover): here
Nov 9 Randomized Approx Algo for Max Cut
Deterministic Approx Algo for Max Cut
Randomized Approx Algo for 3SAT
Method of Conditional Expectation for Derandomization
Deterministic Approx Algo for 3SAT
Week 15 Nov 14 Doubt-clearing session

Tutorial on Approximation Algorithms
Nov 15 Institute holiday


Practice Problems:
  1. Practice problem set on amortized analysis
  2. Practice problem set on Fibonacci heap
  3. Practice problem set on maximum flow
  4. Practice problem set on push relabel algorithm
  5. Practice problem set on applications of flow
  6. Practice problem set on stable matching
  7. Practice problem set on order statistics and string matching
  8. Practice problem set on intractability
  9. Practice problem set on approximation algorithm


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