Combinatorial Objects & Their Algorithmic Applications (CS6100)
Teaching Group
An Introductory Note
This course is supposed to be quite open ended so we will follow some flexibility with the contents we cover, and we can evolve them based on the interests as we progress. There are several combinatorial objects that find lots of application in designing algorithms in various paradigms like, Parameterized Algorithms, Approximation Algorithms, Streaming Algorithms and Dynamic Algorithms. Matroids and Greedoids are among such widely used combinatorial objects which also explain the inherent working of several greedy algorithm. The course will be focused on understanding these objects, algorithm for performing highly useful operations on them, and their applications. A large part of the course will be focused on understanding matroids from the algorithmic point of view. Then we will look at similar such results for other such highly useful combinatorial objects like greedoids and delta matroids. If time permits we will also go over some recently developed tools in algorithm design.
Textbooks
Some Practical Information
Tentative Timings (Slot H): Monday 14:00-15:15, Wednesday 15:30-16:45, and Thursday 17:00-17:50.
Room: CS 34.
Evaluation (tentative):
Expectations Regarding Academic Honesty And Usage of Inclusive Languages
- Instructor: Akanksha Agrawal
- Teaching Assistant: Vinod Shambhu Gupta
An Introductory Note
This course is supposed to be quite open ended so we will follow some flexibility with the contents we cover, and we can evolve them based on the interests as we progress. There are several combinatorial objects that find lots of application in designing algorithms in various paradigms like, Parameterized Algorithms, Approximation Algorithms, Streaming Algorithms and Dynamic Algorithms. Matroids and Greedoids are among such widely used combinatorial objects which also explain the inherent working of several greedy algorithm. The course will be focused on understanding these objects, algorithm for performing highly useful operations on them, and their applications. A large part of the course will be focused on understanding matroids from the algorithmic point of view. Then we will look at similar such results for other such highly useful combinatorial objects like greedoids and delta matroids. If time permits we will also go over some recently developed tools in algorithm design.
Textbooks
- Part IV of the textbook on Combinatorial Optimization, Schriver.
- Matroid Optimization part of the course on Combinatorial Optimization by Goemans.
Some Practical Information
Tentative Timings (Slot H): Monday 14:00-15:15, Wednesday 15:30-16:45, and Thursday 17:00-17:50.
Room: CS 34.
Evaluation (tentative):
- 20% class participation, this will be calculated based on presenting solutions to exercises questions given during the class.
- 40% Midterm exam.
- 40% Final exam.
Expectations Regarding Academic Honesty And Usage of Inclusive Languages
