UNIT 3: Algorithm Design Techniques & Advanced Data Structures

1.0 Fundamentals of Algorithm Analysis

1.1 Asymptotic Notations (Big O, Big Ω, Big Θ)

• Definition & Purpose: Asymptotic notations describe the limiting behavior of a function f(n) as n approaches infinity. They provide a coarse-grained measure of time/space complexity, ignoring constants and lower-order terms.

• Mathematical Interpretations:

  • Big O (Upper Bound): f(n) = O(g(n)) if ∃ positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.

  [!TIP] Used for worst-case analysis. f(n) grows no faster than g(n).

  • Big Ω (Lower Bound): f(n) = Ω(g(n)) if ∃ positive constants c and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.

  [!TIP] Used for best-case analysis. f(n) grows at least as fast as g(n).

  • Big Θ (Tight Bound): f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)). This means f(n) grows at the same rate as g(n).

• Comparing Functions: To compare f(n) and g(n), compute lim_{n→∞} f(n)/g(n).

  • If limit is a positive constant, f(n) = Θ(g(n)).

  • If limit is 0, f(n) = o(g(n)) (strictly smaller, f(n) = O(g(n)) but not Θ(g(n))).

  • If limit is ∞, g(n) = o(f(n)).

1.2 Time & Space Complexity Analysis

• Worst-case: Maximum time/space over all inputs of size n. Most common for guarantees.

  Example: Quick sort worst-case Θ(n²) when pivot is smallest/largest element.

• Average-case: Expected time/space over all possible inputs (assuming a distribution). Harder to compute but often more realistic.

  Example: Quick sort average-case Θ(n log n) assuming random pivot/input.

• Best-case: Minimum time/space over inputs of size n. Often not meaningful alone.

  Example: Binary search best-case Θ(1) if target is middle element.

• When to Prioritize:

  • Worst-case: Critical for real-time systems, safety-critical apps.

  • Average-case: When worst-case is rare and input distribution is known/uniform.

  • Best-case: Rarely used alone; may indicate best possible scenario.

1.3 Recurrence Relations

• Generating Recurrence: From recursive algorithm by counting operations at each level.

  Example: Binary search: T(n) = T(n/2) + Θ(1) (one comparison + recursive call on half).

• Solving Recurrences:

  1. Substitution Method: Guess solution, prove by induction.

     Example: For T(n)=2T(n/2)+n, guess T(n)=O(n log n), prove T(n) ≤ c n log n.

  2. Recursion Tree Method: Visualize cost per level, sum costs. Good for intuition.

     Example: T(n)=3T(n/4)+n² → tree with branching factor 3, subproblem size n/4, cost n² at root.

  3. Master Theorem: For T(n)=aT(n/b)+f(n), where a≥1, b>1.

     Let n^{log_b a} be the critical exponent.

     • Case 1: If f(n)=O(n^{log_b a - ε}) for ε>0, then T(n)=Θ(n^{log_b a}).

     • Case 2: If f(n)=Θ(n^{log_b a} log^k n), then T(n)=Θ(n^{log_b a} log^{k+1} n).

     • Case 3: If f(n)=Ω(n^{log_b a + ε}) and a f(n/b) ≤ c f(n) for c<1, then T(n)=Θ(f(n)).

     [!TIP] Limitations: Only for divide-and-conquer with equal subproblem sizes. Cannot handle e.g., T(n)=T(n-1)+n.

• Complex Recurrences: May require recursion tree or substitution.

  Example: T(n)=n + T(n/10) + T(7n/5) → tree not perfectly balanced; sum costs across levels.

1.4 Amortized Analysis (Brief)

• Idea: Average cost of an operation over a sequence of operations, smoothing out occasional expensive ops with many cheap ones.

• Methods: Aggregate method, accounting method, potential method.

• Example: Dynamic array (vector) insertion: most inserts O(1), occasional resize O(n). Amortized cost O(1).

2.0 Divide and Conquer Paradigm

2.1 General Design Technique & Control Abstraction

• Steps:

  1. Divide: Split problem into a subproblems of size ~n/b.

  2. Conquer: Solve subproblems recursively.

  3. Combine: Merge subproblem solutions into original solution.

• Control Abstraction:

  
  DAndC(P) {
  
      if |P| small: return solution directly;
  
      else {
  
          divide P into P1, P2, ..., Pa;
  
          for i=1 to a: Si = DAndC(Pi);
  
          return combine(S1, S2, ..., Sa);
  
      }
  
  }
  
  

2.2 Recurrence for Divide and Conquer

• General form: T(n) = a·T(n/b) + f(n), where f(n) is cost of divide/combine.

2.3 Binary Search

• Algorithm:

  
  BinarySearch(A, low, high, key) {
  
      if low > high: return NOT_FOUND;
  
      mid = ⌊(low+high)/2⌋;
  
      if A[mid] == key: return mid;
  
      else if key < A[mid]: return BinarySearch(A, low, mid-1, key);
  
      else: return BinarySearch(A, mid+1, high, key);
  
  }
  
  

• Recurrence: T(n) = T(n/2) + Θ(1) → T(n) = Θ(log n).

• Trace: Given sorted array, show recursive calls narrowing range.

2.4 Merge Sort

• Algorithm:

  
  MergeSort(A, l, r) {
  
      if l < r {
  
          m = ⌊(l+r)/2⌋;
  
          MergeSort(A, l, m);
  
          MergeSort(A, m+1, r);
  
          Merge(A, l, m, r); // Merge two sorted halves
  
      }
  
  }
  
  

