UNIT - I Introduction Introduction to Data Structures : Concept of data, Data object, Data structure, Concept of primitive and non-primitive, linear and nonlinear, static and dynamic, persistent and ephemeral data structures, Definition of ADT Analysis of algorithm : Frequency count and its importance in analysis of an algorithm, Time complexity & Space complexity of an algorithm Big 'O', '' and '' notations, Sequential Organization : Single and multidimensional array and address calculation. Linked Organization : Concept of linked organization, Singly Linked List, Doubly Linked List, Circular Linked List (Operations : Create, Display, Search, Insert, Delete). (Chapter - 1) UNIT - II Searching and Sorting Searching and sorting : Need of searching and sorting, Concept of internal and external sorting, sort stability, Searching methods : Linear and binary search algorithms, Fibonacci Series. Sorting methods : Bubble, Insertion, Quick, Merge, Shell and comparison of all sorting methods. Analyze insertion sort, quick sort, binary search, Hashing for Best, Worst and Average case. (Chapter - 2) UNIT - III Stack & Queue Stack : Concept of stack, Concept of implicit and explicit stack, stack as an ADT using sequential and linked organization, Applications of stack : recursion, converting expressions from infix to postfix or prefix form, evaluating postfix or prefix form. Queue : Concept of queues as ADT, Implementation of queue using array and linked organization, Concept of circular queue, double ended queue, Applications of queue : priority queue. (Chapter - 3) UNIT - IV Trees Tree : Trees and binary trees-concept and terminology, Expression tree, Binary tree as an ADT, Binary search tree, Recursive and Non recursive algorithms for binary tree traversals , Binary search tree as ADT (Insert, Search, Delete, level wise Display) Threaded binary tree : Concept of threaded binary tree (inorder, preorder and postorder). Preorder and In-order traversals of in-order threaded binary tree, Applications of trees. (Chapter - 4) UNIT - V Graph and Symbol Table Graph : Concept and terminologies, Graph as an ADT, Representation of graphs using adjacency matrix and adjacency list, Breadth First Search traversal, Depth First Search traversal, Prim’s and Kruskal’s algorithms for minimum spanning tree, Shortest path using Dijkstra's algorithm, topological sorting. Symbol Table : Notion of Symbol Table, OBST, AVL Trees. Heap : Heap data structure, Min and Max Heap, Heap sort, applications of heap (Chapter - 5) UNIT - IV Hashing and File Organization Hashing : Hash tables and scattered tables : Basic concepts, hash function, characteristics of good hash function, Different key-to-address transformations techniques, synonyms or collisions, collision resolution techniques - linear probing, quadratic probing, rehashing, chaining with and without replacement. File : Concept of File, File types and file organization (sequential, index sequential and Direct Access), Comparison of different file organizations. (Chapter - 6)
