Design& Analysis of Algorithms (CY-502) - Unit 4 Short Notes

UNIT 4: DESIGN & ANALYSIS OF ALGORITHMS

I. FUNDAMENTALS OF ALGORITHM ANALYSIS

A. Time Complexity

• Definition: Measure of the amount of time an algorithm takes to run as a function of the length of the input. It is expressed using asymptotic notations (Big O, etc.).

• Cases:

  • Best-case: Minimum time required (e.g., search for first element in a list).

  • Average-case: Expected time over all possible inputs (requires probability distribution).

  • Worst-case: Maximum time required (most commonly analyzed).

• Key Exam Focus: Proving average-case complexity (e.g., Quick Sort, Binary Search).

[!TIP] Exam Tip: For average-case analysis of Quick Sort, assume all permutations of input are equally likely. The pivot splits the array into sizes i-1 and n-i. The recurrence is C(n) = (n-1) + (1/n) * Σ C(i). Solve to get C(n) = O(n log n).

B. Asymptotic Notations

Mathematical tools to describe the limiting behavior of a function.

[!TIP] Common Pitfall: f(n) = O(g(n)) does not imply g(n) = O(f(n)). Θ denotes equality up to constant factors.

C. Space Complexity

• Definition: Amount of memory space required by an algorithm as a function of input size.

• Types:

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

  • Total Space: Input space + Auxiliary space.

• Analysis: Count memory for variables, data structures (arrays, recursion stack). Recursive algorithms often have O(recursion depth) auxiliary space.

[!TIP] Exam Short Note: "Space Complexity refers to the maximum amount of memory an algorithm requires during its execution. It includes the space for input data and any additional auxiliary space. For example, Merge Sort uses O(n) auxiliary space, while Heap Sort uses O(1)."

II. DIVIDE AND CONQUER PARADIGM

A. General Method & Recurrence Relations

1. Divide: Break the problem into smaller subproblems.

2. Conquer: Solve subproblems recursively.

3. Combine: Merge subproblem solutions to form the final solution.

• Recurrence Relation: T(n) = a*T(n/b) + f(n), where:

  • a = number of subproblems

  • n/b = size of each subproblem

  • f(n) = cost of divide/combine steps.

Methods to Solve Recurrences:

1. Substitution Method: Guess a bound, prove by induction.

2. Recursion Tree Method: Visualize costs per level, sum them.

3. Master Theorem: For T(n) = aT(n/b) + f(n):

   • If f(n) = O(n^{log_b a - ε}) → T(n) = Θ(n^{log_b a})

   • If f(n) = Θ(n^{log_b a}) → T(n) = Θ(n^{log_b a} log n)

   • If f(n) = Ω(n^{log_b a + ε}) and a*f(n/b) ≤ c*f(n) → T(n) = Θ(f(n))

B. Sorting Algorithms

Merge Sort

• Algorithm: Recursively split array into halves, sort each half, merge two sorted halves.

• Time Complexity: T(n) = 2T(n/2) + Θ(n) → Θ(n log n) in all cases (best, average, worst).

• Space Complexity: Θ(n) auxiliary space for merging.

Quick Sort

• Algorithm: Choose a pivot, partition array around pivot (elements < pivot left, > pivot right), recursively sort partitions.

  • Lomuto Partition: Pivot is last element, single pointer i tracks boundary.

  • Hoare Partition: Pivot is first element, two pointers from ends moving inward.

• Complexity Analysis:

  • Best/Average Case: Pivot splits array evenly → T(n) = 2T(n/2) + Θ(n) → Θ(n log n).

  • Worst Case: Pivot is smallest/largest element (e.g., already sorted array with naive pivot) → T(n) = T(n-1) + Θ(n) → Θ(n²).

• Proof of Average-Case O(n log n):

  Assume all input permutations equally likely. The probability that a particular pivot i (1≤i≤n) is chosen is 1/n. The expected number of comparisons C(n) satisfies:

