 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.
CP5151 ADVANCED DATA STRUCTURES AND ALGORITHMS SYLLABUS

UNIT I ROLE OF ALGORITHMS IN COMPUTING
Algorithms – Algorithms as a Technology Insertion Sort – Analyzing Algorithms – Designing Algorithms Growth of Functions: Asymptotic Notation – Standard Notations and Common Functions Recurrences: The Substitution Method – The RecursionTree Method
UNIT II HIERARCHICAL DATA STRUCTURES
Binary Search Trees: Basics – Querying a Binary search tree – Insertion and Deletion RedBlack trees: Properties of RedBlack Trees – Rotations – Insertion – Deletion BTrees: Definition of Btrees – Basic operations on BTrees – Deleting a key from a BTree Fibonacci Heaps: structure – Mergeableheap operations Decreasing a key and deleting a nodeBounding the maximum degree.
UNIT III GRAPHS
Elementary Graph Algorithms: Representations of Graphs – BreadthFirst Search – DepthFirst Search – Topological Sort – Strongly Connected Components Minimum Spanning Trees: Growing a Minimum Spanning Tree – Kruskal and Prim SingleSource Shortest Paths: The BellmanFord algorithm – SingleSource Shortest paths in Directed Acyclic Graphs – Dijkstra‘s Algorithm; AllPairs Shortest Paths: Shortest Paths and Matrix Multiplication – The FloydWarshall Algorithm;
UNIT IV ALGORITHM DESIGN TECHNIQUES
Dynamic Programming: MatrixChain Multiplication – Elements of Dynamic Programming – Longest Common Subsequence Greedy Algorithms: An ActivitySelection Problem – Elements of the Greedy Strategy Huffman Codes.
UNIT V NP COMPLETE AND NP HARD
NPCompleteness: Polynomial Time – PolynomialTime Verification – NP Completeness and Reducability – NPCompleteness Proofs – NPComplete Problems
TOTAL: 60 PERIODS
OUTCOMES:
 Upon the completion of the course the students should be able to:
 Design data structures and algorithms to solve computing problems
 Design algorithms using graph structure and various string matching algorithms to solve reallife problems
 Apply suitable design strategy for problem solving
REFERENCES:
 Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, ―Data Structures and Algorithms‖, Pearson Education, Reprint 2006.
 Robert Sedgewick and Kevin Wayne, ―ALGORITHMS‖, Fourth Edition, Pearson Education.
 S.Sridhar,‖Design and Analysis of Algorithms‖, First Edition, Oxford University Press. 2014
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ―Introduction to Algorithms‖, Third Edition, PrenticeHall, 2011.
Anna University PG Regulation 2017 CSE Syllabus, CP5151 Applied Probability And Statistics Syllabus, Reg 2017 CP5151 Syllabus, 1st Sem PG Advanced Data Structures
No comments:
Post a comment