Advanced Algorithms
A foray into measured compromises.
This course focuses on advanced algorithmic techniques, with an emphasis on parameterized complexity and approximation algorithms. The primary problems studied include Vertex Cover, Feedback Vertex Set (FVS), and Longest Path problems.
2019 · Jan-Apr Term (IITGN)
Logistics
- Class Timings. Tuesdays and Fridays: 2:00PM to 3:30PM
- Office Hours. By email appointment or whenever the door is open
- Class Venue. AB 7/103
- Office Hours Venue. AB 4/305
Email for queries: neeldhara.m+cs614@iitgn.ac.in - please use this email so I can quickly prioritize emails pertaining to the course.
Please watch this space for announcements - they will all be made on the page linked to below. Very few emails are sent, so please check this place for notifications.
Grading Policy
| Component | Weight |
|---|---|
| Mini-Quizzes | 50% |
| Writing Project | 10% |
| Midsem* | 15% |
| Endsem* | 25% |
We will be using Gradescope to communicate feedback and handle regrade requests. Quiz grades were published within 48 hours, with a regrade request window of approximately 72 hours.
Lecture Schedule
| Date | # | Topic | Title | Materials |
|---|---|---|---|---|
| Jan 3 | 🎉 | — | No Class | — |
| Jan 7 | 00 | Vertex Cover | Our Favorite Problem: Vertex Cover | — |
| Jan 8 | 01 | Vertex Cover | Vertex Cover Continued | Notes, Quiz |
| Jan 10 | 02 | Vertex Cover | 2k Kernel for Vertex Cover | Notes |
| Jan 14 | 03 | Vertex Cover | Improved Branching for AGVC | Notes, Quiz |
| Jan 18 | 04 | Vertex Cover | Hardness of Vertex Cover | Notes, Quiz |
| Jan 22 | 05 | FVS | Improved FPT algorithms for FVS | Notes, Quiz |
| Jan 24 | 06 | FVS | Quadratic Kernel for FVS | Notes, Full Kernel |
| Jan 29 | 07 | FVS | 2-approximation algorithm for FVS | — |
| Jan 31 | 08 | FVS | FVS via tree decompositions | Notes |
| Feb 5 | ⭐️ | — | No Class | — |
| Feb 7 | 🎉 | — | Quiz 1 | — |
| Feb 12 | 09 | FAST | Chromatic Coding for FAST | Notes |
| Feb 14 | 10 | Paths | Color Coding and Rep Sets | Matroids, Paths |
Announcements
Jan 3, 2019 — No Class Today. We will be scheduling a makeup class in due course, meanwhile, the first class is postponed to 3PM on the 7th of January.
Dec 31, 2018 — Website Live. Please make note of the class timings, venue, and course plan.
References
Books:
- Parameterized Algorithms, Cygan et al.
- Design of Approximation Algorithms, Williamson and Shmoys:
Lecture Videos:
- Videos from the RAPC winter school
- Parameterized Complexity Course Videos from IMSc
- Coursera, Approximation Algorithms: Part I and Part II
General Resources:
Covering some prerequisite material:
Udacity: Intro to Theoretical Computer Science (specifically, Computability, Complexity, Theory: Algorithms)
Specialized: TCS+ Talks