Analysis & Design of Algorithms (AL-402) - Unit 3 Short Notes

UNIT 3: Advanced Algorithm Design and Analysis

I. Algorithm Analysis Fundamentals

Time Complexity Notations

• Big O (O): Upper bound. $$\displaystyle T(n) = O(f(n)) $$ if $$\displaystyle \exists c > 0, n_0 $$ such that $0 \le T(n) \le c f(n)$ for all $$\displaystyle n \ge n_0 $$.

• Omega (Ω): Lower bound. $$\displaystyle T(n) = \Omega(f(n)) $$ if $$\displaystyle \exists c > 0, n_0 $$ such that $0 \le c f(n) \le T(n)$ for all $$\displaystyle n \ge n_0 $$.

• Theta (Θ): Tight bound. $$\displaystyle T(n) = \Theta(f(n)) $$ if $$\displaystyle T(n) = O(f(n)) $$ and $$\displaystyle T(n) = \Omega(f(n)) $$.

[!TIP] For polynomial $$\displaystyle T(n) = a_k n^k + ... + a_0 $$, $$\displaystyle \Theta(n^k) $$.

Recurrence Relations

Solving Techniques:

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

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

3. Master Theorem: For $$\displaystyle T(n) = aT(n/b) + f(n) $$, $$\displaystyle a \ge 1, b > 1 $$.

   • Case 1: $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) \Rightarrow T(n) = \Theta(n^{\log_b a}) $$

   • Case 2: $$\displaystyle f(n) = \Theta(n^{\log_b a}) \Rightarrow T(n) = \Theta(n^{\log_b a} \log n) $$

   • Case 3: $$\displaystyle f(n) = \Omega(n^{\log_b a + \epsilon}) $$ and regularity condition $$\displaystyle \Rightarrow T(n) = \Theta(f(n)) $$

Application to Divide-and-Conquer:

• Merge Sort: $$\displaystyle T(n) = 2T(n/2) + \Theta(n) \Rightarrow \Theta(n \log n) $$ (Master Theorem Case 2).

