Unit-I
Introduction: growth functions – recurrence relation – methods – master method. Sorting: bubble – insertion sort – selection sort.
| Course Name | Advanced Data Structures And Algorithms |
| Course Code | 24MAT471 |
| Program | 5 Year Integrated MSc/ BSc. (H) in Mathematics with Minor in Data Science |
| Semester | Elective |
| Credits | 3 |
| Campus | Amritapuri |
Introduction: growth functions – recurrence relation – 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 knapsack problem – task scheduling problem. Dynamic programming: matrix multiplication problem – 0-1 knapsack.
Graph algorithms: graph traversal (DFS, BFS with analysis) – biconnected components – strong connectivity; shortest path algorithms (along with analysis) – Dijkstra – Bellman Ford – Floyd Warshall. All pairs shortest path algorithm – minimum spanning tree (with analysis) – Kruskal – Prim’s – Baruvka’s.
NP problems: definition, P, NP, NP complete, NP hard & co-NP, examples – P, NP.
Course Out Comes:
CO-1: Understand the basic concepts of growth functions and various sortings.
CO-2: Understand and the concept of divide and conquer for various sortings.
CO-3: Understand and apply the greedy method for various problems.
CO-4: Understand various definitions of graphs and apply to some algorithms.
CO-5: Understand the concepts of various computational complexity classes.
Pre-requisite: Data Structures and Algorithms.
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.