$$C(n) = (n-1) + \frac{1}{n} \sum_{i=1}^{n} [C(i-1) + C(n-i)]$$

Solving this recurrence yields `C(n) ≈ 1.386 n log n` → `O(n log n)`.

[!TIP] Exam Focus: You may be asked to sort a given list using Quick Sort (show partition steps). Always state the partition scheme used (Lomuto/Hoare).

C. Matrix Multiplication

Strassen's Algorithm

• Idea: For two 2x2 block matrices A and B, compute 7 products (M1 to M7) instead of 8, then combine.

  
  M1 = (A11 + A22) * (B11 + B22)
  
  M2 = (A21 + A22) * B11
  
  M3 = A11 * (B12 - B22)
  
  M4 = A22 * (B21 - B11)
  
  M5 = (A11 + A12) * B22
  
  M6 = (A21 - A11) * (B11 + B12)
  
  M7 = (A12 - A22) * (B21 + B22)
  
  

  Then:

  
  C11 = M1 + M4 - M5 + M7
  
  C12 = M3 + M5
  
  C21 = M2 + M4
  
  C22 = M1 - M2 + M3 + M6
  
  

• Recurrence Relation: T(n) = 7T(n/2) + Θ(n²) (7 subproblems of size n/2, plus O(n²) for additions).

• Solution (using Master Theorem): a=7, b=2, log_b a = log₂7 ≈ 2.807. Since f(n)=Θ(n²) = O(n^{log₂7 - ε}) for ε≈0.807, Case 1 applies.

$$\boxed{T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})}$$

This is better than the naive `Θ(n³)` for large `n`.

[!TIP] Exam Focus: "Write and solve recurrence for Strassen's" is a direct, repeated question. Memorize the 7 M products and the recurrence solution.

III. GREEDY ALGORITHM PARADIGM

A. General Method & Correctness

• Greedy Choice Property: A local optimum choice at each step leads to a global optimum.

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

• Correctness Proof: Usually by exchange argument or greedy stays ahead method.

  • Exchange Argument: Show any solution differing from greedy can be transformed into greedy without worsening cost.

  • Greedy Stays Ahead: Show that after each step, the greedy solution is at least as good as any other partial solution.

[!TIP] Exam Question: "How do you prove correctness of Greedy algorithm?" → Answer: "By demonstrating the Greedy Choice Property and Optimal Substructure. Common proof techniques are the Exchange Argument and Greedy Stays Ahead."

B. Standard Greedy Problems

1. Fractional Knapsack Problem

• Problem: Maximize total profit with weight capacity W. Items can be taken fractionally.

• Algorithm:

  1. Calculate profit/weight ratio p_i / w_i for each item.

  2. Sort items in decreasing order of ratio.

  3. Starting from highest ratio, take as much as possible (full item or fraction until capacity W is full).

• Complexity: O(n log n) due to sorting.

• Example (Dec 2024): n=4, m=15, p=(10,10,12,18), w=(2,4,6,9)

  • Ratios: 5, 2.5, 2, 2

  • Sorted: Item1 (5), Item2 (2.5), Item3 (2), Item4 (2)

  • Take: Full Item1 (w=2, p=10, rem=13), Full Item2 (w=4, p=10, rem=9), Full Item3 (w=6, p=12, rem=3), Fraction of Item4 (3/9=1/3, p=6).

  • Total Profit = 10+10+12+6 = 38.

2. Job Sequencing with Deadlines

• Problem: Schedule jobs (each with profit p_i and deadline d_i (1 slot per job)) to maximize total profit. Jobs must finish by deadline.

• Algorithm:

  1. Sort all jobs in decreasing order of profit.

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

  3. For each job in sorted order, place it in the latest available slot that is ≤ its deadline.

  4. If no such slot exists, discard the job.

• Complexity: O(n²) (or O(n log n) with Disjoint Set Union).

