UNIT 5: ADVANCED ALGORITHMIC PARADIGMS AND ANALYSIS

I. FUNDAMENTALS OF ALGORITHM ANALYSIS

Time Complexity

Definition: Measures the amount of computational time an algorithm takes as a function of input size n.
Significance: Enables comparison of algorithm efficiency independent of hardware/implementation.
Asymptotic Notations:
- Big O (O): Upper bound. $$\displaystyle f(n) = O(g(n)) $$ if $$\displaystyle \exists c > 0, n_0 $$ s.t. $0 \le f(n) \le c \cdot g(n)$ for all $$\displaystyle n \ge n_0 $$.
- Omega (Ω): Lower bound. $$\displaystyle f(n) = \Omega(g(n)) $$ if $$\displaystyle \exists c > 0, n_0 $$ s.t. $0 \le c \cdot g(n) \le f(n)$ for all $$\displaystyle n \ge n_0 $$.
- Theta (Θ): Tight bound. $$\displaystyle f(n) = \Theta(g(n)) $$ if $$\displaystyle f(n) = O(g(n)) $$ and $$\displaystyle f(n) = \Omega(g(n)) $$.

Recurrence Relations

Describes runtime of recursive/divide-and-conquer algorithms. Solving Techniques:

Substitution Method: Guess solution, verify by induction.
Recursion Tree: Visualize costs per level, sum them.
Master Theorem: For $$\displaystyle T(n) = aT(n/b) + f(n) $$, where $$\displaystyle a \ge 1, b > 1 $$:
- If $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a}) $$.
- If $$\displaystyle f(n) = \Theta(n^{\log_b a}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a} \log n) $$.
- If $$\displaystyle f(n) = \Omega(n^{\log_b a + \epsilon}) $$ and regularity condition holds, then $$\displaystyle T(n) = \Theta(f(n)) $$.

[!TIP] Common Pitfall: Misapplying Master Theorem when $f(n)$ is not polynomially larger/smaller than $$\displaystyle n^{\log_b a} $$.

Average-Case Analysis

Evaluates expected performance over all inputs of size n assuming a probability distribution.
Quicksort Example:
- Worst-case (pivot always smallest/largest): $$\displaystyle T(n) = T(n-1) + \Theta(n) \Rightarrow O(n^2) $$.
- Average-case (pivot splits array reasonably): Recurrence $$\displaystyle T(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + \Theta(n) $$.
- Solution: $$\displaystyle T(n) = O(n \log n) $$.

II. DIVIDE AND CONQUER ALGORITHMS

Merge Sort

Algorithm:

Divide array into two halves.
Recursively sort each half.
Merge two sorted halves. Complexity: Recurrence $$\displaystyle T(n) = 2T(n/2) + \Theta(n) $$.

By Master Theorem (Case 2): $$\displaystyle T(n) = \Theta(n \log n) $$.

Quicksort

Partitioning (Lomuto/Hoare):

Choose pivot (often last/first element).
Rearrange array so elements < pivot left, > pivot right.
Return pivot index. Complexity:
Worst-case (already sorted/reverse sorted with bad pivot): $$\displaystyle T(n) = T(n-1) + \Theta(n) \Rightarrow O(n^2) $$.
Average-case: $$\displaystyle T(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + \Theta(n) \Rightarrow \boxed{O(n \log n)} $$.

Strassen's Matrix Multiplication

Algorithm:

For two $n \times n$ matrices (assume $n$ is power of 2), divide each into 4 submatrices.
Compute 7 products recursively instead of 8.
Combine to get result. Complexity: Recurrence $$\displaystyle T(n) = 7T(n/2) + \Theta(n^2) $$.

By Master Theorem: $$\displaystyle T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.8074}) $$.

III. GREEDY ALGORITHMS

Core Principles

Greedy Choice Property: A locally optimal choice leads to a globally optimal solution.
Optimal Substructure: Optimal solution contains optimal solutions to subproblems.
Proving Correctness: Show greedy choice is safe (leads to optimal) and problem has optimal substructure.

