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.
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.
ConversionConversion EmoticonEmoticon