6.4 Algorithmic Paradigms

An algorithmic paradigm is a general strategy or framework for designing algorithms to solve computational problems. Rather than focusing on a specific problem, paradigms define how a problem should be decomposed, approached, or optimized. Mastery of these paradigms enables developers and researchers to select the most efficient and mathematically sound approach for complex tasks.

1. Divide & Conquer

Divide and conquer recursively breaks a problem into two or more independent subproblems of the same type, solves each recursively, and combines the results. This paradigm excels when subproblems are independent and the combination step is efficient.

Core Characteristics:

• Recursion-driven decomposition
• Independent subproblems
• Efficient merge/combine step
• Typical complexity: O(n log n) for sorting/searching

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Classic Applications: Merge Sort, Quick Sort, Binary Search, Strassen’s Matrix Multiplication, Closest Pair of Points.

2. Dynamic Programming

Dynamic programming (DP) optimizes recursive solutions that exhibit overlapping subproblems and optimal substructure. Instead of recomputing results, DP stores intermediate solutions in a table (memoization/top-down or tabulation/bottom-up), reducing exponential time to polynomial.

def fib_dp(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Classic Applications: Knapsack Problem, Longest Common Subsequence, Matrix Chain Multiplication, Edit Distance, Floyd-Warshall Algorithm.

3. Greedy Algorithms

Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum. They are highly efficient but require proof of correctness (greedy choice property + optimal substructure). No backtracking or reconsideration of past decisions occurs.

def activity_selection(start, finish):
    n = len(finish)
    result = [0]
    j = 0
    for i in range(1, n):
        if start[i] >= finish[j]:
            result.append(i)
            j = i
    return result

Classic Applications: Dijkstra’s Shortest Path, Kruskal’s/Prim’s MST, Huffman Coding, Interval Scheduling, Fractional Knapsack.

4. Backtracking

Backtracking is a systematic search technique that explores potential solutions incrementally. When a partial solution violates constraints, the algorithm "backtracks" by undoing the last choice and trying alternatives. It’s essentially depth-first search with pruning.

Key Components:

• State space tree representation
• Constraint checking (feasibility)
• Pruning invalid branches early

Classic Applications: N-Queens Problem, Sudoku Solver, Hamiltonian Path, Subset Sum, Crossword Puzzle Filling.

5. Branch & Bound

Branch and bound is an optimization extension of backtracking, primarily used for combinatorial optimization problems. It maintains upper/lower bounds for each node in the state space tree. Nodes that cannot possibly yield a better solution than the current best are pruned.

Difference from Backtracking: Backtracking finds any valid solution; Branch & Bound finds the optimal solution by evaluating cost bounds.

Classic Applications: Traveling Salesman Problem (TSP), 0/1 Knapsack (optimization variant), Integer Programming, Job Sequencing with Deadlines.

6. Randomized Algorithms

Randomized algorithms use randomness as part of their logic. They fall into two categories:

• Las Vegas: Always correct, but runtime is probabilistic (e.g., Randomized QuickSort).
• Monte Carlo: Fixed runtime, but may return approximate or incorrect results with bounded probability (e.g., Miller-Rabin primality test).

Classic Applications: Randomized QuickSort, Karger’s Min-Cut, Monte Carlo Integration, Hashing/Collision Resolution, Cryptography.

Comparative Summary

References & Further Reading