• Complexity: T(n)=2T(n/2)+Θ(n) → Θ(n log n) (Master Theorem Case 2).

• Trace: Given sequence {23, 11, 5, 15, 68, 31, 4, 17}, show recursive splitting and merging steps.

2.5 Quick Sort

• Partition Algorithm (Lomuto or Hoare):

  
  Partition(A, low, high) {
  
      pivot = A[high]; // or choose via strategy
  
      i = low-1;
  
      for j=low to high-1 {
  
          if A[j] ≤ pivot {
  
              i++;
  
              swap(A[i], A[j]);
  
          }
  
      }
  
      swap(A[i+1], A[high]);
  
      return i+1;
  
  }
  
  

• Pivot Selection Strategies:

  • First/last element (simple, worst-case prone).

  • Random element (averages out worst-case).

  • Median-of-three (better balance).

• Complexity:

  • Worst-case: T(n)=T(n-1)+Θ(n) → Θ(n²) (when pivot is extreme).

  • Average-case: T(n)=Θ(n log n) (assuming random pivot/input).

• Simulation: Trace on given data (e.g., 20, 35, 10, 16, 54, 21, 25), show partition steps and recursive calls.

2.6 Strassen’s Matrix Multiplication

• Algorithm Steps:

  1. Partition n×n matrices A, B into four n/2×n/2 submatrices.

  2. Compute 7 products (P1 to P7) using recursive multiplication on combinations of submatrices.

  3. Derive result submatrices C11, C12, C21, C22 from P1..P7.

• Complexity: T(n)=7T(n/2)+Θ(n²) → T(n)=Θ(n^{log_2 7}) ≈ Θ(n^{2.81}).

• vs Conventional: Conventional Θ(n³). Strassen’s is asymptotically faster for large n, but larger constant factor and numerical instability.

2.7 Finding Maximum and Minimum

• Divide & Conquer Approach:

  
  MinMax(A, low, high) {
  
      if low == high: return (A[low], A[low]); // min, max same
  
      if high == low+1: {
  
          if A[low] < A[high]: return (A[low], A[high]);
  
          else: return (A[high], A[low]);
  
      }
  
      else {
  
          mid = ⌊(low+high)/2⌋;
  
          (min1, max1) = MinMax(A, low, mid);
  
          (min2, max2) = MinMax(A, mid+1, high);
  
          return (min(min1,min2), max(max1,max2));
  
      }
  
  }
  
  

• Recurrence: T(n)=2T(n/2)+2 (two comparisons at combine).

• Worst-case Complexity: T(n)=Θ(n) (solves in ~1.5n comparisons vs 2n-2 in naive).

3.0 Greedy Algorithms

3.1 Greedy Choice Property & Optimal Substructure

• Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice at each step, without reconsidering previous choices.

• Optimal Substructure: An optimal solution to the problem contains within it optimal solutions to subproblems.

• Proof Requirement: Must prove both properties to ensure greedy yields global optimum. If either fails, greedy may be suboptimal.

3.2 Knapsack Problem

• Fractional Knapsack (Greedy works):

  1. Compute profit/weight ratio r_i = p_i/w_i for each item.

  2. Sort items in decreasing order of r_i.

  3. Take items in order until knapsack full; last item may be taken fractionally.

• 0/1 Knapsack (Greedy fails; requires DP):

  Example: Capacity 50, items: (p=60, w=10, r=6), (p=100, w=20, r=5), (p=120, w=30, r=4). Greedy picks item1+item2 (value 160, weight 30), but optimal is item2+item3 (value 220, weight 50).

• Solving Given Instance (e.g., n=7, m=15, P=(10,5,15,7,6,18,3), W=(2,3,5,7,1,4,1)):

  1. Compute ratios: (5, 1.67, 3, 1, 6, 4.5, 3).

  2. Sort by ratio descending: item5(w=1,p=6,r=6), item6(w=4,p=18,r=4.5), item1(w=2,p=10,r=5), item3(w=5,p=15,r=3), item7(w=1,p=3,r=3), item2(w=3,p=5,r=1.67), item4(w=7,p=7,r=1).

  3. Pick sequentially: item5 (w=1, val=6, rem=14), item6 (w=4, val=18, rem=10), item1 (w=2, val=10, rem=8), item3 (w=5, val=15, rem=3), item7 (w=1, val=3, rem=2). Cannot take item2 (w=3>2). Total value = 52.

3.3 Job Sequencing with Deadlines

• Problem: Schedule jobs with profits p_i and deadlines d_i (1 unit time each) to maximize total profit, each job finishes by its deadline.

• Greedy Algorithm:

  1. Sort jobs by decreasing profit.

  2. Initialize result array slot[1..max_deadline] as empty.

  3. For each job in sorted order, place it in latest available slot before its deadline.

• Using Disjoint Sets: Efficiently find latest free slot using Union-Find with path compression.

• Solving Given Instance (e.g., n=4, P=(100,10,15,27), D=(2,1,2,1)):

  1. Sort by profit: J1(p=100,d=2), J4(p=27,d=1), J3(p=15,d=2), J2(p=10,d=1).

  2. Place J1 in slot 2. Place J4 in slot 1. J3 has no slot before d=2 (slot 2 taken). J2 no slot before d=1 (slot 1 taken).

  3. Selected jobs: J1, J4. Total profit = 127.

3.4 Minimum Cost Spanning Tree (MST)

• Definition: Spanning tree of a connected, weighted graph with minimum total edge weight.