• Example (Nov 2023): n=4, p=(100,10,15,27), d=(2,1,2,1)

  • Sorted by profit: J1(100,d2), J4(27,d1), J3(15,d2), J2(10,d1)

  • Place J1 in slot 2. Place J4 in slot 1. J3 & J2 have no slot.

  • Optimal Sequence: J4 (slot1), J1 (slot2). Total Profit = 127.

3. Huffman Coding

• Problem: Generate optimal prefix codes (variable-length codes) for characters based on frequencies to minimize total bits (expected code length).

• Algorithm (using Min-Heap):

  1. Create a min-heap node for each character with its frequency.

  2. While heap size > 1:

     • Extract two nodes with smallest frequency (x, y).

     • Create a new internal node with frequency x.freq + y.freq.

     • Make x and y children of this node (assign 0 to left, 1 to right, or vice versa).

     • Insert the new node into the heap.

  3. The remaining node is the root of the Huffman Tree.

  4. Traverse the tree to generate codes (path from root to leaf).

• Complexity: O(n log n) using heap.

• Example: Frequencies: a:5, b:9, c:12, d:13, e:16, f:45. Build tree bottom-up.

4. Optimal Merge Pattern

• Problem: Given n sorted files of lengths L1, L2, ..., Ln, find the optimal way to merge them into one file minimizing total merge cost (cost = sum of lengths of files being merged).

• Relation to Huffman: Exactly the same as building a Huffman tree where file lengths are frequencies. The total cost equals the weighted path length of the Huffman tree.

• Algorithm: Use a min-heap. Repeatedly merge the two smallest files until one remains.

• Complexity: O(n log n).

[!TIP] Exam Focus: Job Sequencing and Fractional Knapsack appear in all three past papers with numerical data. Practice both algorithms step-by-step with given numbers.

IV. DYNAMIC PROGRAMMING PARADIGM

A. General Method vs. Divide & Conquer

• Key Idea: Break problem into overlapping subproblems, solve each once, store result, use stored result for larger problems.

B. Standard DP Problems

1. 0/1 Knapsack Problem

• Problem: Given n items (profit p_i, weight w_i), capacity W. Choose items (0 or 1 of each) to maximize total profit without exceeding W.

• DP Table: dp[i][w] = maximum profit using first i items with capacity w.

• Recurrence:

$$ dp[i][w] = \begin{cases} 0 & \text{if } i=0 \text{ or } w=0 \\ dp[i-1][w] & \text{if } w_i > w \\ \max(p_i + dp[i-1][w-w_i], dp[i-1][w]) & \text{otherwise} \end{cases} $$

• Algorithm (Tabulation):

  
  for i=0 to n:
  
      for w=0 to W:
  
          if i==0 or w==0: dp[i][w] = 0
  
          else if w_i > w: dp[i][w] = dp[i-1][w]
  
          else: dp[i][w] = max(p_i + dp[i-1][w-w_i], dp[i-1][w])
  
  return dp[n][W]
  
  

• Complexity: O(nW) time and space.

• Example (Nov 2022): n=3, W=6, p=(1,2,5), w=(2,3,4)

  • Build table:

    | i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | | 2 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | | 3 | 0 | 0 | 1 | 2 | 5 | 5 | 7 |

  • dp[3][6] = 7 (Items 1 & 3: profit 1+5=6? Wait, check: Actually items 2 & 3: w=3+4=7>6 invalid. Items 1 & 2: w=2+3=5, p=1+2=3. Item 3 alone: p=5. So max is 5? Let's recalc properly: For i=3, w=4: max(p3+dp[2][0]=5+0=5, dp[2][4]=2) → 5. w=5: max(p3+dp[2][1]=5+0=5, dp[2][5]=3) → 5. w=6: max(p3+dp[2][2]=5+1=6, dp[2][6]=3) → 6. So dp[3][6]=6. But expected answer from paper? Possibly different data. For given data, max profit is 6 (items 1 & 3). But paper says "Solve... N=3, m=6 profits (1,2,5) weights (2,3,4)". That yields 6. But let's trust the recurrence. In exam, build table carefully.)

  • Correct Table:

    w: 0 1 2 3 4 5 6

    i=1: 0 0 1 1 1 1 1

    i=2: 0 0 1 2 2 3 3

    i=3: 0 0 1 2 5 5 6

  • Answer: Maximum Profit = 6.

