Data Structures for GTU 18 Course (III – CECSEITICT – 3130702) – 2020 Edition

1. Introduction to Data Structure Data management concepts, Data types – primitive and non-primitive, Performance analysis and measurement (Time and space analysts of algorithms – Average, best and worst case analysis). Types of data structures – Linear and non linear data structures. 2. Linear Data Structure Array : Representation of arrays, Applications of arrays, Sparse matrix and its representation. Stack : Stack-Definitions and concepts, Operations on stacks, Applications of stacks, Polish expression. Reverse polish expression and their compilation. Recursion. Tower of Hanoi. Queue : Representation of queue, Operations on queue, Circular queue, Priority queue, Array representation of priority queue, Double ended queue, Applications of queue. Linked list :Singly linked list. Doubly linked list. Circular linked list. Linked implementation of stack, linked implementation of queue, Applications of linked list. 3. Nonlinear Data Structure Tree-definitions and concepts, Representation of binary tree, Binary tree traversal (lnorder, Postorder, Preorder).Threaded binary tree, Binary search trees, Conversion of general trees to binary trees, Applications of trees- Some balanced tree mechanism, e.q. AVL trees, 2-3 trees, Height balanced, Weight balance. Graph-matrix representation of graphs, Elementary graph operations. (Breadth first search. Depth first search. Spanning trees. Shortest path. Minimal spanning tree). 4. Hashing and File Structures Hashing : The symbol table, Hashing functions. Colllsion resolution techniques. File structure : Concepts of fields, Records and files, Sequential, Indexed and relative I random file organization, Indexing structure for index files, Hashing for direct files, Multi-key file organization and access methods 5. Sorting and Searching Sorting – Bubble sort, Selection sort, Quick sort, Merge sort searching – Sequential search and binary search.