### RGTU/RGPV MCA-404 Design and Analysis of Algorithms Syllabus MCA 4th -Fourth sem Syllabus

RGTU/RGPV MCA-404 Design and Analysis of Algorithms Syllabus
MCA 4th Sem MCA-404 Design and Analysis of Algorithms Syllabus
MCA 4th - Fourth Semester Syllabus

MCA-404 Design and Analysis of Algorithms Course Contents:

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

Note : Paper is to be set unit wise with internal choice.

 Mixx it! | More