Syllabus Data Structures and Algorithms - (210252) Credit Scheme Examination Scheme and Marks 03 End_Semester(TH) : 70 Marks Unit III Graphs Basic Concepts, Storage representation, Adjacency matrix, adjacency list, adjacency multi list, inverse adjacency list. Traversals-depth first and breadth first, Minimum spanning Tree, Greedy algorithms for computing minimum spanning tree - Prims and Kruskal Algorithms, Dikjtra's Single source shortest path, All pairs shortest paths - Flyod-Warshall Algorithm Topological ordering. (Chapter - 3) Unit IV Search Trees Symbol Table-Representation of Symbol Tables - Static tree table and Dynamic tree table, Weight balanced tree - Optimal Binary Search Tree (OBST), OBST as an example of Dynamic Programming, Height Balanced Tree - AVL tree. Red-Black Tree, AA tree, K-dimensional tree, Splay Tree. (Chapter - 4) Unit V Indexing and Multiway Trees Indexing and Multiway Trees - Indexing, indexing techniques-primary, secondary, dense, sparse, Multiway search trees, B-Tree - insertion, deletion, B+Tree - insertion, deletion, use of B+ tree in Indexing, Trie Tree. (Chapter - 5) Unit VI File Organization Files : concept, need, primitive operations. Sequential file organization - concept and primitive operations, Direct Access File - Concepts and Primitive operations, Indexed sequential file organization - concept, types of indices, structure of index sequential file, Linked Organization - multi list files, coral rings, inverted files and cellular partitions. (Chapter - 6)
