Credit: 3
Objective
To introduce and practice advanced algorithms and programming techniques necessary for developing sophisticated computer application programs
To get accustomed with various programming constructs such as divide-and-conquer, backtracking, and dynamic programming.
To learn new techniques for solving specific problems more efficiently and for analyzing space and time requirements.
Unit I
Review of order rotation & growth of functions, recurrences, probability distributions, Average case analysis of algorithms, Basic data structures such as stacks, queues, linked lists, and applications.
Unit II
Direct access tables and hash tables, hash functions and relates analysis, Binary Search trees and Operations, AVL Trees and balancing operations, R B Trees, properties, operations.
Unit III
B – Trees – definition – properties, operations, data structures for disjoint sets, Graph algorithms, MST single source all pair shortest paths, BFS, DFS, topological sort, strongly connected components.
Unit IV
Quick sort randomized version, searching in linear time, More graph algorithms – maximal independent sets, coloring vertex cover, introduction to perfect graphs.
Unit V
Algorithmic paradigms Greedy Strategy, Dynamic programming, Backtracking, Branch-and-Bound, Randomized algorithms.
Outcome
Students are familiar with algorithmic techniques such as brute force, greedy, and divide and conquer.
Application of advanced abstract data type (ADT) and data structures in solving real world problems.
Effectively combine fundamental data structures and algorithmic techniques in building a complete algorithmic solution to a given problem
Text Books
H. S. Wilf, Algorithms and complexity, Prentice hall.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, Prentice hall.
K. Vishwanathan Iyer, Lecture notes for classroom use.
