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.