Job Sequencing with Deadlines

Problem: Maximize profit by scheduling jobs with deadlines (1 unit time each) on single machine. Greedy Algorithm:

Sort jobs by decreasing profit.
Initialize result array of size max deadline, all slots free.
For each job in sorted order, place it in the latest free slot before its deadline. Example (Jun 2024):

Jobs: (P:100,10,15,27), (d:2,1,2,1)
Sorted by profit: Job1(100,d2), Job4(27,d1), Job3(15,d2), Job2(10,d1)
Schedule: Slot2=Job1, Slot1=Job4 → Max Profit = 127.

Knapsack Problem (Fractional)

Problem: Maximize total value with weight capacity W, items can be taken fractionally. Greedy Approach:

Compute value/weight ratio for each item.
Sort items by decreasing ratio.
Take as much as possible of each item in order until capacity filled. Example (Dec 2024):

n=5, M=10, p=(10,15,10,12,8), w=(3,3,2,5,1)
Ratios: 3.33, 5, 5, 2.4, 8 → Sort: Item5(8,1), Item2(15,3), Item3(10,2), Item1(10,3), Item4(12,5)
Take: full item5 (w1,val8), full item2 (w3,val15) → total w=4, val=23.
Next item3: take full (w2,val10) → total w=6, val=33.
Next item1: take full (w3,val10) → total w=9, val=43.
Next item4: take 1 unit (w1/5, val 12/5=2.4) → total w=10, val=45.4.

Huffman Coding

Algorithm for Optimal Prefix Codes:

Create min-heap of nodes (char, freq).
While heap size > 1:
- Extract two min-freq nodes.
- Create new internal node with freq = sum, left/right children.
- Insert new node into heap.
Remaining node is root. Traverse to assign codes (left=0, right=1). Example: Given frequencies, build tree to get variable-length codes (shorter for frequent chars).

Optimal Merge Pattern

Problem: Minimize total cost to merge k sorted lists (cost = sum of lengths merged). Relation to Huffman: Identical to constructing Huffman tree—merge smallest lists first. Algorithm: Use min-heap, repeatedly merge two smallest lists until one remains. Total Cost: Sum of all internal node frequencies in merge tree.

Minimum Spanning Tree (MST)

Kruskal's Algorithm:

Sort all edges by increasing weight.
Initialize forest (each vertex separate).
For each edge in order:
- If edge connects two different trees (no cycle), add it.
- Use Union-Find (Disjoint Set) to detect cycles efficiently. Complexity: $O(E \log E)$ dominated by sorting.

Single-Source Shortest Paths (Dijkstra)

Greedy with Priority Queue:

Initialize dist[source]=0, others=∞. Priority queue (min-heap) of (dist, vertex).
While queue not empty:
- Extract min u.
- For each neighbor v of u:
  - If dist[u] + weight(u,v) < dist[v], update dist[v] and decrease-key in heap. Works for: Non-negative edge weights. Complexity: $O((V+E) \log V)$ with binary heap.

IV. DYNAMIC PROGRAMMING

Key Concepts

Overlapping Subproblems: Problem can be broken down into subproblems reused multiple times.
Memoization (Top-down): Recursive with caching results.
Tabulation (Bottom-up): Fill DP table iteratively.

All-Pairs Shortest Paths (Floyd-Warshall)

Algorithm:


for k from 1 to n:

  for i from 1 to n:

    for j from 1 to n:

      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Input: Adjacency matrix (∞ for no edge, 0 for diagonal). Output: Matrix of shortest distances. Complexity: $$\displaystyle O(n^3) $$. Detects negative cycles: If dist[i][i] < 0 after algorithm.

Reliability Design

Problem: Maximize system reliability with cost constraint. System has k stages, each stage can choose device type with reliability $$\displaystyle r_i $$ and cost $$\displaystyle c_i $$. Total cost ≤ budget. DP Approach:

Let R[i][C] = max reliability for first i stages with cost exactly C.
Recurrence: $$\displaystyle R[i][C] = \max_{j: c_{i,j} \le C} \{ r_{i,j} \times R[i-1][C - c_{i,j}] \} $$.
Compute table for all stages and costs up to budget.
Answer: $$\displaystyle \max_{C \le budget} R[k][C] $$.

Multistage Graph

Problem: Find shortest path from source s to sink t in directed acyclic graph with stages. DP (Forward/Backward Pass):

Let cost[i] = shortest distance from node i to t.
Backward: Process nodes in reverse topological order:

$$\displaystyle cost[i] = \min_{j \in \text{successors}(i)} \{ \text{weight}(i,j) + cost[j] \} $$.
cost[s] is answer. Complexity: $O(V + E)$.

V. BACKTRACKING

General Framework

Build solution incrementally.
State Space Tree: Nodes represent partial solutions.
Pruning: Abandon branch as soon as determined it cannot lead to valid/optimal solution.

Graph Coloring (m-coloring)

Problem: Color graph vertices with m colors so no adjacent vertices same color. Algorithm:


bool graphColoring(graph, m):

  color[1..n] = {0}

  return colorUtil(1, color, m)

bool colorUtil(v, color, m):

  if v > n: return true  // all colored

  for c = 1 to m:

    if isSafe(v, color, c):

      color[v] = c

      if colorUtil(v+1, color, m): return true

      color[v] = 0  // backtrack

  return false

isSafe(v, color, c):

  for each neighbor u of v:

    if color[u] == c: return false

  return true

N-Queens Problem

Place n queens on n×n chessboard so no two attack each other. Algorithm:

Place queens row by row.
For each row i, try each column j:
- Check if safe (no queen in same column, or diagonal).
- If safe, place queen and recurse for row i+1.
- If recursion succeeds, return solution.
- Else, remove queen (backtrack). Example 4-Queens: Solutions: [2,4,1,3] and [3,1,4,2] (1-indexed column positions per row).

Hamiltonian Cycle

Problem: Find cycle visiting each vertex exactly once and returning to start. Backtracking:

Start at vertex 0, path[0]=0.
Recursively try to add next vertex v if:
- v not already in path.
- Edge exists from last vertex in path to v.
If path length = n and edge from last to start exists → cycle found.
Else backtrack.

VI. BRANCH AND BOUND

Methodology

State Space Tree: Systematically enumerate candidate solutions.
Bounding Function: Computes lower/upper bound on cost of any solution in a subtree.
Best-First Search: Explore most promising node first (using priority queue).
Pruning: Discard node if its bound ≥ best solution found so far.

Travelling Salesperson Problem (TSP)

Reduction Method for Cost Matrix:

Row Reduction: For each row, subtract min element of that row from all elements.
Column Reduction: For each column, subtract min element of that column.
Lower Bound = sum of all subtracted values.
Set zero entries as potential edges to include. Branch and Bound Algorithm:

Start with reduced matrix, lower bound LB.
For each edge (i,j) not yet decided:
- Include edge: Set row i and column j to ∞ (except (j,i) to avoid subtour), reduce matrix, new LB = old LB + cost[i][j] + reduction_cost.
- Exclude edge: Set cost[i][j] = ∞, reduce matrix, new LB = old LB + reduction_cost.
Use priority queue (min-heap) ordered by LB.
Explore node with smallest LB first.
If LB ≥ best known tour cost, prune.
When path length = n and return to start possible → complete tour, update best.

Example (Dec 2024 5x5 matrix): Apply reduction, then systematically branch on edges, compute bounds, prune aggressively.

VII. COMPLEXITY THEORY

Complexity Classes

P: Problems solvable in polynomial time by deterministic Turing machine. (e.g., sorting, shortest path).
NP: Problems verifiable in polynomial time (solution can be checked quickly). Equivalently, solvable in polynomial time by non-deterministic Turing machine. (e.g., TSP, Boolean satisfiability).
NP-Hard: Problems at least as hard as hardest problems in NP. Every NP problem reduces to them in polynomial time. Not necessarily in NP (may not have polynomial-time verifiable solutions). (e.g., Halting Problem, optimization version of TSP).
NP-Complete: Problems that are both NP-Hard and in NP. (e.g., decision version of TSP, 3-SAT, Clique).

