UNIT 2: Data Structures - Comprehensive Short Notes

1. Fundamentals of Data Structures and Algorithm Analysis

1.1 Data Structure: Definition & Classification

• Definition: A data structure is a named location that can be used to store and organize data.

• Classification:

  • Linear: Arrays, Linked Lists, Stacks, Queues (elements in a sequence).

  • Non-Linear: Trees, Graphs (hierarchical or networked).

  • Static: Arrays (size fixed at compile time).

  • Dynamic: Linked Lists (size can change at runtime).

1.2 Abstract Data Type (ADT)

• Concept: A theoretical specification of a data type defining operations and behavior, independent of implementation.

• Examples:

  • Stack ADT: push(), pop(), peek(), isEmpty(), isFull().

  • Queue ADT: enqueue(), dequeue(), peek(), isEmpty(), isFull().

1.3 Algorithm

• Definition: A finite sequence of well-defined instructions to solve a problem.

• Characteristics:

  1. Input: Zero or more quantities.

  2. Output: At least one quantity.

  3. Definiteness: Each step precise.

  4. Finiteness: Terminates after finite steps.

  5. Effectiveness: Each step doable.

1.4 Algorithm Efficiency

• Time Complexity: Number of primitive operations (e.g., comparisons, assignments) as function of input size \( n \).

• Space Complexity: Amount of memory used (auxiliary space + input space).

1.5 Asymptotic Notations

• Big-O (Upper Bound): \( f(n) = O(g(n)) \) if \( \exists c > 0, n_0 \) such that \( 0 \leq f(n) \leq c \cdot g(n) \) for all \( n \geq n_0 \).

• Omega (Lower Bound): \( f(n) = \Omega(g(n)) \) if \( \exists c > 0, n_0 \) such that \( 0 \leq c \cdot g(n) \leq f(n) \) for all \( n \geq n_0 \).

• Theta (Tight Bound): \( f(n) = \Theta(g(n)) \) if \( \exists c_1, c_2 > 0, n_0 \) such that \( 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \) for all \( n \geq n_0 \).

[!TIP] Common Pitfall: Big-O describes worst-case; Omega best-case; Theta average-case (if tight).

1.6 Time Complexity Analysis

• Loop Analysis:

  • Single loop: \( O(n) \).

  • Nested loops: Multiply iterations (e.g., two nested loops each \( O(n) \) → \( O(n^2) \)).

• Recurrence Relations:

  • Substitution method: Guess solution, verify by induction.

  • Master Theorem: For \( T(n) = aT(n/b) + f(n) \), compare \( f(n) \) with \( n^{\log_b a} \).

1.7 Space Complexity

• Auxiliary Space: Extra space used by algorithm (excluding input).

• Example: Recursive Fibonacci uses \( O(n) \) stack space; iterative uses \( O(1) \).

2. Arrays and Searching

2.1 Arrays

2.1.1 Array Basics

• Declaration: int arr[10]; (C/C++), int[] arr = new int[10]; (Java).

• Initialization: int arr[] = {1, 2, 3};.

• Types: 1D, 2D (matrix), multi-dimensional.

2.1.2 Address Calculation

• Row-Major Order (C/C++/Java):

  \[ \text{Address}(A[i][j]) = \text{Base} + ((i \times \text{COLS}) + j) \times \text{size} \]

• Column-Major Order (Fortran/Matlab):

  \[ \text{Address}(A[i][j]) = \text{Base} + ((j \times \text{ROWS}) + i) \times \text{size} \]

[!EXAMPLE] For \( A[20][5] \), base=840, size=8 bytes:

Row-major \( A[15][3] = 840 + ((15 \times 5) + 3) \times 8 = 840 + 78 \times 8 = 840 + 624 = 1464 \).

Column-major \( A[15][3] = 840 + ((3 \times 20) + 15) \times 8 = 840 + 75 \times 8 = 840 + 600 = 1440 \).

2.1.3 Sparse Matrices

• Definition: Matrix with mostly zero elements.

