Simplified DFS Notes (Units I–IV)
UNIT I: Linear Data Structures
1. Introduction to Data Structures
• Data Structure: A method of organizing, managing, and storing data so it can be
accessed and modified efficiently.
• Classification:
o Linear Data Structures: Elements are stored in a sequential order.
Examples: Arrays, Linked Lists, Stacks, Queues.
o Non-Linear Data Structures: Data is stored hierarchically. Examples:
Trees and Graphs.
2. Abstract Data Types (ADT)
• Abstract Data Type: A theoretical concept that defines the behavior (operations)
of a data structure without specifying implementation.
• Examples: List, Stack, Queue, Tree, Graph.
3. Arrays
• Array: A fixed-size data structure that stores elements of the same type in
contiguous memory locations.
o One-Dimensional Array: Linear arrangement accessed by a single index.
o Multi-Dimensional Array: Arrays of arrays (like a matrix).
o Memory Representation: Stored continuously; index-based access is
fast.
o Sparse Matrix: A matrix with many zero values; stored efficiently using
special representations.
4. Searching Algorithms
• Time Complexities:
o Linear Search: O(n)
o Binary Search: O(log n)
• Linear Search: Checks each element sequentially. Simple but slow.
• Binary Search: Efficient for sorted arrays; repeatedly divides search range in
half.
5. Sorting Algorithms
• Time Complexities:
o Selection Sort: O(n²)
o Bubble Sort: Best O(n), Worst/Average O(n²)
o Insertion Sort: Best O(n), Worst/Average O(n²)
o Radix Sort: O(nk) where k is the number of digits
o Merge Sort: O(n log n)
o Shell Sort: Depends on gap sequence (average ~ O(n^1.5))
• Selection Sort: Selects minimum element and places it at the start.
• Bubble Sort: Swaps adjacent elements until sorted.
• Insertion Sort: Inserts elements into their correct position in sorted part.
• Radix Sort: Non-comparative sort; processes digits of numbers.
• Merge Sort: Divide and conquer algorithm for efficient sorting.
• Shell Sort: Improves insertion sort by comparing far elements first.
6. Linked Lists
• Linked List: A dynamic data structure of nodes, each containing data and a
pointer.
o Singly Linked List: Each node points to the next.
o Doubly Linked List: Each node points to both previous and next.
o Circular Linked List: Last node points to the first.
o Header Linked List: Starts with a dummy header node.
7. Polynomial Arithmetic with Linked Lists
• Used to represent and perform operations on polynomials.
• Each node stores a term with a coefficient and exponent.
• Addition: Traverse and combine terms with the same exponent.
8. Stacks and Queues
• Time Complexities:
o Push/Pop/Peek (Stack): O(1)
o Enqueue/Dequeue (Queue): O(1)
Stack:
• A linear structure following LIFO (Last In, First Out).
• Operations: Push, Pop, Peek.
Queue:
• A linear structure following FIFO (First In, First Out).
• Operations: Enqueue, Dequeue.
• Types:
o Circular Queue: Last position connects to first.
o Deque: Insertion/deletion from both ends.
o Priority Queue: Elements have priorities.
9. Polish Notations
• Different ways to write arithmetic expressions:
o Infix: Operator in between operands (A + B).
o Prefix: Operator before operands (+ A B).
o Postfix: Operator after operands (A B +).
• Used for expression evaluation and conversion using stacks.
10. Recursion
• A function calling itself directly or indirectly.
• Used in problems like factorial, Fibonacci, tree traversals, etc.
UNIT II: Trees (Non-Linear Structures)
1. Tree Basics
• A hierarchical structure with one root and multiple levels of children.
• Terminology:
o Root: Topmost node.
o Leaf: Node without children.
o Parent, Child: Direct relationship.
o Height: Longest path from root to a leaf.
o Degree: Number of children a node has.
2. Binary Tree
• Each node has at most two children: left and right.
• Can be used for expression trees and hierarchy models.
3. Binary Search Tree (BST)
• A binary tree with ordering property: left < root < right.
• Supports efficient search, insertion, deletion.
4. Tree Traversals
• Ways to visit all nodes in a tree:
o Inorder: Left → Root → Right
o Preorder: Root → Left → Right
o Postorder: Left → Right → Root
o Level Order: Visit level by level using a queue
5. Threaded Binary Tree
• Uses NULL pointers to store in-order successors.
• Makes in-order traversal faster without recursion or stack.
6. Tree Sort
• Inserts elements into BST and performs inorder traversal to sort them.
• Time Complexity: O(n log n) average, O(n²) worst (if tree becomes unbalanced)
• Inserts elements into BST and performs inorder traversal to sort them.
7. Trie (Prefix Tree)
• A tree to store strings by sharing common prefixes.
• Used in autocomplete and spell-check systems.
8. AVL Tree
• A BST that maintains balance using rotations.
• Balance Factor = height(left) - height(right).
• Rotations:
o LL → Right Rotate
o RR → Left Rotate
o LR → Left + Right Rotate
o RL → Right + Left Rotate
• Time Complexity:
o Search: O(log n)
o Insertion: O(log n)
o Deletion: O(log n)
• A BST that maintains balance using rotations.
• Balance Factor = height(left) - height(right).
• Rotations:
o LL → Right Rotate
o RR → Left Rotate
o LR → Left + Right Rotate
o RL → Right + Left Rotate
M-Way Trees and B-Trees
1. M-Way Tree
• A tree where each node has up to M children.
• Used in multi-level indexing.
2. B-Tree
• A self-balancing M-Way tree.
• Keeps data sorted and balanced; used in databases and file systems.
3. B+ Tree
• A type of B-Tree with data only in leaf nodes.
• Supports faster sequential access.
4. B* Tree
• Enhanced B+ Tree with better space utilization.
Heaps
1. Heap Definition
• A complete binary tree that satisfies the heap property.
o Max-Heap: Parent ≥ children
o Min-Heap: Parent ≤ children
2. Heap Operations
• Heapify: Rearranges array to maintain heap property. Time: O(log n)
• Heap Sort: Sorting using heap. Time: O(n log n)
• Heapify: Converts array into a valid heap.
• Heap Sort: Sorting algorithm using heap.
3. Priority Queue
• An abstract data type where each element has a priority.
• Implemented using heaps to quickly access the highest priority.
UNIT III: Graphs
1. Graph Representation
• Adjacency Matrix: 2D array for direct connections.
• Adjacency List: List of neighbors for each vertex.
2. Graph Traversals
• BFS (Breadth-First Search): Visits level-by-level using a queue.
• DFS (Depth-First Search): Explores as deep as possible using a stack or
recursion.
3. Connected Components
• Subgraphs where all nodes are connected.
4. Spanning Tree & MST
• Spanning Tree: Subgraph that connects all vertices without cycles.
• Minimum Spanning Tree (MST):
o Kruskal’s Algorithm: Greedy approach, sorts edges.
o Prim’s Algorithm: Builds MST from a chosen start node.
5. Shortest Path Algorithms
• Dijkstra’s Algorithm: Time: O(V²) with array, O(E log V) with min-heap
• Floyd-Warshall Algorithm: Time: O(V³)
• Dijkstra’s Algorithm: Finds shortest path from one source to all others. (No
negative weights)
• Floyd-Warshall Algorithm: Finds all pairs shortest paths (handles negative
weights).
6. Topological Sorting
• Applies to Directed Acyclic Graphs (DAG).
• Produces a linear ordering of vertices.
o Kahn’s Algorithm: BFS-based using in-degrees.
o DFS-based: Uses postorder traversal.
UNIT IV: Hashing and File Structures
1. Hashing
• Technique to map keys to indices using a hash function.
• Enables quick data retrieval.
Collision Resolution
• Chaining: Uses linked lists for collisions at the same index.
• Open Addressing:
o Linear Probing: Check next slot.
o Quadratic Probing: Use a quadratic function to find next slot.
o Double Hashing: Uses a second hash function to compute the next slot.
2. File Organization
• Sequential: Data stored one after another.
• Index Sequential: Uses an index for faster searching.
• Relative: Uses a hashing function to locate records.
File Operations in C
• fread(), fwrite() for binary files.
• fseek(), ftell() to manipulate file pointers.
3. External Sorting
• Used when data exceeds main memory size.
• Time Complexity: Depends on disk I/O; typically O(n log n)
• Techniques:
o K-Way Merge Sort: Merges k sorted sequences.
o Balanced Merge: Distributes data across tapes/files.
o Polyphase Merge: Optimized version of balanced merge.
• Used when data exceeds main memory size.
• Techniques:
o K-Way Merge Sort: Merges k sorted sequences.
o Balanced Merge: Distributes data across tapes/files.
o Polyphase Merge: Optimized version of balanced merge.
End of Units I to IV (Detailed, Structured, and Concept-Based Notes)
