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

UnitII: 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.