Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

CS 614 | Jan-Apr 2022

CS614. Advanced Algorithms

January — April 2023
About the Course

This course will explores the tradeoffs involved in coping with NP-completeness.

When we think about designing algorithms, we are usually very demanding in how we go about it: we require our algorithms to be fast and accurate on all conceivable inputs. This is asking for quite a bit, and perhaps it is not surprising that we cannot afford this luxury all the time. The good news is that most of the time we can make meaningful progress by relaxing just one of these demands:

  1. Give up on accuracy, but not completely: look for solutions that are good enough (approximation) and/or work with algorithms that report the right solution most of the time (Las-Vegas style randomization).

  2. Give up on coverage, a little bit: let your algorithms work well on structured inputs. Hopefully the structure is such that it is not too limiting and is interesting enough for some application scenario, and is also enough to give you algorithmic leverage, i.e, there’s enough that you can exploit to make fast and accurate algorithms.

  3. Give up on speed, to some extent: going beyond the traditional allowance of polynomial time, which is the holy grail of what is considered efficient, takes you places. You could either allow for your algorithms have super-polynomial running times, and optimize as much as possible while being accurate on all inputs (exact algorithms), or allow for bad running times on a bounded subset of instances (Monte-Carlo style randomization).

This course is an introduction to techniques in achieving specific trade-offs, and understanding the theoretical foundations of frameworks that help us establish when certain tradeoffs are simply not feasible.

Fig. Exploring tradeoffs between the demands of accuracy, speed, and coverage.

Target Audience

Anyone who is biting their nails from the NP-completeness cliffhanger at the end of their introduction to algorithms will probably enjoy this course.

Prerequisites

This is a theoretical course that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs), and some background in the design and analysis of algorithms. Programming experience is tangentially useful but not necessary. For students of IITGN, this course naturally follows up on DSA-II.

References
  1. The Design of Approximation Algorithms • David P. Williamson and David B. Shmoys
  2. Parameterized Algorithms • Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh
  3. Randomized Algorithms • Motwani and Raghavan
  4. Beyond the Worst-Case Analysis of Algorithms • Tim Roughgarden
  5. Algorithms • Jeff Erickson
Timings and Venue

Lectures on Mondays and Wednesdays • 2PM — 3:30PM • 7/206

TAs and Office hours

Office Hours: By email.

TAs TBA.

Evaluation policy
  • Each of the three exams account for 20% of the grade.
  • Each class will have a quiz worth 2 points. The quizzes will be integrated into the lecture via Mentimeter. The total number of points you can earn through quizzes is capped at 40, and accounts for 40% of the grade.
  • The are three assignments that are not graded but are recommended for practice.
Register

For IITGN students, (pre-)register through IMS as usual.

If you are not from IITGN and are interested in taking up the course, then please send me an email.

  • Lectures
  • Assignments
  • Quizzes
  • Exams
Date Lecture Slides Notes Video
04 Jan, 2023 1. Matroids and Greedy Algorithms - I

Matroids - definitions and examples • GreedyBasis Algorithm • Example: Scheduling with Deadlines

09 Jan, 2023 2. Matroids and Greedy Algorithms - II

Proof of correctness of GreedyBasis

11 Jan, 2023 3. Matroid Intersection - I

Matroid Intersection and Matroid Parity (Section 12.2.1) • Connections with Matchings • 3-Matroid Intersection is NP-complete (Theorem 12.6)

16 Jan, 2023 4. Matroid Intersection - II

A polynomial time algorithm for Matroid Intersection

18 Jan, 2023 5. Vertex Cover

Definition • Applications • Introduction to Approximation Algorithms • 2-approximation for Vertex Cover via maximal matchings

23 Jan, 2023 6. Vertex Cover

Introduction to Linear Programming • 2-approximation via rounding • A simple randomized algorithm for Vertex Cover

25 Jan, 2023 7. Vertex Cover

