Advanced Data Structures

Course Code: MCA212

Course Title: Advanced Data Structure (4 Credits)




Course Contents


Unit – 1: Data Structures Basics: Structure and Problem Solving, Data structures, Data structure Operations, Algorithm: complexity, Time- space tradeoff.


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


Unit – 3:  Linked List: Introduction, Linked lists, Representation of linked lists 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: Stack and Queue: Introduction, Array Representation of Stack, Linked List Representation of stack, Application of stack, Queue, Array Representation of Queue, Linked List Representation of Queue.


Unit – 5: Trees: Definitions and Concepts, Operations on Binary Trees, Representation of binary tree, Conversion of General Trees to Binary Trees, Sequential and Other Representations of Trees, Tree Traversal.


Unit -6: Balanced Trees: AVL- tree – structure, operations, its application, B-Tree – structure, operations, its application.


Unit –7: Graphs: Matrix Representation of Graphs, List Structures, Other Representations of Graphs, Breadth First Search, Depth First Search, Spanning Trees.


Unit -8 Applications of Graphs: Topological Sorting, Shortest-Path Algorithms – Unweighted Shortest Paths – Dijkstra’s Algorithm, Minimum spanning tree- Prim’s Algorithm, Introduction to NP-Completeness.


Unit – 9: Dynamic Storage Management: Fixed Block Storage Allocation, First-fit Storage Allocation, Storage Release, Buddy Systems, Garbage Collection.


Unit –10: Sorting Techniques: Notation and Concepts, Insertion Sort, Selection Sort, Bubble Sort, Merge Sorting, Heap Sort, Radix Sort, Quick Sort.


Unit –11: Searching Techniques: Sequential Searching, Binary Searching, Search Trees, Hash- Table Methods.


Unit – 12: File Structures: External Storage devices-Magnetic Tapes, Magnetic Drums, Magnetic Disks, Mass Storage Devices, Intermediate Storage Devices; Definitions and Concepts, Record Organization, Sequential Files- Structure, Processing; Indexed Sequential Files-Structure, Processing; Direct Files-Structure, Processing.


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- Distribution-dependent Hashing Function, Dynamic Hashing Techniques.