# CS 614 | Jan-Apr 2022

## CS614. Advanced Algorithms

##### January — April 2023

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 |

Issued | Assessment | Problem Set | Solutions | Due |

04 Jan, 2023 |
Matroids and Greedy Algorithms - IMatroids - definitions and examples • GreedyBasis Algorithm • Example: Scheduling with Deadlines |
04 Jan, 2023 | ||

09 Jan, 2023 |
Matroids and Greedy Algorithms - IIProof of correctness of GreedyBasis |
09 Jan, 2023 | ||

11 Jan, 2023 |
Matroid Intersection - IMatroid 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 - IIA polynomial time algorithm for Matroid Intersection |
16 Jan, 2023 | ||

18 Jan, 2023 |
Vertex CoverDefinition • Applications • Introduction to Approximation Algorithms • 2-approximation for Vertex Cover via maximal matchings |
18 Jan, 2023 | ||

23 Jan, 2023 |
Vertex CoverIntroduction to Linear Programming • 2-approximation via rounding • A simple randomized algorithm for Vertex Cover |
23 Jan, 2023 | ||

25 Jan, 2023 |
Vertex CoverIntroduction to Fixed-Parameter Tractability • An O(2^k) FPT algorithm by branching |
25 Jan, 2023 | ||

30 Jan, 2023 |
Vertex CoverIntroduction to Above-Guarantee Parameterization • FPT in above-guarantee parameters by branching |
30 Jan, 2023 | ||

01 Feb, 2023 |
Vertex CoverIntroduction to Kernelization • A Quadratic Kernel for Vertex Cover based on degree reductions • A Linear Kernel for Vertex Cover based on the LP formulation |
01 Feb, 2023 | ||

13 Feb, 2023 |
Set CoverA Greedy Approximation Algorithm • A LP formulation and its dual |
13 Feb, 2023 | ||

15 Feb, 2023 |
Set CoverRounding a Dual Solution |
15 Feb, 2023 | ||

20 Feb, 2023 |
Feedback Vertex SetAn O(log n)-approximation via primal dual |
20 Feb, 2023 | ||

22 Feb, 2023 |
Feedback Vertex SetAn O(log n)-approximation via primal dual (contd.) |
22 Feb, 2023 | ||

27 Feb, 2023 |
Feedback Vertex SetA 2-approximation algorithm using a different LP formulation |
27 Feb, 2023 | ||

01 Mar, 2023 |
Feedback Vertex SetA 2-approximation algorithm using a different LP formulation (contd.) |
01 Mar, 2023 | ||

13 Mar, 2023 |
Feedback Vertex SetReduction rules for FVS • A linear kernel on graphs of constant maximum degree |
13 Mar, 2023 | ||

15 Mar, 2023 |
Feedback Vertex SetBounding the degree of YES-instances of FVS |
15 Mar, 2023 | ||

20 Mar, 2023 |
Feedback Vertex SetIterative 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 BoundsIntroduction to NP-completeness • 3-Partition and friends • Multiprocessor Scheduling • Packing rectangles into a rectangle |
27 Mar, 2023 | ||

29 Mar, 2023 |
Lower BoundsReductions from 3-Partition |
29 Mar, 2023 | ||

03 Apr, 2023 |
Lower BoundsSAT and Circuit SAT • CNF SAT • 3SAT • 3SAT-4 • Monotone 3SAT • Polynomial-time variants |
03 Apr, 2023 | ||

05 Apr, 2023 |
Lower BoundsSchaefer's Dichotomy Theorem • 2-colorable perfect matching |
05 Apr, 2023 | ||

10 Apr, 2023 |
Lower BoundsParameterized Intractability • The W-hierarchy • Reductions from CLIQUE |
10 Apr, 2023 | ||

12 Apr, 2023 |
Lower BoundsKernel Lower Bounds • Composition and Distillation • Examples of compositions • Parameter preserving transformations |
12 Apr, 2023 | ||

17 Apr, 2023 |
Lower BoundsThe (Strong) Exponential Time Hypothesis • Sparsification Lemma • Implications for parameterized algorithms |
17 Apr, 2023 | ||

19 Apr, 2023 |
Lower BoundsReductions based on the ETH |
19 Apr, 2023 | ||

24 Apr, 2023 |
Lower BoundsInapproximability 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 BoundsGap Inapproximability • Gap Problems • Gap-producing and gap-preserving reductions • PCP theorem • Unique Games Conjecture |
26 Apr, 2023 |

Issued | Assessment | Problem Set | Solutions | Due |

TBA |
Exam 1 |
- | ||

TBA |
Exam 2 |
- | ||

TBA |
Exam 3 |
- |