Advanced Data Structures syllabus

Tree- Basic terminology, Representation using sequential and linked organization, Binary tree - properties, Converting tree to binary tree, Binary tree traversals and Tree Iterators - Inorder, Preorder, Postorder, Depth First and Breadth First. Binary Search Tree (BST), BST operations, Threaded binary search tree-concepts, threads, insertion and deletion of nodes in Inorder threaded binary search tree, in order traversal of in-order threaded binary search tree.

Graph: Basic Concepts, Storage representation, Adjacency matrix, adjacency list, adjacency multi list, inverse adjacency list, Dynamic graphs vs. static graphs. Traversals-Depth First Search and Breadth First Search, Minimum Spanning Tree, Greedy algorithms for computing minimum spanning tree- Prims and Kruskal Algorithms, Dikjtra’s Single source shortest path, All pairs shortest paths- Floyd-Warshall Algorithm

Introduction to Hashing: Basic Concept, Comparison with arrays, linked lists, and trees. Hash Table & Operations: Definition, structure, insertion, deletion, searching, bucket roles, and performance metrics, Hash Functions: Properties of good hash functions; Types of Hash Functions: division, multiplication, extraction, mid-square, folding, and universal hashing. Collision and Resolution Techniques, Hash Table Overflow and Management, Applications of Hashing

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

m-way Search Trees: Definition and properties, Searching m-way Search Trees, B Tree : Definition and properties, Insertion and Deletion in B Tree, B+ Tree : Definition and properties, Searching, Insertion and Deletion in B+ Tree. Heap: Heap data structures basic concepts, Min and Max Heap, Realization of Heap, Heap as an ADT, Heap sort, applications of heap.