Objectives
Outcomes
Unit – I
Review of first level portions – different paradigms – different problems from various domains.
Unit – II
Randomized Algorithms– Los vegas and Moute Carlo-Chernoff Bound – Probabilistic Amplification – Typical randomised algorithms e.g. Min cut, Randomised Quick Sort, Randomised Selection, Primdity testing.
Unit – III
Graph algorithms– Review – BFS, DFS, Topological Sort, Shortest paths – B-Trees, AVL Trees.
Unit – IV
Graph Algorithms– MIS, Coloring problems, vertex cover, introduction to perfect graphs.
Unit – V
Approximation algorithms– Ratio bound vertex cover, Set covering, Travelling Salesman problem, Subset sum.