• Representations:

  | Method | Structure | Space Complexity | Best For | |--------|-----------|------------------|----------| | Triplet | (row, col, value) array | \( O(\text{non-zero}) \) | General | | CSR | Three arrays: values, col_index, row_ptr | \( O(\text{non-zero} + \text{rows}) \) | Row operations | | CSC | Similar to CSR but column-oriented | \( O(\text{non-zero} + \text{cols}) \) | Column operations |

2.1.4 Array Issues

• Overflow: Inserting when full.

• Underflow: Deleting when empty.

• Compaction: Shifting elements to remove gaps (e.g., after deletion in unordered array).

2.1.5 Closest Sum to Zero

• Algorithm:

  1. Sort array \( O(n \log n) \).

  2. Use two pointers: left=0, right=n-1.

  3. Track min_sum = ∞.

  4. While left < right:

     • sum = arr[left] + arr[right]

     • Update min_sum if |sum| smaller.

     • If sum < 0, left++; else right--.

• Complexity: \( O(n \log n) \) due to sort.

• Optimization: If array already sorted, \( O(n) \).

2.2 Searching Algorithms

2.2.1 Linear Search

• Scan sequentially until found or end.

• Time: \( O(n) \) worst/average, \( O(1) \) best (first element).

• Space: \( O(1) \).

2.2.2 Binary Search

• Precondition: Sorted array.

• Algorithm:

  
  low = 0, high = n-1
  
  while low <= high:
  
      mid = (low + high) / 2
  
      if arr[mid] == key: return mid
  
      else if arr[mid] < key: low = mid + 1
  
      else: high = mid - 1
  
  return -1
  
  

• Time: \( O(\log n) \).

• Space: \( O(1) \) iterative, \( O(\log n) \) recursive (stack).

2.2.3 Fibonacci Search

• Uses Fibonacci numbers to divide array.

• Advantage: Fewer comparisons on average for uniform access.

• Time: \( O(\log n) \), similar to binary but with different mid calculation.

3. Linear Data Structures

3.1 Stacks

3.1.1 Stack ADT & Operations

• LIFO (Last In First Out).

• Operations:

  • push(x): Add to top.

  • pop(): Remove from top.

  • peek(): Return top without removing.

  • isEmpty(), isFull().

3.1.2 Implementation

• Array: Fixed size, top index. Overflow if top == size-1, underflow if top == -1.

• Linked List: Dynamic, top points to head node. No overflow.

3.1.3 Applications

• Expression Conversion: Infix to Postfix/Prefix using precedence.

• Expression Evaluation: Postfix evaluation with stack.

• Balanced Parentheses: Push '(' on stack, pop on ')', check empty at end.

• Recursion: System stack stores function calls.

• Josephus Problem: Circular simulation.

3.1.4 Stack as Recursive Data Structure

• Naturally supports recursion: each call pushes frame onto stack; returns pop frame.

3.2 Queues

3.2.1 Queue ADT & Operations

• FIFO (First In First Out).

• Operations: enqueue(x), dequeue(), peek(), isEmpty(), isFull().

3.2.2 Implementation

• Linear Array: front and rear indices. After dequeue, front moves, leaving unused space at front → inefficient.

• Circular Array: rear = (rear + 1) % size. Reuses space. Overflow if (rear + 1) % size == front.

• Linked List: front and rear pointers. No overflow.

3.2.3 Variations

• Dequeue (Double-Ended Queue): Insert/delete at both ends.

• Priority Queue: Elements with priority; dequeue highest priority first (often implemented with heap).

3.2.4 Applications & Limitations

• Applications: CPU scheduling, IO buffers, printer queues.

• Limitations: Array implementation fixed size; linear array wastes space.

3.3 Linked Lists

3.3.1 Types

• Singly Linked List: Node has data and next.

• Doubly Linked List: Node has prev, data, next.

• Circular Linked List: Last node points to first (or head).

3.3.2 Operations & Time Complexities

3.3.3 Advantages & Drawbacks

• Advantages: Dynamic size, efficient insertion/deletion, no memory waste.

