Data & File Structures

Course Code: MIT107

Course Title: Data & File Structures (4 Credits)




Course Contents


Unit – 1: Data Structures Basics: Structure and Problem Solving, Data Structures, Data Structure Operations, Algorithm: Complexity and Time- Space Tradeoff.


Unit –2: Algorithm – Complexity Notations: Mathematical Notation and Functions, Algorithm Notation, Control Structures, Complexity of Algorithm, Rate of Growth- Asymptotic Notation.


Unit – 3: Linked List: Linked List and its representation in memory, Traversing a Linked List, Searching a Linked List, Memory Allocation and Garbage Collection, Insertion into Linked list, Deletion from a Linked list, Types of Linked List.


Unit – 4: Stacks and Queues: Stack, Applications of Stack, Queue.


Unit – 5: Trees and Binary Trees: Tree: Definition and Concepts, 3    Binary Tree: Definition and Concepts, Types of Binary Tree, Traversal on Binary Tree, Representation of Binary Tree.      


Unit – 6: Binary Search Tree: Conversion of General Tree to Binary Tree, Sequential and Other Representations of Binary Tree, Concept of Binary Search Tree (BST), Operations on BST.


Unit -7: Balanced Trees: Definition and Structure of AVL Tree, Operations on AVL Tree, Definition and Structure of B-Tree, Operations on B-Tree, Applications of B-Tree.


Unit –8: Graphs: Basic Concepts about Graphs, Matrix Representation of Graphs, List Structures, Other Representations of Graphs, Algorithms for Graph Traversal, Spanning Trees.


Unit – 9: Applications of Graphs: Topological Sorting, Weighted Shortest Path – Dijkstra’s Algorithm, Minimum Spanning Tree (MST), Introduction to NP-Completeness.


Unit –10: Dynamic Storage Management: Dynamic Storage Management, Memory Management, First-fit Storage Allocation, Storage Release, Buddy Systems, Garbage Collection.


Unit –11: Searching and Sorting Techniques: Sorting- Notations and concepts, Bubble sort, Merge sort, Selection sort, Heap sort; Searching- Sequential searching, Binary searching.      


Unit –12: File Structures: External Storage Devices, Introduction to File Organization, Sequential Files, Indexed Sequential Files, Direct Files.


Unit - 13: External Sorting Techniques: External Sorting- Run lists, Tape sorting; Sorting on Disks, Generating Extended Initial Runs.


Unit –14: External Searching Techniques: External Searching, Introduction to Static Hashing, Dynamic Hashing Techniques.