MTL760: Advanced Algorithms

3 Credits (3-0-0)

Pre-requisites: MTL342

Overlaps with: COL758

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.