Credits: 3 (3-0-0)
Prerequisites: MTL342 or COL351 or equivalent
Description
Review of NP-completeness and reductions. Introduction to parameterized complexity, parameterized algorithms through bounded search trees, iterative compression, randomized methods in parameterized algorithms, dynamic programming over subsets, treewidth and parameterized algorithms for bounded treewidth graphs, algebraic techniques in parameterized complexity, Matroids and representative sets, lower bounds for parameterized algorithms based on Exponential Time Hypothesis and Strong Exponential Time Hypothesis.
Prerequisite Tree
flowchart TD
MTL780-1044[MTL780]
MTL780-1044 --- Or1045[Any one of]:::empty
Or1045 -.-> MTL342-1046[MTL342]
MTL342-1046 --> MTL180-1046[MTL180]
Or1045 -.-> COL351-1047[COL351]
COL106-1047 --> COL100-1047[COL100]
COL351-1047 --> COL106-1047[COL106]
classDef empty height:17px, fill:transparent, stroke:transparent;
classDef trueEmpty height:0px, width:0px;