Study Materials & Notes

Data Structure & Algoritms PCC-CS301 Organizer: Introduction, Linked Lists, Trees, Stacks & Queues, Graphs and Sorting & Hashing

The document is a comprehensive textbook chapter overview and compilation of questions and answers on **Data Structure & Algorithm (DSA)**. It covers fundamental concepts and includes numerous solved questions from past WBUT (West Bengal University of Technology) examinations. **Key Topics Covered in the Overview Sections:** * **Introduction:** Defines *Data*, *Metadata*, and *Data Structure* (linear and non-linear). It lists common operations on data structures (Traversing, Searching, Inserting, Deleting, Sorting, Merging). It also introduces **Abstract Data Type (ADT)**, the basic properties of an **Algorithm** (Input, Output, Definiteness, Finiteness, Effectiveness), and **Algorithm Analysis** (Time Complexity and Space Complexity) using asymptotic notations like Big O, Omega, and Theta. * **Linked Lists:** Covers Singly, Circular, and Doubly Linked Lists. It details operations like insertion and linked representation of polynomials. * **Trees:** Defines a **Tree** and its basic terminology (Node, Root, Degree, Path, Terminal/Leaf nodes, Non-Terminal nodes). It specifically describes **Binary Tree**, **Binary Search Tree (BST)**, and **Threaded Binary Tree**. * **Stacks & Queues:** Discusses Abstract Data Types like stacks and queues, and different variations like Dequeue (Double Ended Queue) and Priority Queue. * **Graphs:** Covers types of graphs (Undirected and Directed), graph traversal methods (**Depth First Search (DFS)** and **Breadth First Search (BFS)**), **Spanning Tree**, and **Shortest Path** algorithms (Dijkstra's, Bellman-Ford, A\* search). * **Sorting & Hashing:** Explains searching methods (**Linear Search** and **Binary Search**), and collision resolution in **Hashing** (Open Addressing and Chaining). It describes various sorting algorithms: **Bubble Sort**, **Insertion Sort**, **Quick Sort**, **Merge Sort**, and **Heap Sort**.