• Drawbacks: Extra memory for pointers, no random access (sequential access only).

3.3.4 Applications

• Polynomial Representation: Each term as node (coefficient, exponent, next).

• Implementing ADTs: Stack, Queue, Dequeue.

• Merging Point of Two Lists:

  
  1. Find lengths len1, len2.
  
  2. Advance longer list by |len1 - len2|.
  
  3. Traverse both together until nodes same (by address).
  
  

  Time: \( O(m+n) \), Space: \( O(1) \).

4. Trees

4.1 Binary Trees

4.1.1 Terminology

• Node: Element.

• Root: Top node.

• Leaf: Node with no children.

• Height: Number of edges on longest path from root to leaf.

• Depth: Number of edges from root to node.

• Level: Depth + 1 (root at level 1).

4.1.2 Properties

• Max nodes at level \( i \): \( 2^{i-1} \).

• Max nodes for height \( h \): \( 2^{h+1} - 1 \).

• Min nodes for height \( h \): \( h + 1 \) (skewed tree).

• For \( n \) nodes, min height = \( \lfloor \log_2 n \rfloor \), max height = \( n-1 \).

4.1.3 Traversals

• In-order: Left → Root → Right (gives sorted order for BST).

• Pre-order: Root → Left → Right (used to copy tree structure).

• Post-order: Left → Right → Root (used to delete tree).

• Level-order (BFS): Visit nodes level by level using queue.

4.1.4 Construction from Traversals

• Need at least two traversals (one must be in-order).

• From in-order + pre-order: First element of pre-order is root; find root in in-order; left part is left subtree, right part is right subtree; recurse.

• From in-order + post-order: Last element of post-order is root; similar process.

4.2 Binary Search Trees (BST)

4.2.1 Definition & Properties

• Left subtree keys < root key.

• Right subtree keys > root key.

• Both subtrees are BSTs.

4.2.2 Operations

• Search: Start at root, go left/right based on comparison. \( O(h) \).

• Insert: Search for leaf position, insert as leaf. \( O(h) \).

• Delete:

  1. Leaf: Simply remove.

  2. One child: Replace with child.

  3. Two children: Find inorder successor (min in right subtree) or predecessor (max in left subtree), copy value, delete successor/predecessor (which has at most one child).

4.2.3 Time Complexity

• Average (balanced): \( O(\log n) \).

• Worst (skewed): \( O(n) \).

4.2.4 Construction & Deletion Example

• Construction: Insert keys in given order.

• Deletion Steps: Follow three cases above.

4.3 Balanced Binary Search Trees

4.3.1 AVL Trees

• Balance Factor (BF): \( \text{BF} = \text{height(left)} - \text{height(right)} \). Must be -1, 0, or 1.

• Rotations:

  • Left-Left (LL): Right rotate on unbalanced node.

  • Right-Right (RR): Left rotate.

  • Left-Right (LR): Left rotate on left child, then right rotate on root.

  • Right-Left (RL): Right rotate on right child, then left rotate on root.

• Insertion: Insert as BST, update heights, check BF from inserted node up to root, perform first unbalanced rotation.

• Deletion: Delete as BST, update heights, check BF, may need multiple rotations up to root.

4.3.2 Red-Black Trees (Brief)

• Properties:

  1. Every node red or black.

  2. Root black.

  3. Red nodes have black children (no two reds adjacent).

  4. Every path from root to leaf has same number of black nodes (black-height).

• Insertion: New node red, fix violations by recoloring and rotations.

• Deletion: Complex; replace node with successor, then fix.

4.3.3 B+ Trees

• All leaves at same level, linked for range queries.

• Internal nodes only store keys (not data), leaves store data pointers.

• Applications: Databases, file systems (e.g., NTFS, HFS).

4.4 Expression Trees

4.4.1 Construction

• Convert infix to postfix using stack.

• Build tree from postfix: scan postfix, push operands, on operator pop two operands, make operator root with popped nodes as children, push back.

4.4.2 Traversals

• In-order: Infix expression (add parentheses for non-leaf operators).

• Pre-order: Prefix expression.

