CP4151 Advanced Data Structures and Algorithms Syllabus:
CP4151 Advanced Data Structures and Algorithms Syllabus – Anna University PG Syllabus Regulation 2021
COURSE OBJECTIVES:
To understand the usage of algorithms in computing
To learn and use hierarchical data structures and its operations
To learn the usage of graphs and its applications
To select and design data structures and algorithms that is appropriate for problems
To study about NP Completeness of problems.
UNIT I ROLE OF ALGORITHMS IN COMPUTING & COMPLEXITY ANALYSIS
Algorithms – Algorithms as a Technology -Time and Space complexity of algorithms- Asymptotic analysis-Average and worst-case analysis-Asymptotic notation-Importance of efficient algorithms- Program performance measurement – Recurrences: The Substitution Method – The Recursion-Tree Method- Data structures and algorithms.
UNIT II HIERARCHICAL DATA STRUCTURES
Binary Search Trees: Basics – Querying a Binary search tree – Insertion and Deletion- Red Black trees: Properties of Red-Black Trees – Rotations – Insertion – Deletion -B-Trees: Definition of B -trees – Basic operations on B-Trees – Deleting a key from a B-Tree- Heap – Heap Implementation – Disjoint Sets – Fibonacci Heaps: structure – Mergeable-heap operations Decreasing a key and deleting a node-Bounding the maximum degree.
UNIT III GRAPHS
Elementary Graph Algorithms: Representations of Graphs – Breadth-First Search – Depth-First Search – Topological Sort – Strongly Connected Components- Minimum Spanning Trees: Growing a Minimum Spanning Tree – Kruskal and Prim- Single-Source Shortest Paths: The Bellman-Ford algorithm – Single-Source Shortest paths in Directed Acyclic Graphs – Dijkstra‘s Algorithm; Dynamic Programming – All-Pairs Shortest Paths: Shortest Paths and Matrix Multiplication – The Floyd-Warshall Algorithm
UNIT IV ALGORITHM DESIGN TECHNIQUES
Dynamic Programming: Matrix-Chain Multiplication – Elements of Dynamic Programming – Longest Common Subsequence- Greedy Algorithms: – Elements of the Greedy Strategy- An Activity-Selection Problem – Huffman Coding.
UNIT V NP COMPLETE AND NP HARD
NP-Completeness: Polynomial Time – Polynomial-Time Verification – NP- Completeness and Reducibility – NP-Completeness Proofs – NP-Complete Problems.
TOTAL : 45 PERIODS
SUGGESTED ACTIVITIES:
1. Write an algorithm for Towers of Hanoi problem using recursion and analyze the complexity (No of disc-4)
2. Write any one real time application of hierarchical data structure
3. Write a program to implement Make_Set, Find_Set and Union functions for Disjoint Set Data Structure for a given undirected graph G(V,E) using the linked list representation with simple implementation of Union operation
4. Find the minimum cost to reach last cell of the matrix from its first cell
5. Discuss about any NP completeness problem
COURSE OUTCOMES:
CO1: Design data structures and algorithms to solve computing problems.
CO2: Choose and implement efficient data structures and apply them to solve problems.
CO3: Design algorithms using graph structure and various string-matching algorithms to solve real-life problems.
CO4: Design one’s own algorithm for an unknown problem.
CO5: Apply suitable design strategy for problem solving.
REFERENCES
1. S.Sridhar,” Design and Analysis of Algorithms”, Oxford University Press, 1st Edition, 2014.
2. Adam Drozdex, “Data Structures and algorithms in C++”, Cengage Learning, 4th Edition, 2013.
3. T.H. Cormen, C.E.Leiserson, R.L. Rivest and C.Stein, “Introduction to Algorithms”, Prentice Hall of India, 3rd Edition, 2012.
4. Mark Allen Weiss, “Data Structures and Algorithms in C++”, Pearson Education, 3rd Edition, 2009.
5. E. Horowitz, S. Sahni and S. Rajasekaran, “Fundamentals of Computer Algorithms”, University Press, 2nd Edition, 2008.
6. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson Education, Reprint 2006.