MC4101 Advanced Data Structures and Algorithms Syllabus:

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