• Post-order: Postfix expression.

4.4.3 Example

Expression: \( (a + b \times c) + (d \times e + f \times g) \)

• Postfix: a b c * + d e * f g * + +

• Tree:

  
        +
  
       / \
  
      +   +
  
     / \ / \
  
    a * d + 
  
       / \ / \
  
      b c e *
  
           / \
  
          f g
  
  

• Traversals:

  • In-order: (a + (b * c)) + ((d * e) + (f * g))

  • Pre-order: + + a * b c + * d e * f g

  • Post-order: a b c * + d e * f g * + +

4.5 Heaps

4.5.1 Definition

• Complete Binary Tree: All levels filled except possibly last, filled left to right.

• Heap Order:

  • Min-Heap: Parent ≤ children.

  • Max-Heap: Parent ≥ children.

4.5.2 Array Implementation

• For node at index \( i \):

  • Parent: \( \lfloor (i-1)/2 \rfloor \)

  • Left child: \( 2i + 1 \)

  • Right child: \( 2i + 2 \)

4.5.3 Operations

• Insert:

  1. Add at end of array.

  2. "Bubble up": Compare with parent, swap if violates heap order, repeat.

  Time: \( O(\log n) \).

• Delete (Extract Min/Max):

  1. Remove root.

  2. Replace root with last element.

  3. "Bubble down": Compare with children, swap with smallest (min-heap) or largest (max-heap) child, repeat.

  Time: \( O(\log n) \).

• Build-Heap: Start from last non-leaf node, heapify each down to root. Time: \( O(n) \).

4.5.4 Analysis

• All operations \( O(\log n) \) except build-heap \( O(n) \).

4.5.5 Applications

• Priority Queue: Efficient min/max access.

• Heap Sort: Repeatedly extract min/max, place at end. Time \( O(n \log n) \), in-place but not stable.

5. Graphs

5.1 Graph Fundamentals

• Vertices (V): Nodes.

• Edges (E): Connections.

• Directed (Digraph): Ordered pair (u,v).

• Undirected: Unordered pair {u,v}.

• Weighted: Edges have weights/costs.

• Terminology:

  • Adjacent: Vertices connected by edge.

  • Path: Sequence of vertices with edges.

  • Cycle: Path starting and ending at same vertex.

  • Connected: Path exists between every pair (undirected).

  • Degree: Number of incident edges (undirected); in-degree/out-degree for directed.

  • DAG: Directed Acyclic Graph.

5.2 Graph Representations

5.3 Graph Traversals

5.3.1 Breadth-First Search (BFS)

• Algorithm:

  1. Start from source, mark visited, enqueue.

  2. While queue not empty:

     • Dequeue vertex \( u \).

     • For each unvisited neighbor \( v \) of \( u \): mark visited, enqueue \( v \).

• Complexity: \( O(V + E) \) (adjacency list), \( O(V^2) \) (matrix).

• Example: Finds shortest path in unweighted graph.

5.3.2 Depth-First Search (DFS)

• Algorithm (recursive):

  
  DFS(u):
  
      mark u visited
  
      for each neighbor v of u:
  
          if v not visited: DFS(v)
  
  

• Stack-based iterative: Push start, while stack not empty: pop, if unvisited mark and push unvisited neighbors.

• Complexity: \( O(V + E) \).

• Note: DFS traversal order depends on neighbor ordering.

5.3.3 BFS vs DFS

5.3.4 Traversing Graph vs Tree

• Graph: May have cycles → need visited array to avoid infinite loops.

• Tree: Acyclic, no cycles → no need for visited (but still used for clarity).

5.3.5 Valid DFS Sequences

• Depends on adjacency list order and stack LIFO.

• Example: Graph with edges a-b, a-f, b-e, b-f, e-h, f-g.

  Valid DFS from a: a b e h f g (if neighbors ordered b,f for a; e,f for b; etc.).

5.4 Graph Algorithms

5.4.1 Minimum Spanning Tree (MST)

