img-20170726-wa0017

Unit – IV

BACKTRACKING: General method, Applications- n-queen problem, Sum of subsets problem, Graph colouring, 0/1knapsack problem, and Hamiltonian cycles.
BRANCH AND BOUND: General method, applications – travelling sales person problem, 0/1
knapsack problem- LC branch and bound solution, FIFO branch and bound solution.

Unit – I

INTRODUCTION: Algorithm, pseudo code for expressing algorithms, performance analysis-space complexity, time complexity, asymptotic notation- big (O) notation, omega notation, theta notation and little (o) notation, recurrences, probabilistic analysis, disjoint set operations, union and find algorithms.

Unit – II

DIVIDE AND CONQUER: General method, applications-analysis of binary search, quick sort, merge sort, AND OR Graphs.
GREEDY METHOD: General method, Applications-job sequencing with deadlines, 0/1 knapsack problem, minimum cost spanning trees, Single source shortest path problem.

Unit – III

GRAPHS (Algorithm and Analysis): Breadth first search and traversal, Depth first search and traversal, Spanning trees, connected components and bi-connected components, Articulation points.
DYNAMIC PROGRAMMING: General method, applications – optimal binary search trees, 0/1
knapsack problem, All pairs shortest path problem, Travelling sales person problem, Reliability design.

Unit – V

NP-HARD AND NP-COMPLETE PROBLEMS: Basic concepts, non-deterministic algorithms, NPhard and NP-complete classes, Cook’s theorem.

TEXT BOOKS

1. Ellis Horowitz, Satraj Sahni, Rajasekharam (2007), Fundamentals of Computer Algorithms, 2nd edition, University Press, New Delhi.

REFERENCES

1. R. C. T. Lee, S. S. Tseng, R.C. Chang and T. Tsai (2006), Introduction to Design and Analysis
of Algorithms Astrategic approach, McGraw Hill, India.
2. Allen Weiss (2009), Data structures and Algorithm Analysis in C++, 2nd edition, Pearson education, New Delhi.
3. Aho, Ullman, Hopcroft (2009), Design and Analysis of algorithms, 2nd edition, Pearson education, New Delhi