Unit - I Hashing Hash Table : Concepts - hash table, hash function, basic operations, bucket, collision, probe, synonym, overflow, open hashing, closed hashing, perfect hash function, load density, full table, load factor, rehashing, issues in hashing, hash functions - properties of good hash function, division, multiplication, extraction, mid - square, folding and universal, collision resolution strategies - open addressing and chaining, hash table overflow - open addressing and chaining, extendible hashing, closed addressing and separate chaining. Skip List : Representation, searching and operations - insertion, removal. (Chapter - 1) Unit - II Trees Tree : Basic terminology, General tree and it's representation, representation using sequential and linked organization, Binary tree - properties, converting tree to binary tree, binary tree traversals (recursive and non-recursive) - inorder, preorder, post order, depth first and breadth first, Operations on binary tree. Huffman Tree (Concept and use), Binary Search Tree (BST), BST operations, Threaded binary search tree - concepts, threading, insertion and deletion of nodes in inorder threaded binary search tree, in order traversal of in-order threaded binary search tree. (Chapter - 2) 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)
