Data Structures & Algorithms for SPPU 19 Course (SE – IV – Comp. – 210252)

Unit – IHashing 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 – IITrees 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, Oprations 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 Unit – V Indexing and Multiway Trees Unit – VI File Organization