MCA-404 Design and Analysis of Algorithms Syllabus

RAJIV GANDHI PROUDYOGIKI VISHWAVIDYALAYA

  (University of Technology of Madhya Pradesh)

 COURSE OF STUDY AND SCHEME OF EXAMINATION

MASTER OF COMPUTER APPLICATIONS (MCA)

W.E.F. 2005-2006

MCA-404 Design and Analysis of Algorithms Syllabus

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.

Brach 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, “Funadmentals of Computer Algorithms,” Galgotia Publication

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