Skip to main content

This site is currently under development.

On this page

Historical course edition. Assessment material and former logistics are excluded from this archive view.

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)

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 Continued1 Notes
Jan 10 02 Vertex Cover 2k Kernel for Vertex Cover2 Notes
Jan 14 03 Vertex Cover Improved Branching for AGVC3 Notes
Jan 18 04 Vertex Cover Hardness of Vertex Cover4 Notes
Jan 22 05 FVS Improved FPT algorithms for FVS5 Notes
Jan 24 06 FVS Quadratic Kernel for FVS6 Notes, Full Kernel
Jan 29 07 FVS 2-approximation algorithm for FVS7 —
Jan 31 08 FVS FVS via tree decompositions Notes
Feb 5 ⭐️ — No Class —
Feb 12 09 FAST Chromatic Coding for FAST8 Notes
Feb 14 10 Paths Color Coding and Rep Sets Matroids, Paths

References

Books:

  1. Parameterized Algorithms, Cygan et al.

  2. Design of Approximation Algorithms, Williamson and Shmoys:

Lecture Videos:

  1. Videos from the RAPC winter school

  2. Parameterized Complexity Course Videos from IMSc

  3. 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

Footnotes

  1. Lecture 01 — Vertex Cover Continued

    Watch videos 170-182 on this playlist. ↩

  2. Lecture 02 — 2k Kernel for Vertex Cover

    For AGVC: The first 14:30 minutes of this lecture.

    For Crown Decompositions: The first 13:30 minutes of this lecture. ↩

  3. Lecture 03 — Improved Branching for AGVC

    4^k branching algorithm, where k is the above-LP parameter for Vertex Cover. Start watching from approximately the 21:00-minute mark. ↩

  4. Lecture 04 — Hardness of Vertex Cover

    Equivalence of Almost 2SAT and AGVC (13:00 to 59:00). ↩

  5. Lecture 05 — Improved FPT algorithms for FVS

    Iterative Compression for Vertex Cover and FVS (Full Video). ↩

  6. Lecture 06 — Quadratic Kernel for FVS

    The first ~30 minutes of this lecture on FVS. This describes a O(Dk) kernel for FVS where D is the maximum degree of the input graph. ↩

  7. Lecture 07 — 2-approximation algorithm for FVS

    All videos in Week 1 of the Approximation Algorithms Course on Coursera (Part II). This covers LP duality and Vertex Cover using primal dual. Alternatively, read Chapter 1 (up to Sec 1.5) from the Design of Approximation Algorithms. ↩

  8. Lecture 09 — Chromatic Coding for FAST

    Iterative Compression for FVST: YouTube video from 7:30 to 52:00 (approximately). Alternately: Section 4.2 from Cygan et al. ↩