2. Multistage Graph Problem

• Definition: A directed acyclic graph (DAG) where vertices are partitioned into k stages. Edges only go from stage i to stage i+1. Find the shortest path from source (stage 1) to sink (stage k).

• Application: Shortest path in acyclic graphs, project scheduling.

• DP Approach (Backward/Forward):

  • Let cost(i, v) = shortest distance from vertex v in stage i to sink.

  • Recurrence (Backward): cost(i, v) = min{ cost(i+1, w) + length(v,w) } for all w adjacent to v.

  • Start from stage k-1 down to stage 1.

• Algorithm (Backward):

  
  for each vertex v in stage k: cost(k, v) = 0
  
  for i = k-1 downto 1:
  
      for each vertex v in stage i:
  
          cost(i, v) = min_{w in Adj(v)} [ length(v,w) + cost(i+1, w) ]
  
  return cost(1, source)
  
  

• Complexity: O(|V| + |E|) since each edge is examined once.

• Example: Given a multistage graph with stages, compute cost(1, s).

3. All-Pairs Shortest Paths (Floyd-Warshall)

• Problem: Find shortest distances between every pair of vertices in a weighted graph (may have negative edges, no negative cycles).

• Algorithm (DP on adjacency matrix):

  Let dist[i][j] be shortest path from i to j using intermediate vertices from set {1..k}.

  
  Initialize dist[i][j] = weight(i,j) if edge exists, else ∞, dist[i][i]=0.
  
  for k = 1 to n:
  
      for i = 1 to n:
  
          for j = 1 to n:
  
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  
  

• Complexity: Θ(n³).

• Negative Cycle Detection: After algorithm, if any dist[i][i] < 0, a negative cycle exists.

• Example (Nov 2023): Given a graph with adjacency matrix, apply Floyd-Warshall step-by-step for k=1,2,3.

[!TIP] Exam Focus: Multistage Graph and Floyd-Warshall are very common. Be prepared to write the algorithm and solve a small graph (3-4 vertices) manually.

V. BACKTRACKING PARADIGM

A. General Method & State Space Tree

• Idea: Systematic exploration of all potential solutions (state space) by constructing candidates incrementally and abandoning a candidate ("backtrack") as soon as it is determined that it cannot possibly lead to a valid solution.

• State Space Tree: Tree where each node represents a partial solution. Root is empty, leaves are complete solutions or dead ends.

• Pruning: Avoid exploring subtrees that cannot yield a solution (using constraint checks).

B. Standard Backtracking Problems

1. N-Queens Problem

• Problem: Place N queens on an N×N chessboard so that no two queens attack each other (no two in same row, column, or diagonal).

• Algorithm (Row-wise placement):

  
  placeQueens(row):
  
      if row > N: print solution; return true
  
      for col=1 to N:
  
          if isSafe(row, col):
  
              place queen at (row, col)
  
              if placeQueens(row+1): return true
  
              remove queen from (row, col)  // backtrack
  
      return false
  
  

  isSafe(row, col) checks column and both diagonals for previous rows.

• State Space Tree for 4-Queens:

  • Root: empty board.

  • Level 1: Try placing queen in row1 at col1, col2, col3, col4 (4 branches).

  • For each, level 2: try safe columns in row2, etc.

  • Solutions: [2,4,1,3] and [3,1,4,2] (where array index=row, value=col).

  • Tree branches are pruned when isSafe fails.

  • Sketch: Draw tree with nodes labeled (row,col) and show dead ends.

2. Graph Coloring (m-coloring)

• Problem: Color vertices of a graph with at most m colors such that no two adjacent vertices have the same color.

