Syllabus Data Structure (BC02001011) Total Credits L + T + (PR/2) Assessment Pattern and Marks Total Marks C Theory Tutorial / Practical ESE (E) PA / CA (M) PA / CA (I) ESE (V) 4 70 30 20 30 150 Unit No. Content 1. INTRODUCTION TO DATA STRUCTURE : Data management concepts, Data types - primitive and non-primitive, Performance analysis and measurement (Time and space analysis of algorithms - Average, best and worst case analysis), Types of data structures - Linear and non linear data structures. (Chapter - 1) 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. (Chapters - 2, 3, 4, 5) 3. NONLINEAR DATA STRUCTURE : Tree-definitions and concepts, Representation of binary tree, Binary tree traversal (Inorder, Postorder, Preorder), Threaded binary tree, Binary search trees, Conversion of general trees to binary trees, Applications of trees - Some balanced tree mechanism, e.g. 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). (Chapters - 6, 7) 4. HASHING AND FILE STRUCTURES : Hashing : The symbol table, Hashing functions, Collision resolution techniques. File structure : Concepts of fields, Records and files, Sequential, Indexed and relative / random file organization, Indexing structure for index files, Hashing for direct files, Multi-key file organization and access methods. (Chapters - 8, 9) 5. SORTING AND SEARCHING : Sorting - Bubble sort, Selection sort, Quick sort, Merge sort searching - Sequential search and binary search. (Chapter - 10) List of Practical At least 10 practical should be performed by students using programming language. 1. Introduction to pointers. Call by Value and Call by reference. 2. Introduction to Dynamic Memory Allocation. DMA functions malloc(), calloc(), free() etc. 3. Implement a program for stack that performs following operations using array. (a) PUSH (b) POP (c) PEEP (d) CHANGE (e) DISPLAY 4. Implement a program to convert infix notation to postfix notation using stack. 5. Write a program to implement QUEUE using arrays that performs following operations (a) INSERT (b) DELETE (c) DISPLAY 6. Write a program to implement Circular Queue using arrays that performs following operations. (a) INSERT (b) DELETE (c) DISPLAY 7. Write a menu driven program to implement following operations on the singly linked list. (a) Insert a node at the front of the linked list. (b) Insert a node at the end of the linked list. (c) Insert a node such that linked list is in ascending order.(according to info. Field) (d) Delete a first node of the linked list. (e) Delete a node before specified position. (f) Delete a node after specified position. 8. Write a program to implement stack using linked list. 9. Write a program to implement queue using linked list. 10. Write a program to implement following operations on the doubly linked list. (a) Insert a node at the front of the linked list. (b) Insert a node at the end of the linked list. (c) Delete a last node of the linked list. (d) Delete a node before specified position. 11. Write a program to implement following operations on the circular linked list. (a) Insert a node at the end of the linked list. (b) Insert a node before specified position. (c) Delete a first node of the linked list. (d) Delete a node after specified position. 12. Write a program which create binary search tree. 13. Implement recursive and non-recursive tree traversing methods inorder, preorder and post-order traversal. 14. Write a program to implement Queue Sort 15. Write a program to implement Merge Sort 16. Write a program to implement Bubble Sort 17. Write a program to implement Binary Search.
