Major Algorithm Families

1. Definition & Classification

In computer science, an algorithm is a finite sequence of well-defined instructions designed to solve a specific problem or perform a computation. Algorithm families emerge when researchers and practitioners group these procedures based on shared structural patterns, mathematical invariants, or strategic approaches to decomposition and optimization.

Classification is not always rigid; many modern algorithms hybridize techniques from multiple families. However, understanding these core paradigms provides a foundational framework for analyzing time/space complexity, designing novel solutions, and evaluating trade-offs in real-world systems.

1.1 Divide and Conquer

Divide and conquer algorithms recursively break a problem into two or more independent subproblems of the same type, solve each recursively, and combine the results. The paradigm excels when subproblems are significantly smaller and the combination step is efficient.

Notable examples: Merge Sort, Quick Sort, Binary Search, Karatsuba Multiplication, Fast Fourier Transform (FFT), and the Coq proof verification framework.

function mergeSort(arr):
    if length(arr) <= 1: return arr
    mid = length(arr) // 2
    left = mergeSort(arr[0:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

1.2 Dynamic Programming

Dynamic programming (DP) optimizes divide and conquer by caching solutions to overlapping subproblems. It applies when a problem exhibits optimal substructure (optimal solution contains optimal sub-solutions) and overlapping subproblems (subproblems recur).

DP can be implemented top-down with memoization or bottom-up with tabulation. It is foundational in bioinformatics (sequence alignment), operations research (knapsack, shortest paths), and machine learning (Viterbi algorithm, HMMs).

1.3 Greedy Algorithms

Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. They are efficient (O(n log n) or O(n)) and simple to implement but only yield correct results for problems with the greedy choice property and optimal substructure.

Classic applications: Dijkstra's shortest path (non-negative weights), Kruskal's and Prim's minimum spanning trees, Huffman coding, and activity selection problems.

1.4 Backtracking & Branch-and-Bound

Backtracking explores the solution space incrementally, abandoning partial candidates ("backtracking") as soon as they violate constraints. It is exhaustive but pruned, making it suitable for combinatorial optimization, constraint satisfaction, and puzzle solving (N-Queens, Sudoku, exact cover).

Branch-and-bound extends this by maintaining upper/lower bounds on objective values to prune entire subtrees. It is the theoretical backbone of integer linear programming (ILP) solvers like CPLEX and Gurobi.

1.5 Graph & Network Algorithms

While sometimes overlapping with other families, graph algorithms form a distinct category due to their reliance on topology, connectivity, and flow theory. They power routing protocols, social network analysis, dependency resolution, and logistics optimization.

• Traversal: BFS, DFS, Iterative Deepening
• Shortest Path: Dijkstra, Bellman-Ford, Floyd-Warshall, A*
• Flow & Matching: Ford-Fulkerson, Hopcroft-Karp, Edmonds' Blossom
• Connectivity: Tarjan's SCC, Hopcroft-Tarjan bridge-finding, Union-Find

2. Comparative Analysis

The table below summarizes key theoretical properties across major algorithm families. Practical performance heavily depends on input distribution, hardware architecture, and implementation quality.

3. Evolution & Modern Trends

Algorithm design has shifted from purely sequential, deterministic models toward adaptive, randomized, and learning-driven paradigms. Key trends include:

• Randomized Algorithms: Monte Carlo and Las Vegas methods provide probabilistic guarantees with faster expected runtimes (e.g., QuickSort, Miller-Rabin primality).
• Approximation & Heuristics: NP-hard problems increasingly rely on PTAS, FPTAS, and metaheuristics (genetic algorithms, simulated annealing, ant colony optimization).
• Algorithmic Machine Learning: Neural architectures now learn algorithmic policies (e.g., differentiable sorting, graph neural networks for routing, transformer-based planners).
• Quantum Algorithm Families: Shor's, Grover's, and HHL algorithms represent a paradigm shift, leveraging superposition and interference for exponential/quadratic speedups in specific domains.
• Streaming & External-Memory Algorithms: Optimized for big data, cache-oblivious structures, and one-pass processing under strict memory bounds.