• Algorithm:

  
  graphColor(k):
  
      if k > n: return true  // all colored
  
      for c=1 to m:
  
          if isSafe(k, c):  // check neighbors of vertex k
  
              color[k] = c
  
              if graphColor(k+1): return true
  
              color[k] = 0  // backtrack
  
      return false
  
  

• Example (Nov 2022): Given a graph (e.g., triangle or square), find if 3-colorable.

3. Hamiltonian Cycle

• Problem: Find a cycle in an undirected graph that visits each vertex exactly once and returns to start.

• Algorithm (Path-based):

  
  hamiltonian(k):
  
      if k == n:
  
          if edge exists between last and first vertex: print solution; return true
  
          else: return false
  
      for each vertex v (not in path and adjacent to path[k-1]):
  
          path[k] = v
  
          if hamiltonian(k+1): return true
  
          path[k] = 0  // backtrack
  
      return false
  
  

• Example: For a given graph (e.g., pentagon), show the path construction.

[!TIP] Exam Focus: "Sketch state space tree for 4-queens" and "Solve graph coloring for given graph" are repeated. Practice drawing trees and applying isSafe checks.

VI. BRANCH AND BOUND PARADIGM

A. General Method

• Idea: Systematic exploration of candidate solutions by partitioning the solution space and computing bounds to discard partitions that cannot contain an optimal solution.

• Key Concepts:

  • Live Node: Node whose children have not yet been generated.

  • E-node (Expanding Node): Live node that is being expanded (its children are being generated).

  • Dead Node: Node that cannot be further expanded or whose subtree does not contain a solution.

  • Bounding Function: Computes a lower bound (for minimization) or upper bound (for maximization) on the cost of any solution in the subtree.

• Search Strategies:

  • FIFO (Queue): Explore nodes in order they are generated.

  • LIFO (Stack): Depth-first (like backtracking but with bounds).

  • Priority Queue (Best-First): Expand node with best bound (most promising).

B. Application: Traveling Salesperson Problem (TSP)

• Problem: Find the shortest possible tour that visits each city exactly once and returns to the start city.

• Branch and Bound Method (Reduction Method):

  1. Cost Matrix Reduction:

     • For each row, subtract the row minimum from every element in that row.

     • For each column of the reduced matrix, subtract the column minimum.

     • The sum of all subtracted values is a lower bound for the tour cost.

  2. State Space Tree: Each node represents a partial path (e.g., 1 → 2 → 3). Level k corresponds to having fixed the first k cities.

  3. Bounding Function for a Node (path 1→i₁→i₂→...→iₖ):

     • cost_so_far = sum of edge costs in the path.

     • lower_bound_remaining = reduce the cost matrix by:

       • Setting row of iₖ and column of iₖ to ∞ (to avoid revisiting).

       • Setting cost(iₖ, 1) to ∞ (to prevent returning to start prematurely).

       • Perform row/column reduction again on the modified matrix, sum the reductions.

     • Total bound = cost_so_far + lower_bound_remaining.

  4. Search: Use a priority queue ordered by bound. Expand the node with smallest bound. If its bound ≥ best solution found so far, prune it.

• Example: Given a 4x4 cost matrix, show reduction for root node, then for child nodes.

[!TIP] Exam Focus: "Explain method of reduction to solve TSP using branch and bound" is a direct, repeated question. Memorize the reduction steps and bounding function calculation.

VII. GRAPH ALGORITHMS

A. Minimum Spanning Tree (MST) - Greedy

• Definition: A spanning tree of a connected, undirected graph with minimum total edge weight.

Prim's Algorithm

• Idea: Grow the MST one vertex at a time from a starting vertex. At each step, add the minimum weight edge connecting a vertex in the MST to a vertex outside.

