MCA-404 Design and Analysis of Algorithms:

UNIT – I

Pre-requisites: Data structure & Discrete structures, models of computation, algorithm analysis, order architecture, time space complexities average and worst case analysis.

UNIT-II

Divide and conquer: Structure of divide-and-conquer algorithms: examples; Binary search, quick sort,Strassen Multiplication; Analysis of divide and conquer run time recurrence relations.

Graph searching and Traversal: Overview, Traversal methods (depth first and breadth first search)

UNIT-III

Greedy Method: Overview of the greedy paradigm examples of exact optimization solution (minimum cost spanning tree), Approximate solution (Knapsack problem), Single source shortest paths.

Branch and bound: LC searching Bounding, FIFO branch and bound, LC branch and bound application:0/1 Knapsack problem, Traveling Salesman Problem, searching & sorting algorithms.

UNIT-IV

Dynamic programming: Overview, difference between dynamic programming and divide and conquer,Applications: Shortest path in graph, Matrix multiplication, Traveling salesman Problem, longest Common sequence.

Back tracking: Overview, 8-queen problem, and Knapsack problem

UNIT-V

Computational Complexity: Complexity measures, Polynomial Vs non-polynomial time complexity;NP-hard and NP-complete classes, examples.

Combinational algorithms, string processing algorithm, Algebric algorithms , set algorithms

BOOKS:

1. Ullman "Analysis and Design of Algorithm" TMH

2. Goodman “Introduction to the Design & Analysis of Algorithms, TMH-2002.

3. Sara Basse, A. V. Gelder, “ Computer Algorithms,” Addison Wesley

4. T. H. Cormen, Leiserson , Rivest and Stein, “Introduction of Computer algorithm,” PHI

5. E. Horowitz, S. Sahni, and S. Rajsekaran, “Fundamentals of Computer Algorithms,” Galgotia Publication.

 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------