• Prim's Algorithm:

  1. Start with arbitrary vertex.

  2. Grow tree by adding minimum-weight edge connecting tree to outside vertex.

  3. Use priority queue for min edge.

  • Time: \( O(E \log V) \) with heap, \( O(V^2) \) with array.

• Kruskal's Algorithm:

  1. Sort all edges by weight.

  2. Add edges in order, skip if forms cycle (use Union-Find).

  • Time: \( O(E \log E) \) (sorting dominates).

• Comparison:

  | | Prim's | Kruskal's | |---|---------|-----------| | Approach | Grows one tree | Grows forest | | Best For | Dense graphs (\( E \approx V^2 \)) | Sparse graphs (\( E \approx V \)) | | Data Structure | Priority queue | Union-Find |

5.4.2 Shortest Path: Dijkstra's Algorithm

• Precondition: Non-negative edge weights.

• Algorithm:

  1. Set distance[source]=0, others=∞.

  2. While vertices unvisited:

     • Pick vertex \( u \) with smallest distance.

     • For each neighbor \( v \) of \( u \): if dist[u] + weight(u,v) < dist[v], update.

• Time: \( O(V^2) \) simple, \( O(E \log V) \) with min-heap.

• Example: Single-source shortest paths.

5.4.3 Connected Components

• Run BFS/DFS from each unvisited vertex; count number of times initiated.

• Time: \( O(V + E) \).

6. Hashing

6.1 Hash Tables

6.1.1 Concept

• Hash Function \( h(k) \): Maps key \( k \) to index in table [0, m-1].

• Load Factor \( \alpha = n/m \): Ratio of entries to buckets. Should be ≤ 0.7 for separate chaining.

6.1.2 Hash Functions

• Division: \( h(k) = k \mod m \). Simple, but m should be prime to reduce collisions.

• Multiplication: \( h(k) = \lfloor m \times (k \times A \mod 1) \rfloor \), where \( A \approx (\sqrt{5}-1)/2 \). Good for any m.

• Mid-square: Square k, extract middle digits.

• String Hashing: Polynomial accumulation: \( h = (\sum_{i=0}^{L-1} \text{char}[i] \times p^i) \mod m \), p prime (e.g., 31).

6.1.3 Rehashing

• When \( \alpha \) exceeds threshold, create new larger table (usually double), rehash all keys.

6.2 Collision Resolution

6.2.1 Separate Chaining

• Each bucket is a linked list (or tree).

• Insert: Append to list at index \( h(k) \).

• Search: Traverse list at \( h(k) \).

• Time: Average \( O(1 + \alpha) \), worst \( O(n) \) if all collide.

6.2.2 Open Addressing

• All elements stored in table itself.