• Algorithm (using adjacency list & min-heap):

  
  Initialize key[v] = ∞ for all v, key[start]=0, parent[v]=NULL
  
  Q = min-heap of all vertices keyed by key[]
  
  while Q not empty:
  
      u = extract-min(Q)  // vertex with smallest key
  
      for each neighbor v of u in Q:
  
          if weight(u,v) < key[v]:
  
              key[v] = weight(u,v)
  
              parent[v] = u
  
  MST edges = {(parent[v], v) for v ≠ start}
  
  

• Time Complexity:

  • With simple array (linear search for min): O(V²).

  • With binary heap: O(E log V).

  • With Fibonacci heap: O(E + V log V).

• Example (Dec 2024): Given a graph, show step-by-step MST construction.

Kruskal's Algorithm

• Idea: Sort all edges by weight, then add edges in increasing order if they do not form a cycle.

• Algorithm:

  
  Sort all edges in non-decreasing order of weight
  
  Initialize a disjoint-set (Union-Find) for vertices
  
  MST = empty
  
  for each edge (u,v) in sorted order:
  
      if find(u) ≠ find(v):  // no cycle
  
          add edge (u,v) to MST
  
          union(u,v)
  
  

• Time Complexity: Dominated by sorting: O(E log E) = O(E log V) (since E ≤ V²). Union-Find operations nearly O(α(V)) (inverse Ackermann).

• Cycle Detection: Union-Find data structure efficiently checks if two vertices are already connected.

[!TIP] Exam Focus: "Construct MST using Prim's and Kruskal's" is common. Know both algorithms and their complexities. For Kruskal's, be ready to sort edges and apply Union-Find.

B. Other Graph Representations

• Adjacency Matrix: V×V matrix. matrix[i][j] = weight if edge exists, else ∞/0.

  • Space: Θ(V²).

  • Good for dense graphs, quick edge lookup O(1).

• Adjacency List: Array of lists. list[u] contains all neighbors of u.

  • Space: Θ(V + E).

  • Good for sparse graphs, iterating neighbors O(degree(u)).

VIII. ADVANCED CONCEPTS & COMPLEXITY THEORY

A. NP-Completeness & NP-Hard

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

• NP: Problems for which a solution can be verified in polynomial time (or solvable by nondeterministic TM in poly-time). P ⊆ NP.

• NP-Hard: Problems at least as hard as the hardest problems in NP. Any NP problem can be reduced to an NP-Hard problem in polynomial time. Not necessarily in NP (may not have polynomial-time verifiable solutions).

• NP-Complete: Problems that are both NP-Hard and in NP. If any NP-Complete has a poly-time algorithm, then P = NP.

• Reduction: To prove problem A is NP-Complete:

  1. Show A ∈ NP (solution verifiable in poly-time).

  2. Take a known NP-Complete problem B and reduce B to A in polynomial time (B ≤p A). If B is hard, then A is at least as hard.

• Comparison (Nov 2022, Nov 2023):

  | Feature | NP-Hard | NP-Complete | | :--- | :--- | :--- | | Definition | At least as hard as NP problems | NP-Hard and in NP | | Membership | Not necessarily in NP | Must be in NP | | Example | Halting Problem, TSP (optimization) | SAT, 0/1 Knapsack (decision), Graph Coloring | | Implication | If P=NP, still may not be poly-time solvable | If P=NP, then poly-time solvable |

[!TIP] Exam Focus: "Compare NP-hard and NP-completeness" is repeated. Emphasize: NP-Complete ⊆ NP, NP-Hard ⊈ NP necessarily. Optimization versions are NP-Hard, decision versions are often NP-Complete.

B. Horner's Algorithm

• Problem: Evaluate polynomial P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ at a given x.

• Naive: O(n²) (compute each xᶦ separately).

• Horner's Rule: Rewrite as P(x) = a₀ + x(a₁ + x(a₂ + ... + x(aₙ) ... ).

• Algorithm:

  
  result = aₙ
  
  for i = n-1 downto 0:
  
      result = result * x + aᵢ
  
  return result
  
  

• Complexity: O(n) time, O(1) space.

