| Course Name | Design and Analysis of Algorithms |
| Course Code | 26CSA511 |
| Program | M. C. A. |
| Semester | 2 |
| Credits | 4 |
| Campuses | Amritapuri, Mysuru |
Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types – Fundamentals of the Analysis of Algorithmic Efficiency –Asymptotic Notations and growth rate. Sorting Algorithms and analysis: Bubble sort, Selection sort, Insertion sort, Shell sort. Recurrence Relations- substitution & master’s method.
Divide and conquer strategy – finding minimum and maximum, integer multiplication, binary search, binary search tree. Merge sort, Quick sort, heap sort, and its analysis. Strassen’s algorithm for matrix multiplication, maximum subarray.
Greedy Method – Knapsack problem, Job sequencing with deadlines, optimal merge pattern. Minimum spanning tree – Prim’s and Kruskal’s algorithm. Single source shortest path – Dijkstra’s algorithm, Bellman-Ford algorithm. Huffman Coding, TSP.
Dynamic programming – Principle of optimality, knapsack problem, matrix chain multiplication, longest common subsequence problem, optimal binary search tree, traveling salesman problem. All pair shortest path – Floyd Warshal algorithm.
Backtracking and Branch and Bound – Queen’s problem, sum of subset, graph coloring, Hamiltonian cycle. The class P and NP, polynomial reduction, NP-completeness problem, and NP-Hard problem. Reduction – 3CNF SAT to Clique, Clique to Vertex cover.
Course Description
The primary objective of this course is to introduce the design and analysis of algorithms. Students will learn how to design an efficient algorithm with a computable problem. This includes modelling the problem, selecting appropriate algorithm design techniques, analyzing the efficiency of algorithms and proving the correctness of algorithms.
Course Objectives
Course Outcomes
| COs | Description |
| CO1 | Analyze and estimate the asymptotic complexity of algorithms and compare alternative algorithmic solutions to justify appropriate choices for given problem scenarios. |
| CO2 | Derive, solve, and interpret recurrence relations that describe the performance of divide‑and‑conquer algorithms. |
| CO3 | Apply the greedy algorithmic strategy to design correct and efficient solutions for optimization and scheduling problems. |
| CO4 | Formulate and solve problems using dynamic programming techniques to obtain optimal solutions for multistage decision problems. |
| CO5 | Analyze intractable and NP‑complete problems and devise suitable approximation, heuristic, or reduction‑based approaches to address computational limitations. |
CO-PO Mapping
| PO/PSO | PO1 | PO2 | PO3 | PO4 | PO5 | PO6 | PO7 | PO8 |
| CO | ||||||||
| CO1 | 3 | 3 | 2 | – | 1 | – | – | 1 |
| CO2 | 3 | 3 | 3 | – | 1 | – | – | 1 |
| CO3 | 3 | 3 | 3 | – | 1 | – | – | 1 |
| CO4 | 3 | 3 | 3 | – | 1 | – | – | 1 |
| CO5 | 3 | 3 | 3 | – | 1 | – | – | 2 |
Prerequisites
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.
