COURSE SUMMARY
Course Title:
Design and Analysis of Algorithms
Course Code:
18CA305
Year Taught:
2018
Semester:
3
Degree:
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.

#### COURSE CONTENT

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 / REFERENCES

• 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.