• Probe Sequence: Find next available slot.

  • Linear Probing: \( h(k,i) = (h'(k) + i) \mod m \). Causes primary clustering.

  • Quadratic Probing: \( h(k,i) = (h'(k) + c_1 i + c_2 i^2) \mod m \). Reduces clustering, may not find empty slot if table > half full.

  • Double Hashing: \( h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod m \). \( h_2(k) \) must be non-zero; good distribution.

• Deletion: Lazy deletion (mark as deleted) to avoid breaking probe sequences.

6.2.3 Example: Separate Chaining with key mod 7

Keys: 32, 50, 700, 140, 76, 85, 46, 92, 70, 73, 101.

• Hash values: 32%7=4, 50%7=1, 700%7=0, 140%7=0, 76%7=6, 85%7=1, 46%7=4, 92%7=1, 70%7=0, 73%7=3, 101%7=3.

• Buckets:

  • 0: 700 → 140 → 70

  • 1: 50 → 85 → 92

  • 2: empty

  • 3: 73 → 101

  • 4: 32 → 46

  • 5: empty

  • 6: 76

6.3 HashMap Implementation

• Java HashMap:

  • Uses array of Node<K,V> (key, value, hash, next).

  • Separate chaining with linked list; when list size > 8, converts to red-black tree (Java 8+).

  • Rehash when \( \alpha > 0.75 \).

• C++ unordered_map:

  • Similar separate chaining; implementation-defined (often linked list or vector).

  • Load factor default 1.0.

6.4 Applications of Hashing

• Symbol Tables: Compilers store variable names/attributes.

• Database Indexing: Hash indexes for equality searches.

• Caches: Web caches (URL → content), CPU caches.

• LRU Cache:

  • Use doubly linked list (MRU at head, LRU at tail) + hash map (key → node).

  • On access: Move node to head (if exists, else create).

  • On insert: If full, remove tail (LRU) from list and map; add new node to head.

  • All operations \( O(1) \).

6.5 Issues

• Overflow: Table full → rehash.

• Underflow: Delete from empty table.

• Compaction: In open addressing, after many deletions, may need to rehash to remove gaps.

7. Sorting Algorithms

7.1 Comparison-Based Sorting

7.1.1 Quick Sort

• Algorithm:

  1. Choose pivot (last element common).

  2. Partition: Rearrange so elements < pivot left, > pivot right.

  3. Recursively sort left and right partitions.

• Pivot Selection: First, last, random, median-of-three (better for worst-case).

• Example: Array [26,56,47,36,13,95,85,32], pivot=32:

  • Partition: [26,13] 32 [56,47,36,95,85]

  • Recurse.

• Complexity:

  • Average: \( O(n \log n) \).

  • Worst: \( O(n^2) \) (already sorted with bad pivot).

• Properties: In-place (but not stable), cache-friendly.

7.1.2 Merge Sort

• Algorithm (recursive):

  1. Divide array into two halves.

  2. Recursively sort each half.

  3. Merge two sorted halves.

• Merge: Use temporary array, compare elements from both halves, copy smaller.

• Iterative: Bottom-up, merge pairs of subarrays.

• Complexity: Always \( O(n \log n) \).

• Properties: Stable, not in-place (needs \( O(n) \) extra space).

7.1.3 Selection Sort

• Algorithm:

  1. For i from 0 to n-2:

     • Find min element in [i, n-1].

     • Swap with element at i.

• Complexity: \( O(n^2) \) all cases.

• Properties: In-place, unstable (swaps may change order of equal elements).

7.1.4 Insertion Sort

• Algorithm:

  1. For i from 1 to n-1:

     • key = arr[i]

     • j = i-1

     • While j >= 0 and arr[j] > key: arr[j+1] = arr[j]; j--

     • arr[j+1] = key

• Complexity:

  • Worst: \( O(n^2) \).

  • Best: \( O(n) \) (already sorted).

• Properties: Stable, in-place, adaptive (efficient for nearly sorted).

7.2 Heap Sort

• Algorithm:

  1. Build max-heap from array.

  2. For i from n-1 down to 1:

     • Swap root (max) with arr[i].

     • Heapify root on reduced heap (size i).

• Complexity: \( O(n \log n) \) (build-heap \( O(n) \), n extractions \( O(n \log n) \)).

• Properties: In-place, not stable.

7.3 Sorting Analysis

• Internal vs External Sorting:

  • Internal: Data fits in main memory (all above).

  • External: Data too large, uses disk (e.g., external merge sort, multi-way merge).

8. Special Topics and Integrated Applications

8.1 Polynomial Manipulation

• Representation:

  • Array: Index = exponent, value = coefficient. Efficient for dense polynomials; sparse wastes space.

  • Linked List: Each node: {coeff, exp, next}. Sorted by exponent; efficient for sparse.

• Addition:

  • Traverse both lists simultaneously.

  • If exponents equal, add coefficients; else copy larger exponent node.

  • Time: \( O(m+n) \), where m,n terms.

8.2 Expression Handling

8.2.1 Infix to Postfix Conversion

• Algorithm:

  1. Initialize empty stack.

  2. Scan infix left to right:

     • If operand, output.

     • If '(', push.

     • If ')', pop and output until '('.

     • If operator: while stack top has higher/equal precedence (and not '('), pop and output; then push current operator.

  3. Pop all remaining operators.

• Precedence: ^ > *// > +/-.

• Example: a+b*c → abc*+.

8.2.2 Postfix Evaluation

• Algorithm:

  1. Initialize empty stack.

  2. Scan postfix:

     • If operand, push.

     • If operator: pop two operands (b = pop(), a = pop()), compute a op b, push result.

  3. Final stack top is result.

• Example: 284-5*+:

  • Push 2,8,4 → stack [2,8,4]

  • -: pop 4,8 → 8-4=4, push → [2,4]

  • Push 5 → [2,4,5]

  • *: pop 5,4 → 4*5=20, push → [2,20]

  • +: pop 20,2 → 2+20=22 → result 22.

8.2.3 Balanced Parentheses

• Algorithm:

  1. Initialize empty stack.

  2. For each char in expression:

     • If '(', push.

     • If ')', if stack empty or top not '(', unbalanced; else pop.

  3. After scan, if stack empty → balanced; else unbalanced.

• Time: \( O(n) \), space \( O(n) \) worst-case.

8.3 Josephus Problem

• Problem: n people in circle, count k, eliminate every k-th, find survivor.

• Solution with Circular Linked List:

  • Build circular list with n nodes.

  • Start at head, count k-1 steps, delete current node.

  • Repeat until one node left.

  • Time: \( O(n \times k) \) worst-case.

• Recurrence Solution:

  \[ J(1) = 0, \quad J(n) = (J(n-1) + k) \mod n \]

  (0-indexed; for 1-indexed add 1).

  • Time: \( O(n) \).

8.4 LRU Page Replacement

• Concept: Replace least recently used page when cache full.

• Implementation:

  • Doubly Linked List: MRU at head, LRU at tail.

  • Hash Map: Key → node pointer for O(1) access.

  • On access: Move node to head (if exists).

  • On insert: If full, remove tail (LRU) from list and map; add new node to head.

• Time: All operations \( O(1) \).

8.5 Sparse Matrices

• Efficient Representations: Triplet, CSR, CSC (see 2.1.3).

• Operations:

  • Addition: For CSR/CSC, merge row/column by row/column indices.

  • Multiplication: Use standard algorithm but skip zeros; CSR × CSC efficient.

8.6 Combined Stack-Queue Array Representation

• Problem: Map n objects (n1 stacks, n2 queues) into array [1, n].

• Design:

  • Use separate top[] for stacks, front[] and rear[] for queues.

  • Divide array into contiguous segments for each ADT.

• Algorithms:

  • Stack Push (stack i): if top[i] < segment_end: top[i]++; arr[top[i]] = x; else overflow.

  • Stack Pop: if top[i] > segment_start: x = arr[top[i]]; top[i]--; return x; else underflow.

  • Queue Enqueue (queue i): if (rear[i] + 1) % size != front[i]: rear[i] = (rear[i]+1)%size; arr[rear[i]] = x; else overflow.

  • Queue Dequeue: if front[i] != -1: x = arr[front[i]]; if front[i] == rear[i]: front[i] = rear[i] = -1; else front[i] = (front[i]+1)%size; return x; else underflow.

• Boundary Management: Ensure segments do not overlap; use modulo for circular queues within segment.

[!TIP] Exam Focus:

• Linked Lists: Insertion/deletion (especially after given node), merging point, doubly linked list operations.

• Stacks: Infix to postfix, postfix evaluation, balanced parentheses.

• Queues: Circular queue implementation, advantages over linear queue.

• Trees: BST insertion/deletion (with examples), AVL rotations (drawing), expression tree traversals, tree construction from traversals.

• Graphs: BFS/DFS algorithms with examples, MST comparison (Prim vs Kruskal), Dijkstra's algorithm.

• Hashing: Separate chaining with example, hash functions, HashMap collision handling.

• Sorting: Quick sort/merge sort with examples and complexity derivation, stability analysis.

• Special Topics: Polynomial addition (linked list), Josephus problem, LRU cache.

• Arrays: Address calculation (row/column major), sparse matrix representations, closest sum to zero.

• Complexity: Analyze nested loops, recurrence relations (e.g., \( T(n)=2T(n/2)+n\log n \)).