Introduction to Fixed-Parameter Tractability • An O(2^k) FPT algorithm by branching

01 Feb, 2023 8. Vertex Cover

Introduction to Above-Guarantee Parameterization • FPT in above-guarantee parameters by branching

02 Feb, 2023 9. Vertex Cover

Introduction to Kernelization • A Quadratic Kernel for Vertex Cover based on degree reductions • A Linear Kernel for Vertex Cover based on the LP formulation

13 Feb, 2023 10. Set Cover

A Greedy Approximation Algorithm • A LP formulation and its dual

15 Feb, 2023 11. Set Cover

Rounding a Dual Solution

20 Feb, 2023 12. Feedback Vertex Set

An O(log n)-approximation via primal dual

22 Feb, 2023 13. Feedback Vertex Set

An O(log n)-approximation via primal dual (contd.)

27 Feb, 2023 14. Feedback Vertex Set

A 2-approximation algorithm using a different LP formulation

01 Mar, 2023 15. Feedback Vertex Set

A 2-approximation algorithm using a different LP formulation (contd.)

13 Mar, 2023 16. Feedback Vertex Set

Reduction rules for FVS • A linear kernel on graphs of constant maximum degree

15 Mar, 2023 17. Feedback Vertex Set

Bounding the degree of YES-instances of FVS

20 Mar, 2023 18. Feedback Vertex Set

Iterative Compression • An O*(3.619^k) algorithm for FVS on general graphs • A polynomial-time algorithm on graphs of maximum degree 3

27 Mar, 2023 19. Lower Bounds

Introduction to NP-completeness • 3-Partition and friends • Multiprocessor Scheduling • Packing rectangles into a rectangle

29 Mar, 2023 20. Lower Bounds

Reductions from 3-Partition

03 Apr, 2023 21. Lower Bounds

SAT and Circuit SAT • CNF SAT • 3SAT • 3SAT-4 • Monotone 3SAT • Polynomial-time variants

05 Apr, 2023 22. Lower Bounds

Schaefer's Dichotomy Theorem • 2-colorable perfect matching

10 Apr, 2023 23. Lower Bounds

Parameterized Intractability • The W-hierarchy • Reductions from CLIQUE

12 Apr, 2023 24. Lower Bounds

Kernel Lower Bounds • Composition and Distillation • Examples of compositions • Parameter preserving transformations

17 Apr, 2023 25. Lower Bounds

The (Strong) Exponential Time Hypothesis • Sparsification Lemma • Implications for parameterized algorithms

19 Apr, 2023 26. Lower Bounds

Reductions based on the ETH

24 Apr, 2023 27. Lower Bounds

Inapproximability Introduction • NP optimization problems • PTAS, APX • Stronger notions of reductions that preserve approximability • APX-hardness of vertex cover

26 Apr, 2023 28. Lower Bounds

Gap Inapproximability • Gap Problems • Gap-producing and gap-preserving reductions • PCP theorem • Unique Games Conjecture

No matching items

These are some practice assignments: the due date is simply the recommended completion deadline. There is no need to submit these assignments.

Issued Assessment Problem Set Solutions Due
11 Jan, 2023 Assignment 1

01 Feb, 2023
20 Feb, 2023 Assignment 2

20 Mar, 2023
03 Apr, 2023 Assignment 3

26 Apr, 2023
No matching items
Issued Assessment Problem Set Solutions Due
09 Jan, 2023 Matroids and Greedy Algorithms - II

Proof of correctness of GreedyBasis

09 Jan, 2023
11 Jan, 2023 Matroid Intersection - I

Matroid Intersection and Matroid Parity (Section 12.2.1) • Connections with Matchings • 3-Matroid Intersection is NP-complete (Theorem 12.6)

11 Jan, 2023
16 Jan, 2023 Matroid Intersection - II

A polynomial time algorithm for Matroid Intersection

16 Jan, 2023
18 Jan, 2023 Vertex Cover

