Teaching

Advanced Data Structures and Algorithms (Online M. Tech in AI and Data Science)

Module I: Trees and heaps - Priority queues and heaps, Binary Search tree, AVL tree, M-way search tree, B-tree, B + tree, hash tables.

Module II:  Algorithms on arrays - Linear-time median finding, sorting in linear time, string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms). 

Module III: Graphs - Various graph representation methods, representation of Di-graph, graph algorithms, Directed Acyclic Graphs (DAGs).

Module-IV:  Geometric algorithms - Convex hull, Voronoi diagram, line segment intersections, closest pair(s) finding, range searching, KD-trees, polygon triangulation. 

Module-V:  Complexity Classes - Computational models, classes: P, NP, NP-hard and NP-complete; reducibility between problems and NP-completeness: discussion on different NP-complete problems like satisfiability, clique, vertex cover, independent set, Hamiltonian cycle, TSP, knapsack, set cover, bin packing, etc. 

Module-VI: Approximation algorithms - approximation ratio, vertex cover, set cover, knapsack problem, and other examples.

Module-VII:  Randomized algorithms – Monte Carlo and Las Vegas algorithms, Min-cut algorithm, Game tree evaluation, Randomness and non-uniformity, examples. 

Module – VIII: Genetic algorithm - Introduction to genetic algorithm, components of GA, GA in machine learning.

Books: 

1. T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, Second Edition, Prentice-Hall India, 2003.

2. M. de-Berg, O. Cheong, M. van-Kreveld, M. Overmars, Computational Geometry, Springer. 

3. Douglas B. West, Introduction to Graph Theory, Prentice Hall of India.

4. Vijay Vazirani, Approximation Algorithms, Springer.

5. Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press

6. An Introduction to Genetic Algorithms, Melanie Mitchell, MIT Press, 2000.

7. Genetic Algorithms In Search, Optimization And Machine Learning, David E. Goldberg, Pearson Education, 2002.