| Course Name | Design and Analysis of Algorithms |
| Course Code | 15CSE211 |
| Program | B. Tech. in Computer Science and Engineering |
| Semester | Four |
| Year Taught | 2019 |
Introduction – Algorithms vs programs. Flow charts and pseudo code, Rate of growth of functions. Asymptotic notation: motivation and types of notations. Recurrence relations and methods to solve them: Recursion tree, substitution, Master Method, Sorting: Bubble – Insertion – Selection – Bucket – Heap, Comparison of sorting algorithms, Divide and Conquer: Quick sort – Merge sort – Binary search – Long integer multiplication – Maximum sub array sum.
Greedy Algorithm – Introduction to the method, Fractional Knapsack problem, Task Scheduling Problem, Dynamic Programming: Introduction to the method, Fibonacci numbers, 0-1 Knapsack problem, Matrix chain multiplication problem. Backtracking, Branch and Bound 0-1 Knapsack, N- Queen problem.
Graph Algorithms – Graph Traversal: Applications of BFS: distance, connectivity and connected components and cycles in undirected graphs. Applications of DFS: Topological sort, cycles in directed graphs, Biconnected Components and Strong Connectivity. Path algorithms: Shortest path algorithms (along with analysis) SSSP: Bellman Ford. APSP: Floyd Warshall’s. Minimum Spanning Tree (with analysis and applications). Introduction to NP class: Definitions P, NP, NP complete, NP hard, Examples of P and NP.
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.