Relationships and Reductions


    P ⊆ NP

    NP-Complete ⊆ NP

    NP-Complete ⊆ NP-Hard

    (If P = NP, then all equal; widely believed false)

Polynomial-Time Reduction: Transform instance of problem A to instance of problem B in polynomial time such that answer is "yes" for A iff "yes" for B. Used to prove NP-Hardness.

Comparison: NP-Hard vs NP-Complete

Feature	NP-Complete	NP-Hard
In NP?	Yes	Not necessarily
Definition	Hardest problems in NP	At least as hard as NP
Example	3-SAT, Clique	TSP (optimization), Halting Problem
Implication if solved in P	P = NP	P = NP (if also in NP)

VIII. ADVANCED ALGORITHMIC TOPICS

B-trees

Structure:

Order m: Each node has at most m children, at least $\lceil m/2 \rceil$ children (except root), at most m-1 keys.
All leaves at same depth. Insertion:

Search leaf where key should go.
If leaf has < m-1 keys, insert sorted.
If leaf full, split:
- Median key moves up to parent.
- Split node into two with lower/upper keys.
- Recursively split parent if full. Example: Construct B-tree of order 5 with insert sequence: 10,20,30,40,50,60,70,80,90.

Data Stream Algorithms

Overview: Process massive data streams (one pass, limited memory). Examples:

Frequency Counting: Misra-Gries algorithm (keep k most frequent items with counts).
Distinct Elements: Flajolet-Martin algorithm (probabilistic using hashing and bit patterns).
Heavy Hitters: Count-Min Sketch (estimate frequencies).

Approximation Algorithms

Concept: For NP-Hard problems, find solution close to optimal in polynomial time.

Performance Ratio $\rho$: $$\displaystyle \frac{\text{algorithm cost}}{\text{optimal cost}} \le \rho $$ for minimization (or ≥ for maximization). Examples:
Vertex Cover: Greedy picking both endpoints of an arbitrary edge → 2-approximation.
TSP with Triangle Inequality: Christofides algorithm (1.5-approximation).

Data Transfer Optimization

Context: Schedule data transfers in networks (e.g., MapReduce shuffle phase) to minimize makespan. Algorithmic Approaches:

Model as multicommodity flow or scheduling with precedence constraints.
Greedy heuristics: Prioritize large transfers early, or use bipartite matching for worker-data assignment.
Often NP-Hard → use approximation or LP relaxation.

Parallel Algorithms

Design Goals:

Speedup: $$\displaystyle S(p) = T(1)/T(p) $$.
Efficiency: $$\displaystyle E(p) = S(p)/p $$.
Work: $$\displaystyle W = p \cdot T(p) $$ (total operations across all processors).
Span (Critical Path Length): Longest chain of dependencies. Complexity Analysis:
Work-optimal: $W$ matches best sequential algorithm.
Span: Determines parallel time via Brent's Theorem: $$\displaystyle T(p) \le \frac{W}{p} + \text{span} $$. Example: Parallel merge sort: work $O(n \log n)$, span $$\displaystyle O(\log^2 n) $$.

Logic Optimization

Overview: Simplify Boolean functions (e.g., in circuit design). Relevance: Minimizes logic gates, reduces cost/delay. Methods:

Karnaugh Maps: Manual grouping for small variables.
Quine-McCluskey: Tabular method for many variables.
Espresso Algorithm: Heuristic for large-scale industrial use.
Binary Decision Diagrams (BDDs): Canonical representation for equivalence checking.

Exam Strategy: Focus on Greedy (Job Seq, Knapsack, Huffman, MST, Dijkstra), DP (Floyd, Reliability, Multistage), Backtracking (N-Queens, Graph Coloring), Branch & Bound (TSP reduction), and Complexity Classes distinctions. Practice solving recurrences (Master Theorem) and applying algorithms to given numerical/graph instances from past papers.