• Kruskal’s Algorithm:

  1. Sort all edges in non-decreasing weight.

  2. Initialize MST as empty, use Union-Find (disjoint sets) for cycle detection.

  3. For each edge in sorted order, if it connects two different sets (no cycle), add it to MST and union the sets.

  4. Stop when MST has V-1 edges.

  [!TIP] Cycle Detection: FindSet(u) != FindSet(v) means no cycle.

• Prim’s Algorithm:

  1. Start with arbitrary vertex r in MST.

  2. Grow MST by adding minimum weight edge connecting MST to a vertex outside MST.

  3. Use priority queue (min-heap) keyed by edge weight to efficiently find min edge.

  4. Stop when all vertices included.

  [!TIP] Implementation: key[v] = min weight edge connecting v to MST. Extract-Min from PQ gives next vertex.

• Uniqueness with Distinct Weights: If all edge weights are distinct, MST is unique. Proof by contradiction: assume two different MSTs, consider first edge where they differ; the lighter edge must be in the MST (cut property), contradiction.

• Step-by-Step Application: Given graph, show edge selection order for both algorithms.

3.5 Huffman Coding

• Building Optimal Prefix Codes:

  1. Create min-heap (priority queue) of nodes, each with symbol and probability/frequency.

  2. While heap size > 1:

     • Extract two nodes with smallest probabilities.

     • Create new internal node with probability = sum, left/right children = extracted nodes.

     • Insert new node into heap.

  3. Final node is root of Huffman tree.

• Constructing Tree from Probabilities (e.g., a:0.07, b:0.09, c:0.12, d:0.22, e:0.23, f:0.27):

  1. Initial leaves: (a.07), (b.09), (c.12), (d.22), (e.23), (f.27).

  2. Merge a+b=0.16 → node N1.

  3. Merge N1(0.16)+c(0.12)=0.28 → N2.

  4. Merge d(0.22)+e(0.23)=0.45 → N3.

  5. Merge N2(0.28)+f(0.27)=0.55 → N4.

  6. Merge N3(0.45)+N4(0.55)=1.0 → root.

• Average Code Length: L_avg = Σ (p_i × l_i), where l_i = code length (depth of leaf).

  Example: If f gets code '0' (len=1), e gets '10' (len=2), d gets '110' (len=3), N3 gets '1110' (len=4), N2 gets '1111' (len=4), then a,b,c under N2 get longer codes. Compute L_avg from tree.

3.6 Optimal Merge Patterns

• Problem: Merge k sorted files with lengths l1, l2, ..., lk into one sorted file. Cost to merge two files of lengths a,b is a+b. Find merge order minimizing total cost.

• Relation to Huffman: Identical to building Huffman tree where file lengths = frequencies. Greedy: always merge two smallest files.

• Algorithm: Use min-heap of file lengths. Repeatedly extract two smallest, merge (cost = sum), insert sum back. Total cost = sum of all merge costs.

• Example: Files sizes {10, 20, 30, 40}:

  1. Merge 10+20=30 (cost=30), heap={30,30,40}.

  2. Merge 30+30=60 (cost=60), heap={40,60}.

  3. Merge 40+60=100 (cost=100). Total cost = 190.

4.0 Dynamic Programming

4.1 Overlapping Subproblems & Optimal Substructure

• Overlapping Subproblems: Problem can be broken down into subproblems which are reused multiple times (vs divide-and-conquer where subproblems are distinct). DP solves each subproblem once and stores solution (memoization/tabulation).

• Optimal Substructure: Optimal solution to problem can be constructed from optimal solutions to subproblems. Must identify recursive relationship.

4.2 0/1 Knapsack Problem

• Tabulation (Bottom-up):

  
  DP[i][w] = max(DP[i-1][w], DP[i-1][w - W_i] + P_i) if W_i ≤ w
  
           = DP[i-1][w] otherwise
  
  

  where DP[i][w] = max value using first i items, capacity w.

• Memoization (Top-down): Recursive with memo[i][w] cache.

