Credits: 3 (3-0-0)
Prerequisites: MTL342
Overlaps with: COL758
Description
MST: Fibonacci Heaps and O(m log log n) time implementation of MST, Linear time MST verification Algorithm, A linear time randomized algorithm for MST,Finding min-cost arborescences; Dynamic Graph Algorithms; Review of NP-completeness; Introduction to NP- hard optimization problems; A brief introduction to LPP; Integer Programming Problem; Primal-Dual Algorithm; Approximation Algorithms: Primal-Dual Approximation Scheme; vertex cover, set cover, TSP; Hardness of Approximation; Introduction to Randomized Algorithms; Some basic Randomized algorithms; Probabilistic Method: Lovasz Local Lemma.
Prerequisite Tree
flowchart TD
MTL760-618[MTL760]
MTL342-618 --> MTL180-618[MTL180]
MTL760-618 --> MTL342-618[MTL342]
classDef empty height:17px, fill:transparent, stroke:transparent;
classDef trueEmpty height:0px, width:0px;