CS456

ADVANCED TOPICS IN ALGORITHMS

Objectives

  • To introduce fundamentals of contemporary topics in algorithms 
  • To provide an exposure to graduate level topics in algorithms

 

Outcomes

  • Ability to pursue an advanced course in algorithms offering in-depth study of one topic
  • Ability to pursue research in advanced topics in algorithms

 

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.

 

TEXT BOOKS

  1. T. H. Cormen, C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms", The MIT press, Cambridge, Massachusetts and McGraw Hill, 1990.
  2. H. S. Wilf, Algorithms and complexity, Prentice hall.