• Example: P(x)=2x³+3x²+4x+5 at x=2:

  result = 4 (a₃)

  i=2: result = 4*2 + 3 = 11

  i=1: result = 11*2 + 4 = 26

  i=0: result = 26*2 + 5 = 57

IX. MISCELLANEOUS & EMERGING TOPICS

A. Parallel Algorithms

• PRAM Model: Parallel Random Access Machine. Assumes unlimited processors, shared memory, unit-time memory access.

• Key Metrics:

  • Work: Total operations across all processors (T₁).

  • Time: Time with p processors (Tₚ).

  • Speedup: Sₚ = T₁ / Tₚ.

  • Efficiency: Eₚ = Sₚ / p = T₁ / (p Tₚ).

  • Scalability: How well speedup increases with p.

• Examples: Parallel Merge Sort, Parallel Prefix Sum.

• Short Note: "Parallel algorithms exploit multiple processors to solve problems faster. They are designed for models like PRAM. Key challenges include load balancing, synchronization, and communication overhead. Speedup is limited by Amdahl's Law."

B. Data Stream Algorithms

• Context: Process massive data streams (e.g., network packets, web logs) with limited memory (cannot store entire stream). Must process in one pass.

• Characteristics: High arrival rate, continuous, unbounded.

• Problems & Algorithms:

  • Count-Distinct: Estimate number of distinct elements (e.g., Flajolet-Martin algorithm).

  • Heavy Hitters (Frequent Items): Find items occurring more than a threshold (e.g., Misra-Gries algorithm, Count-Min Sketch).

  • Sampling: Maintain a random sample of the stream (e.g., reservoir sampling).

• Example: "In streaming services, data stream algorithms track trending videos (heavy hitters) or estimate unique viewers (count-distinct) using sketches that fit in small memory."

C. B-Trees

• Structure: Balanced search tree where each node can have multiple keys (order m B-tree: each node has at most m-1 keys and m children). All leaves at same depth.

• Properties:

  • Root: at least 2 children (unless only one node).

  • Internal nodes (except root): at least ⌈m/2⌉ children.

  • Leaves: all at same depth, contain actual data pointers.

• Creation (Insertion):

  1. Search for leaf where key should go.

  2. Insert key in sorted order within leaf.

  3. If leaf overflows (> m-1 keys), split:

     • Median key moves up to parent.

     • Two halves become separate nodes.

     • Propagate split upward if parent overflows.

• Advantages for Disk-Based Systems:

  • High fan-out reduces tree height → fewer disk accesses (I/O).

  • Balanced ensures O(log_m n) search/insert/delete.

  • Nodes align with disk block sizes.

• Example: Insert sequence into B-tree of order 5.

D. Lower Bound Theory

• Goal: Prove that any algorithm for a problem must take at least Ω(f(n)) time in the worst case.

• Techniques:

  1. Decision Tree Model: For comparison-based problems (sorting, searching), any algorithm can be represented as a binary decision tree where each comparison is a node. The height of the tree is the worst-case number of comparisons.

     • Sorting: n! permutations → decision tree has at least n! leaves. Height h ≥ log₂(n!) = Θ(n log n) → Ω(n log n) lower bound for comparison sorts.

     • Searching in sorted array: Binary search decision tree has n+1 outcomes → height ≥ log₂(n+1) → Ω(log n).

  2. Adversary Argument: Construct an input that forces the algorithm to perform many steps, regardless of its choices.

• Application to Algebraic Problems: For problems like matrix multiplication or polynomial evaluation, lower bounds can be derived from the number of input elements and the number of possible outputs, or using decision trees for comparisons.

[!TIP] Exam Focus: "How lower bound theory is used to solve algebraic problems?" → Explain decision tree method for comparison-based problems (sorting, searching) and adversary method for others. Mention Ω(n log n) for sorting.

X. QUICK REFERENCE TABLE: COMPLEXITIES

\boxed{\text{Remember: For exams, always state assumptions (e.g., comparison model for sorting lower bounds) and show working for numerical problems.}}