Algorithm Design Paradigms
Algorithm design paradigms are the recurring high-level strategies — divide-and-conquer, dynamic programming, greedy choice, and exhaustive search with pruning — used to construct correct and efficient algorithms for computational problems.
Definition
An algorithm design paradigm is a general template or strategy for solving a class of problems, characterized by a way of decomposing the problem and combining sub-solutions, together with the structural properties a problem must have for the paradigm to apply.
Scope
This area covers the general-purpose techniques for building algorithms independent of any single problem domain. It treats how a problem's structure (optimal substructure, overlapping subproblems, the greedy-choice property, decomposability) suggests a matching strategy, and how each paradigm is reasoned about for correctness and analyzed for running time. It excludes the data structures that implement these algorithms (covered in fundamental data structures) and the complexity-theoretic limits on what any algorithm can achieve (covered in complexity and analysis of algorithms).
Sub-topics
Core questions
- What structural property of a problem makes a given paradigm applicable and correct?
- How is a recursive decomposition turned into an efficient algorithm via memoization or tabulation?
- When does a locally optimal (greedy) choice lead to a globally optimal solution?
- How is the running time of a paradigm-based algorithm derived, e.g. via recurrences?
- How do exhaustive-search paradigms prune the search space to remain tractable on typical instances?
Key concepts
- divide-and-conquer
- recurrence relations
- dynamic programming
- memoization and tabulation
- greedy choice and exchange arguments
- backtracking
- branch and bound
- optimal substructure
- exhaustive search and pruning
Key theories
- Optimal substructure
- A problem has optimal substructure when an optimal solution can be assembled from optimal solutions to its subproblems; this property underlies both dynamic programming and many greedy algorithms.
- Overlapping subproblems and memoization
- When a recursive decomposition revisits the same subproblems repeatedly, storing each subproblem's solution (memoization or bottom-up tabulation) reduces exponential recomputation to polynomial time — the basis of dynamic programming.
- Greedy-choice property
- Some problems admit a globally optimal solution built by repeatedly making the choice that looks best at the moment; correctness is typically proved by an exchange argument or via matroid theory.
Clinical relevance
Design paradigms are the working vocabulary of practical software: divide-and-conquer underlies fast sorting and signal processing, dynamic programming powers sequence alignment in bioinformatics and shortest-path subroutines, greedy methods drive scheduling and data compression (Huffman coding), and branch-and-bound is central to combinatorial optimization and operations research.
History
Divide-and-conquer reasoning predates computers but became central with fast algorithms such as mergesort and Karatsuba multiplication in the 1960s. Richard Bellman introduced dynamic programming in the 1950s. The systematic textbook treatment of paradigms as a unifying lens matured through works such as Aho, Hopcroft and Ullman's design-and-analysis text and later CLRS and Kleinberg-Tardos.
Key figures
- Richard Bellman
- Thomas H. Cormen
- Jon Kleinberg
- Éva Tardos
- Robert Sedgewick
Related topics
Seminal works
- cormen2009
- kleinberg2006
- sedgewick2011
Frequently asked questions
- What is the difference between dynamic programming and greedy algorithms?
- Both exploit optimal substructure, but a greedy algorithm commits to one locally optimal choice at each step and never reconsiders it, whereas dynamic programming considers and combines solutions to all relevant subproblems. Greedy is faster when it applies but is correct for fewer problems.
- How do I know which paradigm to use?
- Look at the problem's structure: decomposable into independent subproblems suggests divide-and-conquer; overlapping subproblems with optimal substructure suggests dynamic programming; a provable greedy-choice property suggests a greedy algorithm; and otherwise systematic search with pruning (backtracking or branch-and-bound) may be required.