• Solving Given Instance (P=(11,21,31,33), W=(2,12,23,15), C=42, n=4):

  Build DP[5][43] table. Fill row by row.

  • Row1 (item1, w=2): DP[1][2..42]=11.

  • Row2 (item2, w=12): DP[2][12..42]=max(11, 21)=21; DP[2][14..42]=32 (11+21).

  • Row3 (item3, w=23): DP[3][23]=31, DP[3][25..42]=max(prev, 31+11=42), etc.

  • Row4 (item4, w=15): DP[4][15]=33, DP[4][17..42]... Final DP[4][42] = 62 (items 1,3,4: 11+31+33=75? Wait check: w1+w3+w4=2+23+15=40 ≤42, value=11+31+33=75. But DP[4][42] should be 75. Let's compute carefully:

    • After row3: DP[3][40] = max(DP[2][40], DP[2][17]+31). DP[2][40]=32 (items1+2), DP[2][17]=32 (items1+2), so DP[3][40]=63 (items1+2+3? w=2+12+23=37, val=11+21+31=63). Actually DP[3][40] should be 63.

    • Row4: for w=42, DP[4][42] = max(DP[3][42], DP[3][27]+33). DP[3][42] likely 63 (items1+2+3). DP[3][27] = max(DP[2][27], DP[2][4]+31). DP[2][27] = 32 (items1+2), DP[2][4] = 11 (item1), so DP[3][27]=42 (items1+3). Then DP[3][27]+33=75. So DP[4][42]=75. Optimal value = 75 (items 1,3,4).

  Trace table in exam.

4.3 All-Pairs Shortest Paths: Floyd-Warshall

• Algorithm:

  
  FloydWarshall(W) { // W is adjacency matrix, W[i][i]=0, W[i][j]=∞ if no edge
  
      let D = W; // copy
  
      for k=1 to n:
  
          for i=1 to n:
  
              for j=1 to n:
  
                  D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
  
      return D;
  
  }
  
  

• Recurrence: D_k[i][j] = min(D_{k-1}[i][j], D_{k-1}[i][k] + D_{k-1}[k][j]) — shortest path using vertices 1..k as intermediates.

• Complexity: Θ(n³).

• Application: Given graph/adjacency matrix, compute D step-by-step for k=1..n.

• Transitive Closure: Modify to boolean: C[i][j] = C[i][j] OR (C[i][k] AND C[k][j]).

4.4 Multistage Graph Problem

• Problem: Directed acyclic graph with stages. Find minimum cost path from start s to terminal t.

• Forward Approach:

  1. Label vertices in each stage.

  2. f(1) = 0 (cost from start to stage1).

  3. For stage j=2 to n: f(j) = min_{i<j} [ f(i) + cost(i,j) ].

  4. f(n) is min cost to t. Backtrack to find path.

• Backward Approach: Similar, start from t backward.

• Algorithm & Computing Time: O(|V|+|E|) if stages known; typically O(n²) for dense graph.

4.5 Reliability Design Problem

• Problem: Design k-stage system with devices of types d1,d2,...,dm at each stage. Each device type has cost c_i and reliability r_i. Total system cost ≤ C. Maximize system reliability R = r1 × r2 × ... × rk (series system).

• DP Solution:

  • R[i][j] = max reliability for first i stages with cost ≤ j.

  • Recurrence: R[i][j] = max_{all device types d at stage i with cost c_d ≤ j} [ R[i-1][j - c_d] × r_d ].

  • Fill table for i=1..k, j=0..C.

• Example: 3 stages, costs (30,15,20), reliabilities (0.9,0.8,0.5), total cost ≤ 105. Compute max R[3][j] for j≤105.

4.6 Longest Common Subsequence (LCS)

• Problem: Given sequences X[1..m], Y[1..n], find longest subsequence common to both.

• DP Recurrence:

  
  if X[i] == Y[j]: LCS[i][j] = LCS[i-1][j-1] + 1
  
  else: LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
  
  

• Complexity: Θ(mn) time and space. Can reduce space to O(min(m,n)).

5.0 Backtracking

5.1 General Backtracking Framework

• State-Space Tree: Tree where each node represents a partial solution (subsequence of decisions). Root = no decisions, leaves = complete solutions or dead ends.

• Pruning Strategies:

  • Bounding: If partial solution cannot lead to feasible/optimal solution, prune subtree.

  • Constraint Satisfaction: Check constraints at each node; if violated, prune.

• Algorithm Template:

  
  Backtrack(candidate) {
  
      if candidate is complete solution: output and return;
  
      else {
  
          for each possible extension of candidate {
  
              if extension is feasible:
  
                  Backtrack(extension);
  
          }
  
      }
  
  }
  
  

5.2 n-Queens Problem

• Problem: Place n queens on n×n chessboard so no two attack each other (no same row, column, diagonal).

• Backtracking:

  1. Place queens row by row.

  2. For row i, try each column j:

     • Check if (i,j) is safe (no queen in same column or diagonal).

     • If safe, place queen and recurse for row i+1.

     • If no safe column in row i, backtrack.

• 4-Queen Solution: One solution: (2,4,1,3) meaning queen in row1 col2, row2 col4, row3 col1, row4 col3.

• State-Space Tree: Nodes represent partial placements. Prune when conflict detected.

5.3 Subset Sum Problem

• Problem: Given set S={s1,...,sn} and target X, find subset summing exactly to X.

• Backtracking:

  
  SubsetSum(i, current_sum) {
  
      if current_sum == X: output subset; return;
  
      if i > n or current_sum > X: return; // prune
  
      // Include si
  
      SubsetSum(i+1, current_sum + s[i]);
  
      // Exclude si
  
      SubsetSum(i+1, current_sum);
  
  }
  
  

• Solving Given Instance (S={1,3,4,5}, X=8):

  • Paths: (1+3+4=8), (3+5=8), (1+2? no 2). Solutions: {1,3,4}, {3,5}.

  • State-space tree shows branches including/excluding each element.

5.4 Graph Coloring Problem (m-coloring)

• Problem: Color graph vertices with at most m colors so adjacent vertices have different colors.

• Backtracking:

  
  mColoring(v) {
  
      if v > n: return true; // all colored
  
      for color=1 to m {
  
          if color is safe for v (no neighbor has it) {
  
              color[v] = color;
  
              if mColoring(v+1): return true;
  
              color[v] = 0; // backtrack
  
          }
  
      }
  
      return false;
  
  }
  
  

• Example: 3-coloring a triangle (m=2 fails, m=3 succeeds).

5.5 Hamiltonian Cycle Problem

• Problem: Find cycle visiting each vertex exactly once in undirected graph.

• Backtracking:

  1. Start at vertex v0, path [v0].

  2. For each neighbor u of last vertex in path:

     • If u not in path and u is start vertex (and path length = n), found cycle.

     • Else if u not in path, add u and recurse.

  3. Backtrack if no extension possible.

• Identifying Cycles: When path length = n and last vertex connects to start.

6.0 Branch and Bound

6.1 Core Concepts

• Live Node: Node whose children are not yet generated (candidate for expansion).

• Dead Node: Node that cannot be expanded further (feasible complete solution or infeasible).

• E-node (Expansion Node): Live node selected for expansion (based on bounding function).

• Bounding Function: Computes upper/lower bound on best possible solution in subtree. Used to prune if bound worse than current best.

• Common Strategy: Use priority queue (min-heap for minimization, max-heap for maximization) keyed by bound. E-node = node with best bound.

6.2 Traveling Salesperson Problem (TSP)

• Problem: Find minimum-cost Hamiltonian cycle in complete weighted graph.

• Reduction to Branch and Bound:

  1. Cost Matrix C[i][j] (∞ if no edge). Assume symmetric? Not necessarily.

  2. Bounding: For partial path v1→v2→...→vk, lower bound = cost so far + minimum outgoing edge from vk to unvisited vertices + minimum incoming edge to v1 from unvisited (to close cycle) + minimum spanning tree on unvisited vertices? Actually common simple bound: cost_sofar + min_{i∈unvisited} min_{j∈unvisited, j≠i} C[i][j] (but careful to avoid double counting). More precise: reduce matrix by row/column minima (like assignment problem).

  3. State: Partial tour (ordered list of visited vertices).

  4. Branch: Extend partial tour by adding one unvisited vertex.

  5. Bound: Compute lower bound for each child using reduced cost matrix.

• Nearest Neighbor Heuristic (Approximation):

  1. Start at arbitrary city.

  2. Repeatedly go to nearest unvisited city.

  3. Return to start.

• Accuracy Ratio: (Cost_approx / Cost_optimal). For TSP, nearest neighbor can be Θ(log n) worst-case.

• Solving Given 5x5 Matrix:

  Given matrix (∞ on diagonal):

  
  ∞  20 30 10 11
  
  15 ∞ 16  4  2
  
   3  5 ∞  2  4
  
  19  6 18 ∞  3
  
  16  4  7 16 ∞
  
  

  • Start at city 1 (index 0). Reduce matrix (subtract row/col minima), compute bound.

  • Branch on possible next cities (2,3,4,5). Compute bound for each child.

  • Choose child with smallest bound as E-node, expand.

  • Continue until complete tour found. Track best complete tour cost as upper bound to prune.

6.3 Comparison with Backtracking

7.0 Graph Algorithms

7.1 Graph Traversals

• Breadth-First Search (BFS):

  • Uses queue.

  • Visits vertices in increasing distance from start.

  • Applications: Shortest path in unweighted graph, connectivity, bipartite check.

• Depth-First Search (DFS):

  • Uses stack (recursion or explicit).

  • Explores as far as possible along each branch before backtracking.

  • Applications: Topological sort, connectivity, cycle detection, SCC (Kosaraju/Tarjan).

• Key Differences:

  | BFS | DFS | |-----|-----| | Queue (FIFO) | Stack (LIFO) | | Level-order | Depth-order | | Finds shortest path (unweighted) | Not necessarily shortest | | More memory (queue size) | Less memory (stack depth) |

7.2 Topological Sorting

• For Directed Acyclic Graph (DAG) only.

• Using DFS:

  1. Perform DFS, push vertex to stack after visiting all its descendants (postorder).

  2. Pop stack to get topological order.

• Algorithm:

  
  TopologicalSort(G) {
  
      for each vertex u: color[u]=WHITE;
  
      stack S;
  
      for each vertex u:
  
          if color[u]==WHITE: DFS-Visit(u);
  
      return S; // pop order
  
  }
  
  DFS-Visit(u) {
  
      color[u]=GRAY;
  
      for each v adjacent to u:
  
          if color[v]==WHITE: DFS-Visit(v);
  
      color[u]=BLACK;
  
      S.push(u);
  
  }
  
  

7.3 Strongly Connected Components (SCC) (Brief)

• Definition: Maximal set of vertices where every vertex reachable from every other.

• Kosaraju’s Algorithm:

  1. DFS on G, get vertices in order of finishing times.

  2. Transpose graph G^T (reverse edges).

  3. DFS on G^T in decreasing finishing time order from step 1. Each DFS tree = SCC.

7.4 Minimum Spanning Tree (Revisited)

• Covered in Greedy section (Kruskal, Prim).

8.0 Advanced Tree Structures

8.1 B-Trees

• Properties (order t):

  • Each node (except root) has at least t-1 keys, at most 2t-1 keys.

  • Root has at least 1 key (if not leaf).

  • All leaves at same depth.

  • Node with k keys has k+1 children.

  • Keys in node sorted; keys in subtree i are between keys i-1 and i.

• Insertion:

  1. Find leaf node L where key belongs.

  2. If L has < 2t-1 keys, insert directly.

  3. If L full (2t-1 keys), split:

     • Median key m moves up to parent.

     • L splits into two nodes with t-1 keys each.

     • Insert new key into appropriate half.

     • If root splits, new root created (height increases).

• Deletion Cases (from node L containing key k):

  1. Case 1: k in leaf L and L has ≥ t keys → simply remove k.

  2. Case 2: k in leaf L but L has exactly t-1 keys:

     • If left sibling has ≥ t keys, borrow one key from sibling via parent.

     • Else if right sibling has ≥ t keys, borrow from right.

  3. Case 3: k in leaf L but both siblings have t-1 keys:

     • Merge L with one sibling (and key from parent) → new node has 2t-2 keys.

     • Key k removed, parent loses a key. May cause parent to underflow → recurse up.

  4. Case 4: k in internal node L:

     • Let c_pred, c_succ be children before/after k.

     • If c_pred has ≥ t keys, replace k with predecessor (max in c_pred), recursively delete predecessor from c_pred.

     • Else if c_succ has ≥ t keys, replace k with successor (min in c_succ), recursively delete successor.

     • Else both have t-1 keys → merge c_pred, k, c_succ into one node (has 2t-1 keys), delete k from merged node, recurse up.

• Example-based deletion: Given B-tree of order t=3, show deletion steps for a key.

8.2 AVL Trees

• Property: For each node, |height(left) - height(right)| ≤ 1 (balance factor ∈ {-1,0,1}).

• Rotations (single):

  • LL (left-left): Right rotate at unbalanced node.

  • RR (right-right): Left rotate.

• Rotations (double):

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

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

• Insertion: Insert as BST, then backtrack to root, update heights, rebalance if |bf|>1. First unbalanced node determines rotation type.

• Deletion: Delete as BST, then backtrack to root, update heights, rebalance (may need multiple rotations up the path).

8.3 Binomial Heaps

• Properties:

  • Collection of binomial trees (like B-tree but different).

  • Binomial tree B_k: order k, 2^k nodes, root degree k, children are B_{k-1}, B_{k-2}, ..., B_0.

  • Heap property: each node ≥ parent (min-heap).

  • Root list: roots of binomial trees in increasing order of degree.

  • At most one binomial tree of any degree (like binary representation of number of nodes).

• Operations:

  • Union (Meld):

    1. Merge root lists of two heaps in increasing degree order (like merging sorted lists).

    2. Traverse merged list, if two consecutive trees have same degree x, link them (make one child of other) to form tree of degree x+1.

    3. Repeat until no two consecutive same degree.

  • Find-Minimum: Scan root list (size O(log n)).

  • Insert: Create 1-node heap, union with existing → O(log n).

  • Extract-Min: Remove min root, reverse its children to form new heap, union with remaining → O(log n).

8.4 Binary Tree Traversals & Construction

• Constructing Tree from Preorder + Inorder:

  1. First element of preorder = root.

  2. Find root in inorder → left subtree (elements before root), right subtree (elements after).

  3. Recurse on left/right subtrees with corresponding preorder segments.

• Deriving Postorder from Preorder + Inorder:

  • After constructing tree, do postorder traversal (left, right, root).

• Example:

  • Inorder: B C A E G D H F I J

  • Preorder: A B C D E G F H I J

  1. Root = A (preorder first).

  2. In inorder: left = B C A → wait, root A at position 3? Actually inorder: B C A E G D H F I J. A is 3rd element. So left subtree inorder: B C (2 elements), right: E G D H F I J (7 elements).

  3. Preorder after A: B C D E G F H I J. Left subtree preorder: first 2 elements B C. Right: rest D E G F H I J.

  4. Recurse: left subtree root B, its left empty? Inorder B C: B root, right C. So left subtree: B with right child C.

  5. Right subtree: preorder D E G F H I J, inorder E G D H F I J. Root D. In inorder: E G left? Actually D at position? Inorder: E G D H F I J → D is 3rd. Left: E G (2), right: H F I J (4). Preorder after D: E G F H I J. Left preorder: E G (2), right: F H I J (4).

  6. Continue... Finally postorder: C B G E H I J F D A? Let's derive properly:

     • Left subtree of A: (B with right C) → postorder: C B.

     • Right subtree of A: root D, left (E with right G) → postorder: G E; right (F with left H, right (I with right J)? Actually from inorder right: H F I J. Preorder right: F H I J. Root F, left H, right (I with right J) → postorder: H J I F.

     • So right subtree postorder: left part G E, then right part H J I F, then root D → G E H J I F D.

     • Full postorder: left C B, right G E H J I F D, root A → C B G E H J I F D A.

  Verify with tree construction.

9.0 Sorting Algorithms & Stability

9.1 Stability in Sorting

• Definition: A sorting algorithm is stable if equal elements retain their relative order after sorting.

• Importance: Crucial when sorting by multiple keys (e.g., first by name, then by age; stable sort preserves name order within same age).

• Stable Algorithms: Merge sort, insertion sort, bubble sort, counting sort, radix sort.

• Unstable Algorithms: Quick sort, heap sort, selection sort, shell sort.

• Reason for Instability:

  • Quick sort: swapping may move equal elements across pivot.

  • Heap sort: extract-min may disrupt order.

  • Selection sort: swaps non-adjacent elements.

9.2 Heap Sort

• Algorithm:

  1. Build-Max-Heap from array: for i = ⌊n/2⌋ down to 1, Heapify(A,i).

  2. For i = n down to 2:

     • Swap A[1] (max) with A[i] (move max to end).

     • Reduce heap size by 1.

     • Heapify(A,1) on reduced heap.

• Heapify (sift-down):

  
  Heapify(A, i) {
  
      l = 2i, r = 2i+1;
  
      largest = i;
  
      if l ≤ heap_size and A[l] > A[i]: largest = l;
  
      if r ≤ heap_size and A[r] > A[largest]: largest = r;
  
      if largest != i:
  
          swap(A[i], A[largest]);
  
          Heapify(A, largest);
  
  }
  
  

• Step-by-Step Trace: Given array, show build-heap phase, then extraction phases.

9.3 Decision Trees for Sorting

• Concept: Model comparison-based sorting as binary decision tree. Each internal node = comparison x_i < x_j?, leaves = permutations.

• Lower Bound: Any comparison sort must have at least n! leaves (one per permutation). Height h satisfies 2^h ≥ n! → h ≥ log₂(n!) = Θ(n log n).

• Example for 3-Element Selection Sort:

  • First pass: compare all pairs to find min? Actually selection sort: find min among 3 (2 comparisons), swap to front. Then find min among remaining 2 (1 comparison). Total 3 comparisons.

  • Decision tree: root compare a,b; based on result, compare a,c or b,c etc. Height = 3 = ⌈log₂(3!)⌉ = ⌈log₂6⌉ = 3.

10.0 Complexity Theory & Problem Classes

10.1 Complexity Classes

• P: Problems solvable in polynomial time by deterministic Turing machine.

  Example: Sorting, shortest path (Dijkstra), MST.

• NP: Problems verifiable in polynomial time by deterministic Turing machine (given a certificate). Equivalently, solvable in polynomial time by nondeterministic Turing machine.

  Example: Boolean satisfiability (SAT), TSP decision version (is there tour ≤ K?).

• NP-Complete: Problems in NP that are NP-hard.

  • NP-hard: At least as hard as any NP problem. Every NP problem reduces to it in polynomial time. Not necessarily in NP.

  Example: Halting problem is NP-hard but not in NP (undecidable).

• Venn Diagram: P ⊆ NP. NP-complete = NP ∩ NP-hard. If P = NP, then P = NP = NP-complete.

• Reducibility: L1 ≤p L2 (polynomial-time many-one reduction) means L1 can be solved using oracle for L2 in polynomial time. If L2 ∈ P and L1 ≤p L2, then L1 ∈ P.

10.2 Proving NP-Completeness

1. Show problem L is in NP (give polynomial-time verifier).

2. Choose known NP-complete problem L' (e.g., 3-SAT, CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE).

3. Construct polynomial-time reduction L' ≤p L:

   • Given instance I of L', transform to instance I' of L in polynomial time.

   • Prove: I is yes-instance of L' iff I' is yes-instance of L.

• Common Reductions:

  • 3-SAT → CLIQUE: variable-clause graph.

  • CLIQUE → VERTEX COVER: complement graph.

  • VERTEX COVER → HAMILTONIAN CYCLE: gadget construction.

10.3 Lower Bound Theory

• Algebraic Problems:

  • Sorting: Ω(n log n) comparisons (decision tree argument).

  • Merging two sorted lists of total length n: Ω(n) comparisons (obvious).

  • Element uniqueness: Ω(n log n) (reduction from sorting).

• Comparison-based: Any algorithm that only compares elements has same lower bound as sorting for problems that require ordering.

11.0 Special Topics & Emerging Areas

11.1 Data Stream Algorithms

• Context: Massive data streams (e.g., network packets, sensor data) too large to store.

• Goal: Compute approximate statistics (distinct elements, heavy hitters, quantiles) using limited memory (sublinear in n).

• Techniques: Hashing, sampling, sketching (e.g., Flajolet-Martin for distinct count, Count-Min Sketch for frequency).

11.2 Approximation Algorithms

• Goal: Find near-optimal solution in polynomial time for NP-hard optimization problems.

• Performance Ratio ρ: For minimization, cost(approx) ≤ ρ × cost(optimal). For maximization, cost(approx) ≥ cost(optimal)/ρ.

• PTAS (Polynomial-Time Approximation Scheme): For any ε>0, produces (1+ε)-approximation in time polynomial in n (but may be exponential in 1/ε).

• FPTAS (Fully PTAS): Running time polynomial in both n and 1/ε.

• Examples: Knapsack PTAS (greedy by profit, then DP on top items), TSP with triangle inequality (2-approximation via MST).

11.3 Data Transfer Optimization

• Problems: Scheduling jobs on machines, minimizing makespan (multiprocessor scheduling), network flow for bandwidth allocation.

• Techniques: Greedy (list scheduling), DP for small instances, approximation algorithms (e.g., 2-1/m approximation for makespan).

11.4 Parallel Algorithms

• Design Considerations:

  • Decomposition: Divide work among processors (task, data, pipeline).

  • Synchronization: Barriers, locks, lock-free.

  • Load Balancing: Avoid idle processors.

  • Communication: Minimize inter-processor communication.

• Complexity Measures:

  • Work T₁: Time on 1 processor.

  • Span T∞ (critical path length): Longest chain of dependencies.

  • Parallel Time T_p on p processors.

  • Speedup S_p = T₁/T_p. Efficiency E_p = S_p/p.

  • Work Law: T_p ≥ T₁/p. Span Law: T_p ≥ T∞.

  • Greedy Scheduler: Achieves T_p = O(T₁/p + T∞).

11.5 Logic Optimization (Brief)

• Context: Digital circuit design, Boolean function minimization.

• Goal: Simplify Boolean expressions (e.g., using Karnaugh maps, Quine-McCluskey algorithm) to reduce gate count.

• Relation to Algorithms: Often uses greedy (choose prime implicants) or DP (for large functions).

12.0 Miscellaneous & Integrated Problems

12.1 Comparing Algorithm Design Techniques

12.2 Trade-offs: Readability vs Optimization

• Sacrifice Readability for Optimization When:

  • Performance is critical (real-time systems, high-frequency trading).

  • Profiling shows bottleneck; optimization yields significant gain.

  • Code is library-level (used by many) and optimization benefits all users.

• Do Not Sacrifice When:

  • Code is maintained by team; readability ensures maintainability.

  • Optimization is premature (not based on measurement).

  • Optimization introduces bugs or reduces clarity marginally for negligible gain.

• Guideline: Write clear, correct code first; optimize only after profiling and if necessary.

12.3 Recurrence Solving Practice

• Master Theorem applicable: T(n)=aT(n/b)+f(n).

• Substitution: Guess O(n²), prove T(n) ≤ c n².

• Recursion Tree: Sum costs per level.

• Complex Recurrence: T(n)=n + T(n/10) + T(7n/5):

  • Tree not balanced; left branch size n/10, right 7n/5.

  • Depth of right branch: (7/5)^k n ≈ 1 → k ≈ log_{5/7} n (negative? Actually 7/5>1, so depth O(log n)).

  • At level i, total work from n terms: n * ( (1/10 + 7/5)^i )? Actually branching factors differ. Sum geometric series with ratio 7/5 dominant → total work dominated by last level? Compute carefully: total work = n + n/10 + 7n/5 + (n/10² + 2*(n/10)*(7n/5)? No, each node spawns two children of different sizes. Sum of sizes at level k: n * ( (1/10 + 7/5)^k )? Not exactly because tree not symmetric. But 7/5 > 1, so size grows geometrically → total work Θ(n^{(7/5)^k})? Actually if at each node, total size of children = n/10 + 7n/5 = 1.5n, so total work grows exponentially? Wait: T(n)=n + T(n/10)+T(7n/5). If nlarge,T(7n/5)dominates. LetS(n)=T(7n/5). Then S(n)= (7n/5) + S(n/50) + S(49n/25). The 49n/25 = 1.96nterm grows faster. Eventually size > originaln, so recurrence may not terminate? Actually n/10shrinks, but7n/5grows. Fornlarge enough,7n/5 > n, so recursion doesn't terminate? That suggests recurrence not well-defined for large n? Possibly ndecreases in some branches? ActuallyT(7n/5)with7n/5 > nmeans argument increases → infinite recursion. So recurrence only makes sense ifneventually becomes small? But7n/5grows, so unless base case triggers fornsmall, it diverges. So perhaps recurrence isT(n)=n + T(n/10) + T(7n/5)but with condition thatn/10and7n/5are integers? Still7n/5 > nforn>0. So recurrence **invalid** for large n? In exam, likely they expect using recursion tree: at each node, total work from children = n/10 + 7n/5 = 1.5n. So work per level multiplies by 1.5? But number of nodes doubles? Actually each node has two children, so number of nodes at level kis2^k. But sizes differ. Sum of sizes at level k: let S_k= sum ofnvalues at levelk. S_0 = n. S_{k+1} = S_k/10 + 7S_k/5 = (0.1 + 1.4) S_k = 1.5 S_k. So S_k = n * (1.5)^k. Work at level kisS_k. Total work = Σ_{k=0}^{∞} S_kdiverges because1.5>1. So recurrence T(n)=∞forn>0? That can't be. Possibly misprint: maybe T(n)=n + T(n/10) + T(n/5)? Or T(n)=n + T(n/10) + T(7n/10)`? Given past paper: "Find the time complexity of the recurrence relation

$$T(n)=n+T\left(\frac{n}{10}\right)+T\left(\frac{7n}{5}\right).$$

" That is exactly as written. But 7n/5 > n, so one branch increases size. Unless base case for n small? But then T(7n/5) for n large will keep increasing until overflow. So recurrence not well-defined. Possibly they meant T(n)=n + T(n/10) + T(7n/10)? Or T(n)=n + T(n/10) + T(7n/5) with n decreasing in some way? Actually if n is integer, 7n/5 may not be integer. But conceptually, if 7n/5 > n, then T(7n/5) > T(n)? That suggests T(n) grows faster than linear? But recurrence says T(n) = n + ..., so if T(7n/5) is much larger, then T(n) is dominated by T(7n/5). Let n large, T(n) ≈ T(7n/5). Then T(n) ≈ T((7/5)^k n). As k→∞, argument →∞, so T(n) infinite unless base case at some large n? Not sensible. So likely typo in past paper. In such case, in exam, note that recurrence does not terminate or is invalid because one subproblem size > n. But if forced, assume n decreases overall? Maybe they meant T(n)=n + T(n/10) + T(7n/10)? That would give a=2, b=10/7? Not standard. Alternatively, maybe T(n)=n + T(n/10) + T(7n/5) with n representing something else? I'll skip detailed solution due to inconsistency. In notes, just say: "Recurrence with subproblem sizes n/10 and 7n/5 has one increasing size; such recurrence may not be well-defined for large n as it doesn't shrink. Typically D&C has n/b with b>1."

12.4 Algorithm Simulation on Given Inputs

• Merge Sort Trace: Given array, show recursive division and merge steps with arrays at each level.

• Quick Sort Trace: Given array, show pivot selection, partition steps, subarrays.

• MST Trace: For Kruskal: sort edges, add in order if no cycle (use Union-Find). For Prim: start vertex, grow tree by min edge to outside vertex (use PQ).

• Huffman Coding: Given probabilities/frequencies, show min-heap merges, tree construction, code assignment.

Final Note: This compilation covers all high-frequency topics from past RGPV papers (2022-2025). Focus on problem-solving with given numerical examples (knapsack, MST, Huffman, TSP, DP tables). Practice recurrence solving (Master Theorem, substitution) and algorithm simulation. Understand proofs (greedy properties, NP-completeness reductions). For data structures (B-tree, AVL, binomial heap), know insertion/deletion steps with examples.