Back close

Course Detail

Course Name Design and Analysis of Algorithms
Course Code 18CA305
Program M. C. A., M. C. A. ( Offered at Mysuru Campus )
Semester Three
Credits Four
Year Taught 2018
Degree Postgraduate (PG)
School School of Arts and Sciences, School of Engineering
Campus Kochi, Mysuru, Amritapuri


Introduction– Asymptotic Notations- Monotonicity vs. Nonmonotonicity – Examples.Analysis of iterative programs, Analysis of recursive programs: Recurrence Relation:Substitution method, Recursion Tree Methods, Master Method. Sorting: Bubble – Insertion Sort- Selection Sort. Divide and Conquer: Quick Sort- Merge Sort- Bucket Sort-Lower Bounds- Heap Sort – Comparisons of Sorting. Greedy Algorithm: Fractional Knap-sack Problem- Task Scheduling Problem. Dynamic Programming: Matrix Multiplication Problem- 0/1 Knap-sack Problem. Branch and Bound – backtracking

Graph Algorithms: Graph Traversals (DFS, BFS with Analysis) – Shortest Path Algorithms (with Analysis) – Dijkstra – Bellman Ford- Floyd Warshall’s all Pair shortest path Algorithm-Minimum spanning Tree (with Analysis) – Kruskal– Prims – Applications of BFS and DFS. Network Flow algorithms

NP Problems: Definition: P-NP-NP Complete-NP Hard. Examples:P-NP.

Text Books

  1. CormenT.H ,Leiserson C.E, Rivest R.L and Stein C, “Introduction to Algorithms”, Third Edition, Prentice Hall of India, 2009.
  2. Baase.S and Gelder A.V., “Computer Algorithms- Introduction to Design and Analysis”, Third edition, Pearson Education Asia, 2003.
  3. Ellis Horowitz ,SartajSahni.S and Rajasekaran.S, “Fundamentals of Computer Algorithms”, Silicon Press, 2008.
  4. Goodrich M.T and Tamassia.R, “Algorithm Design Foundations, Analysis, and Internet Examples”, Fourth Edition, John Wiley and Sons, 2002.
  5. Dasgupta.S, Papadimitriou.C. andVazirani.U, “Algorithms”, Eighth edition, Tata McGraw-Hill, 2009.

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.

Admissions Apply Now