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: This unit gives a brief explanation about mathematical function and notations occur in study of algorithms and the notation of complexity of an algorithm.


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 and Binary Trees: This unit gives an overview of terminology of the tree structure and the unit further explored to binary tree. It explains the types of binary tree and different traversal pattern on binary tree. Finally this unit discuss the what are the different ways that the binary tree can be represented.


Unit -6: Binary Search Tree: This unit discusses about the BST (Binary Search tree), how to construct binary tree from a given tree. This unit discusses about sequential and other representation of binary tree. How to carry out search, insertion and deletion procedure on BST.


Unit –7: Balances Trees: This unit is discuss about two more important type of tree called AVL tree and B-Tree. This unit discusses about the tree structure and various operations on both type of trees. Concluded with the the discussion of applications of B-Tree.


Unit -8: Graphs: This unit covers the basic concept of graphs as data structure. It also discussed the representation of graph in matrix and list structure. Explain to write algorithm for finding paths between nodes and this unit concluded with the discussion of spanning tree.


Unit – 9: Application of Graphs: This unit covers topological sorting and Dijkstra’s algorithm to find shortest path in graph and to find the minimum spanning tree using prim’s algorithm.


Unit –10: Dynamic Storage Management: This unit familiarises you with the concept of dynamic memory management and what are the various practices involved in memory management. It explores the concept of buddy system, storage realse and the role of agrbage collection.


Unit –11: Searching & Sorting Techniques: This unit covers the notation and concepts of sorting. Further this unit explores about sorting technique, sequential and binary search technique.


Unit – 12: File Structures: This unit discuss the various external storage devices. It also discuss about the various file structures like sequential, indexed sequential and direct file and its processing procedure.


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.