Unit I : Trees (09 Hours)
Tree- basic terminology, General tree and its representation, representation using sequential and linked organization, Binary tree- properties, converting tree to binary tree, binary tree traversals-inorder, preorder, post order, level wise -depth first and breadth first, Operations on binary tree.Binary Search Tree (BST), BST operations, Threaded binary tree- concepts, threading, insertion and deletion of nodes in in-order threaded binary tree, in order traversal of in-order threaded binary tree. Case Study- Use of binary tree in expression tree-evaluation and Huffman's coding
Unit II: Graphs (09 Hours)
Basic Concepts, Storage representation, Adjacency matrix, adjacency list, adjacency multi list, inverse adjacency list. Traversals-depth first and breadth first, Introduction to Greedy Strategy, Minimum spanning Tree, Greedy algorithms for computing minimum spanning tree- Prims and Kruskal Algorithms, Dikjtra's Single source shortest path, Topological ordering. Case study- Data structure used in Webgraph and Google map.
Unit III : Hashing (09 Hours)
Hash Table- Concepts-hash table, hash function, 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. Dictionary- Dictionary as ADT, ordered dictionaries. Skip List- representation, searching and operations- insertion, removal.
Unit IV : Search Trees (09 Hours)
Symbol Table-Representation of Symbol Tables- Static tree table and Dynamic tree table, Introduction to Dynamic Programming, Weight balanced tree, Optimal Binary Search Tree (OBST), OBST as an example of Dynamic Programming, Height Balanced Tree- AVL tree.
Unit V : Indexing and Multiway Trees (09 Hours)
Indexing and Multiway Trees- Indexing, indexing techniques, Types of search tree- Multiway search tree, B-Tree, B+Tree, Trie Tree, Splay Tree, Red-Black Tree, K-dimensional tree, AA tree. Set- Set ADT, realization of Set and operations. Heap-Basic concepts, realization of heap and operations, Heap as a priority queue, heap sort
Unit VI : File Organization (09 Hours)
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. External Sort- Consequential processing and merging two lists, multiday merging- a k way merge algorithm.