Definition • Applications • Introduction to Approximation Algorithms • 2-approximation for Vertex Cover via maximal matchings

18 Jan, 2023
23 Jan, 2023 Vertex Cover

Introduction to Linear Programming • 2-approximation via rounding • A simple randomized algorithm for Vertex Cover

23 Jan, 2023
25 Jan, 2023 Vertex Cover

Introduction to Fixed-Parameter Tractability • An O(2^k) FPT algorithm by branching

25 Jan, 2023
01 Feb, 2023 Vertex Cover

Introduction to Above-Guarantee Parameterization • FPT in above-guarantee parameters by branching

01 Feb, 2023
03 Feb, 2023 Vertex Cover

Introduction to Kernelization • A Quadratic Kernel for Vertex Cover based on degree reductions • A Linear Kernel for Vertex Cover based on the LP formulation

03 Feb, 2023
13 Feb, 2023 Set Cover

A Greedy Approximation Algorithm • A LP formulation and its dual

13 Feb, 2023
15 Feb, 2023 Set Cover

Rounding a Dual Solution

15 Feb, 2023
20 Feb, 2023 Feedback Vertex Set

An O(log n)-approximation via primal dual

20 Feb, 2023
22 Feb, 2023 Feedback Vertex Set

An O(log n)-approximation via primal dual (contd.)

22 Feb, 2023
27 Feb, 2023 Feedback Vertex Set

A 2-approximation algorithm using a different LP formulation

27 Feb, 2023
01 Mar, 2023 Feedback Vertex Set

A 2-approximation algorithm using a different LP formulation (contd.)

01 Mar, 2023
13 Mar, 2023 Feedback Vertex Set

Reduction rules for FVS • A linear kernel on graphs of constant maximum degree

13 Mar, 2023
15 Mar, 2023 Feedback Vertex Set

Bounding the degree of YES-instances of FVS

15 Mar, 2023
20 Mar, 2023 Feedback Vertex Set

Iterative Compression • An O*(3.619^k) algorithm for FVS on general graphs • A polynomial-time algorithm on graphs of maximum degree 3

20 Mar, 2023
27 Mar, 2023 Lower Bounds

Introduction to NP-completeness • 3-Partition and friends • Multiprocessor Scheduling • Packing rectangles into a rectangle

27 Mar, 2023
29 Mar, 2023 Lower Bounds

Reductions from 3-Partition

29 Mar, 2023
03 Apr, 2023 Lower Bounds

SAT and Circuit SAT • CNF SAT • 3SAT • 3SAT-4 • Monotone 3SAT • Polynomial-time variants

03 Apr, 2023
05 Apr, 2023 Lower Bounds

Schaefer's Dichotomy Theorem • 2-colorable perfect matching

05 Apr, 2023
10 Apr, 2023 Lower Bounds

Parameterized Intractability • The W-hierarchy • Reductions from CLIQUE

10 Apr, 2023
12 Apr, 2023 Lower Bounds

Kernel Lower Bounds • Composition and Distillation • Examples of compositions • Parameter preserving transformations

12 Apr, 2023
17 Apr, 2023 Lower Bounds

The (Strong) Exponential Time Hypothesis • Sparsification Lemma • Implications for parameterized algorithms

17 Apr, 2023
19 Apr, 2023 Lower Bounds

Reductions based on the ETH

19 Apr, 2023
24 Apr, 2023 Lower Bounds

Inapproximability Introduction • NP optimization problems • PTAS, APX • Stronger notions of reductions that preserve approximability • APX-hardness of vertex cover

24 Apr, 2023
26 Apr, 2023 Lower Bounds

Gap Inapproximability • Gap Problems • Gap-producing and gap-preserving reductions • PCP theorem • Unique Games Conjecture

26 Apr, 2023
No matching items
Issued Assessment Problem Set Solutions Due
TBA Exam 1

-
TBA Exam 2

-
TBA Exam 3

-
No matching items

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×