COURSE SUMMARY
Course Title: 
Design and Analysis of Algorithms
Course Code: 
18CA305
Year Taught: 
2018
Semester: 
3
Degree: 
Postgraduate (PG)
School: 
School of Arts and Sciences
School of Engineering
Campus: 
Kochi
Mysuru
Amritapuri

'Design and Analysis of Algorithms' is a course offered at Amrita Vishwa Vidyapeetham.

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.

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