• Quick Sort average: $$\displaystyle T(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + \Theta(n) \Rightarrow \Theta(n \log n) $$.

Strassen's Matrix Multiplication

Algorithm: For two $n \times n$ matrices (assume $n$ power of 2):

1. Divide each matrix into 4 submatrices of size $n/2$.

2. Compute 7 products recursively:

   $$\displaystyle M_1 = (A_{11}+A_{22})(B_{11}+B_{22}) $$

   $$\displaystyle M_2 = (A_{21}+A_{22})B_{11} $$

   $$\displaystyle M_3 = A_{11}(B_{12}-B_{22}) $$

   $$\displaystyle M_4 = A_{22}(B_{21}-B_{11}) $$

   $$\displaystyle M_5 = (A_{11}+A_{12})B_{22} $$

   $$\displaystyle M_6 = (A_{21}-A_{11})(B_{11}+B_{12}) $$

   $$\displaystyle M_7 = (A_{12}-A_{22})(B_{21}+B_{22}) $$

3. Combine to get result submatrices:

   $$\displaystyle C_{11} = M_1 + M_4 - M_5 + M_7 $$

   $$\displaystyle C_{12} = M_3 + M_5 $$

   $$\displaystyle C_{21} = M_2 + M_4 $$

   $$\displaystyle C_{22} = M_1 - M_2 + M_3 + M_6 $$

Recurrence: $$\displaystyle T(n) = 7T(n/2) + \Theta(n^2) $$. Complexity: By Master Theorem, $$\displaystyle a=7, b=2, \log_b a = \log_2 7 \approx 2.807 $$, $$\displaystyle f(n)=\Theta(n^2) $$. Since $$\displaystyle n^2 = O(n^{\log_2 7 - \epsilon}) $$ for $\epsilon \approx 0.807$, Case 1 applies:

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

Quick Sort

Average-Case Complexity Proof (Sketch):

• Recurrence for average case: $$\displaystyle T(n) = \frac{1}{n} \sum_{k=0}^{n-1} [T(k) + T(n-k-1)] + \Theta(n) $$.

• Assume $T(k) \le c k \log k$ for $$\displaystyle k < n $$.

• Substitute and simplify using integral approximation:

$$ T(n) \le \frac{2c}{n} \sum_{k=0}^{n-1} k \log k + \Theta(n) \le c n \log n - \Theta(n) + \Theta(n) $$

For large $n$, $T(n) \le c n \log n$.

$$ \boxed{\text{Average-case: } \Theta(n \log n)} $$

[!TIP] Worst-case (sorted input) recurrence: $$\displaystyle T(n) = T(n-1) + \Theta(n) \Rightarrow \Theta(n^2) $$.

Merge Sort

Algorithm:

MERGE-SORT(A, l, r):

  if l < r:

    m = ⌊(l+r)/2⌋

    MERGE-SORT(A, l, m)

    MERGE-SORT(A, m+1, r)

    MERGE(A, l, m, r)

Complexity: Recurrence $$\displaystyle T(n) = 2T(n/2) + \Theta(n) $$. Master Theorem Case 2 gives $\boxed{\Theta(n \log n)}$ in all cases.

II. Greedy Algorithms

Core Properties

1. Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.

2. Optimal Substructure: Optimal solution to problem contains optimal solutions to subproblems.

[!TIP] To prove correctness, show both properties hold. Counterexample if greedy fails (e.g., 0/1 Knapsack).

Classic Greedy Problems

1. Job Sequencing with Deadlines

• Goal: Maximize profit with unit-time jobs, each with deadline $$\displaystyle d_i $$ and profit $$\displaystyle p_i $$. Schedule at most one job per time slot before its deadline.

• Greedy Strategy: Sort jobs by decreasing profit. For each job, schedule it in the latest available slot before its deadline.

• Example (June 2024):

  Jobs: $$\displaystyle (P_1,P_2,P_3,P_4)=(100,10,15,27) $$, $$\displaystyle (d_1,d_2,d_3,d_4)=(2,1,2,1) $$

  Sorted by profit: J1(100,2), J4(27,1), J3(15,2), J2(10,1)

  Timeline: slot 2 → J1, slot 1 → J4. J3 and J2 rejected.

  Optimal profit = 127, sequence: J1, J4.

2. Fractional Knapsack

• Goal: Maximize total value with capacity $W$, items with value $$\displaystyle v_i $$, weight $$\displaystyle w_i $$, can take fractions.

• Greedy Strategy: Sort by value/weight ratio descending. Take as much as possible of each item until capacity full.

• Example (Dec 2024):

  $$\displaystyle N=5, M=10 $$, $$\displaystyle (p)=(10,15,10,12,8) $$, $$\displaystyle (w)=(3,3,2,5,1) $$

  Ratios: $$\displaystyle 10/3≈3.33, 15/3=5, 10/2=5, 12/5=2.4, 8/1=8 $$

  Sorted: J5(8,1), J2(15,3), J3(10,2), J1(10,3), J4(12,5)

  Take: J5 full (w=1, v=8), J2 full (w=3, v=15), J3 full (w=2, v=10), J1 partial: need 4 more capacity? Wait: total taken=1+3+2=6, remaining 4. J1 weight 3 → take full (v=10), total weight=9, remaining 1. J4 weight 5 → take 1/5 (v=12/5=2.4).

  Total value = 8+15+10+10+2.4 = 45.4.

3. Huffman Coding

• Goal: Construct optimal prefix-free binary codes for symbols with frequencies $$\displaystyle f_i $$.

• Greedy Strategy: Repeatedly merge two least frequent nodes into a new node with combined frequency.

• Algorithm:

  1. Create min-heap of nodes (symbol, freq).

  2. While heap size > 1:

     • Extract two min nodes $x,y$.

     • Create new node with freq = $x.freq + y.freq$, children $x,y$.

     • Insert new node.

  3. Assign 0/1 to left/right edges from root.

• Complexity: $O(n \log n)$ with heap.

4. Optimal Merge Pattern

• Goal: Merge $n$ sorted files of lengths $$\displaystyle l_1,...,l_n $$ with minimum total comparisons (cost = sum of lengths merged).

• Greedy Strategy: Always merge two smallest files first (same as Huffman).

• Example: Files: 10, 20, 30, 40.

  Step1: merge 10+20=30 (cost=30) → files: 30,30,40.

  Step2: merge 30+30=60 (cost=60) → files: 60,40.

  Step3: merge 60+40=100 (cost=100).

  Total cost = 30+60+100 = 190.

5. Minimum Spanning Tree (Kruskal's)

• Goal: Find spanning tree with minimum total edge weight.

• Greedy Strategy: Sort edges by weight ascending. Add edge if it doesn’t form cycle (use Union-Find).

• Algorithm:

  1. Sort edges $E$ by weight.

  2. Initialize each vertex as separate set (Union-Find).

  3. For each edge $(u,v)$ in sorted order:

     • If Find($u$) ≠ Find($v$): add edge, Union($u,v$).

• Complexity: $O(E \log E)$ (dominated by sorting).

6. Single Source Shortest Path (Dijkstra's)

• Goal: Shortest paths from source $s$ to all vertices in graph with non-negative weights.

• Greedy Strategy: Repeatedly select vertex with smallest tentative distance.

• Algorithm:

  1. Initialize dist[$s$]=0, others=∞. Set $S$ = empty.

  2. While not all vertices in $S$:

     • Choose $u \notin S$ with min dist[$u$].

     • Add $u$ to $S$.

     • For each neighbor $v$ of $u$: if dist[$v$] > dist[$u$] + $w(u,v)$, update dist[$v$].

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

[!TIP] Fails with negative weights (use Bellman-Ford).

III. Dynamic Programming

Core Principles

1. Overlapping Subproblems: Problem can be broken into subproblems reused multiple times.

2. Optimal Substructure: Optimal solution composed of optimal solutions to subproblems.

[!TIP] DP = recursion + memoization (top-down) or tabulation (bottom-up). Avoid recomputation.

DP Applications

1. Reliability Design Problem

• Goal: Maximize system reliability $R$ subject to cost constraint $$\displaystyle C_{\max} $$. System has $n$ stages, each stage $i$ can choose device type $j$ with reliability $$\displaystyle r_{ij} $$ and cost $$\displaystyle c_{ij} $$.

• DP Formulation: Let $R[i][c]$ = max reliability for first $i$ stages with cost exactly $c$.

$$ R[i][c] = \max_{j: c_{ij} \le c} \{ r_{ij} \times R[i-1][c - c_{ij}] \} $$

• Algorithm: Bottom-up for $$\displaystyle i=1..n $$, $$\displaystyle c=0..C_{\max} $$.

• Example (Dec 2024): 3 stages, costs (30,15,20), reliabilities (0.9,0.8,0.5), $$\displaystyle C_{\max}=105 $$. Compute $R[3][c]$ for $c \le 105$, take max.

2. Multistage Graph

• Goal: Find shortest path from start $s$ to terminal $t$ in directed acyclic graph with stages.

• DP Formulation: Let $C[i][v]$ = min cost from vertex $v$ in stage $i$ to $t$.

$$ C[i][v] = \min_{w \in \text{Adj}(v)} \{ c(v,w) + C[i+1][w] \} $$

Base: $$\displaystyle C[\text{last stage}][t] = 0 $$.

• Algorithm: Process stages backward from terminal.

• Complexity: $O(|V|+|E|)$ if adjacency lists used.

3. 0/1 Knapsack Problem

• Goal: Maximize total value $$\displaystyle \sum p_i x_i $$ with $$\displaystyle \sum w_i x_i \le M $$, $$\displaystyle x_i \in \{0,1\} $$.

• DP Table: $V[i][w]$ = max value using first $i$ items with capacity $w$.

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

• Algorithm: Fill $n \times M$ table. Complexity $O(nM)$.

• Example (June 2024): $$\displaystyle n=7, M=15 $$, $$\displaystyle p=(10,5,15,7,6,18,3) $$, $$\displaystyle w=(2,3,5,7,1,4,1) $$. Compute table, trace back for selected items.

4. All-Pairs Shortest Path (Floyd-Warshall)

• Goal: Shortest paths between every pair in weighted graph (no negative cycles).

• DP Formulation: Let $$\displaystyle D^k[i][j] $$ = shortest path from $i$ to $j$ using intermediate vertices from $\{1..k\}$.

$$ D^k[i][j] = \min(D^{k-1}[i][j],\ D^{k-1}[i][k] + D^{k-1}[k][j]) $$

• Algorithm: Initialize $$\displaystyle D^0 $$ = adjacency matrix (∞ for no edge, 0 diagonal). For $$\displaystyle k=1..n $$, update all $i,j$.

• Complexity: $$\displaystyle O(n^3) $$. Also reconstructs paths via predecessor matrix.

$$ \boxed{\text{Time: } \Theta(n^3),\ \text{Space: } \Theta(n^2)} $$

IV. Backtracking

Framework

• Systematic search through solution space (often tree).

• Constraint satisfaction: prune branches violating constraints.

• Pruning: Stop exploring when partial solution cannot lead to full solution.

[!TIP] Backtracking = DFS with pruning. Used for combinatorial problems.

Problems

1. Graph Coloring (m-coloring)

• Goal: Color vertices with $m$ colors so no adjacent vertices share color.

• Algorithm:

  
  M-COLORING(graph, m):
  
    color[1..n] = 0
  
    return BACKTRACK(1)
  
  
  
  BACKTRACK(k):
  
    for color c = 1 to m:
  
      if SAFE(k, c):  // check neighbors of vertex k
  
        color[k] = c
  
        if k == n: return true
  
        if BACKTRACK(k+1): return true
  
        color[k] = 0  // backtrack
  
    return false
  
  

• Complexity: $$\displaystyle O(m^n) $$ worst-case.

2. N-Queen Problem

• Goal: Place $n$ queens on $n \times n$ chessboard so no two attack.

• Constraint: No two queens in same row, column, or diagonal.

• Backtracking: Place queens row by row. For row $k$, try each column $c$; if safe, recurse to row $k+1$.

• 4-Queen Example: Solutions: [2,4,1,3] and [3,1,4,2] (column positions per row).

• Complexity: $O(n!)$ with pruning.

3. Hamiltonian Cycle

• Goal: Find cycle visiting each vertex exactly once.

• Backtracking:

  1. Start at vertex $$\displaystyle v_0 $$, path = $$\displaystyle [v_0] $$.

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

     • If $u$ not in path and (if $$\displaystyle u=v_0 $$ only when path length = $n$), add $u$.

     • Recurse. If path length $n+1$ (cycle), success.

  3. Backtrack if dead end.

• Complexity: $O(n!)$.

V. Branch and Bound

Methodology

• State Space Tree: Nodes represent partial solutions.

• Bounding Function: Computes lower/upper bound on cost in subtree.

• Pruning: Discard node if bound worse than current best.

• Strategies: FIFO (queue), LIFO (stack), best-first (priority queue by bound).

Travelling Salesman Problem (TSP)

Reduction Method (Cost Matrix):

1. Row Reduction: For each row, subtract min element in that row from all elements in row.

2. Column Reduction: For each column, subtract min element in that column.

3. Lower Bound = sum of all subtracted minima.

4. If zero(s) in matrix, consider edges corresponding to zeros to form reduced graph.

Branch and Bound with Reduction:

• Node: Partial tour (path), reduced cost matrix, bound.

• Branch: Extend path by adding next vertex (not yet visited).

• Bound: For node with path $$\displaystyle v_1 \to ... \to v_k $$, set row $$\displaystyle v_k $$ and column $$\displaystyle v_1 $$ to ∞ (prevent return to start and reuse $$\displaystyle v_k $$). Reduce matrix, new bound = old bound + cost($$\displaystyle v_{k-1},v_k $$) + reduction cost.

• Prune: If bound ≥ current best tour cost.

• Example (Dec 2024 matrix):

$$ \begin{bmatrix} \infty & 20 & 30 & 10 & 11 \\ 15 & \infty & 16 & 4 & 2 \\ 3 & 5 & \infty & 2 & 4 \\ 19 & 6 & 18 & \infty & 3 \\ 16 & 4 & 7 & 16 & \infty \end{bmatrix} $$

Start at vertex 1 (index 0). Reduce matrix, compute initial bound. Branch on possible next vertices (2,3,4,5), compute bounds, explore promising branches first.

VI. Advanced Topics and Complexity Theory

Complexity Classes

Relations:

$$ \boxed{\text{P} \subseteq \text{NP} \quad \text{NP-Complete} \subseteq \text{NP-Hard}} $$

If $$\displaystyle \text{P} = \text{NP} $$, then all NP-Complete in P. Widely believed false.

[!TIP] To prove NP-Complete: (1) Show in NP, (2) Reduce known NP-Complete problem to it.

Approximation Algorithms

• For NP-Hard problems: Find solution within factor $\rho$ of optimum in polynomial time.

• Approximation Ratio: $$\displaystyle \rho = \frac{\text{algorithm cost}}{\text{optimum cost}} $$ (maximization: $$\displaystyle \frac{\text{opt}}{\text{alg}} $$).

• PTAS: Polynomial Time Approximation Scheme. For any $$\displaystyle \epsilon>0 $$, $(1+\epsilon)$-approximation in time poly($n$) for fixed $\epsilon$.

• Examples:

  • Vertex Cover: 2-approximation (pick both endpoints of an edge).

  • TSP with triangle inequality: 1.5-approximation (Christofides).

Data Stream Algorithms

• Streaming Model: Data arrives as stream, one pass, limited memory (sublinear in $n$).

• Goals: Estimate aggregates (frequency moments, heavy hitters).

• Algorithms:

  • Misra-Gries (Frequent Items): Keep at most $k-1$ counters for top-$k$ frequent items. $O(k)$ space.

  • Bloom Filters: Approximate set membership with false positives.

  • Count-Min Sketch: Estimate frequency of items.

Data Transfer Optimization

• Context: Minimize total transfer time/cost in networks (e.g., file distribution, cloud data).

• Approaches:

  • Greedy: Always send to nearest/fastest node.

  • DP: For sequential transfers with constraints.

  • Network Flow: Model as max-flow/min-cost flow.

• Example: Transfer file of size $F$ from source to $n$ clients with bandwidths $$\displaystyle b_i $$. Min time = $$\displaystyle \max(F / \sum b_i,\ \max_i F/b_i) $$? Actually, optimal scheduling uses water-filling.

B-trees

• Structure: Balanced search tree with order $m$:

  • Each node has ≤ $m$ children, ≥ $\lceil m/2 \rceil$ (except root).

  • All leaves at same depth.

  • Keys in node sorted, $n$ keys → $n+1$ children.

• Insertion:

  1. Search leaf, insert key (sorted).

  2. If overflow (≥ $m$ keys), split median up to parent.

  3. Propagate splits up to root (root split increases height).

• Example: Order 3 B-tree (2-3 tree). Insert keys 10,20,30,5,15. Show splits.

• Complexity: Search/Insert/Delete: $$\displaystyle O(\log_m n) $$.

Parallel Algorithms

• Design Paradigms:

  • Divide-and-Conquer: Parallelize recursive calls (e.g., parallel merge sort).

  • MapReduce: Map phase (independent), Shuffle, Reduce.

  • Pointer Jumping: For linked lists/trees.

• Complexity Measures:

  • Work $W(n)$: Total operations across all processors.

  • Span (critical path) $$\displaystyle T_{\infty}(n) $$: Longest chain of dependencies.

  • Parallel Time on $P$ processors: $$\displaystyle T_P(n) \ge \max(T_{\infty}(n),\ W(n)/P) $$ (Greedy scheduling).

• Example: Parallel sum of $n$ numbers using binary tree: $$\displaystyle W(n)=O(n) $$, $$\displaystyle T_{\infty}(n)=O(\log n) $$.

Logic Optimization

• Goal: Minimize Boolean function (e.g., sum-of-products) for hardware.

• Algorithmic Aspects:

  • Quine-McCluskey: Tabular method for minimization (exponential in worst-case).

  • Espresso: Heuristic for large functions.

  • Binary Decision Diagrams (BDDs): Canonical representation, useful for equivalence checking.

• Steps: Find prime implicants via consensus, cover minterms with essential primes.

EXAM-READY SUMMARY

• Recurrences: Master Theorem is key. Strassen’s $$\displaystyle T(n)=7T(n/2)+\Theta(n^2) \Rightarrow \Theta(n^{\log_2 7}) $$.

• Greedy: Prove greedy choice + optimal substructure. Job sequencing: sort by profit, assign latest slot. Fractional knapsack: sort by $$\displaystyle p_i/w_i $$.

• DP: Identify subproblems, recurrence, table. 0/1 knapsack $O(nM)$. Floyd-Warshall $$\displaystyle O(n^3) $$.

• Backtracking: Systematize search, prune early. N-Queen: check diagonals.

• Branch and Bound: TSP reduction → bound → prune. Use priority queue (best-first).

• Complexity: P ⊆ NP, NP-Complete = NP ∩ NP-Hard. Reduce SAT to prove NP-Complete.

• Advanced: B-tree insertion splits. Parallel time = max(span, work/P). Approximation ratio for TSP metric: 1.5 (Christofides).

[!TIP] Past papers emphasize: Strassen’s, Quick Sort avg proof, Job Sequencing (numerical), Fractional Knapsack (numerical), Huffman, Dijkstra’s, Floyd-Warshall, Reliability Design, Multistage Graph, 0/1 Knapsack, Graph Coloring, N-Queen, TSP (branch and bound), P/NP/NP-Complete, B-trees, Data Streams, Approximation, Data Transfer, Parallel, Logic Optimization. Practice numerical examples from June/Dec 2024.