Several recurring paradigms underlie the design of efficient algorithms. Recursion is the process in which a function calls itself as a subroutine, while iteration uses a loop to repeat a process; recursion can be more memory intensive because of call-stack overhead. Dynamic programming is a paradigm that solves a complex problem by breaking it into overlapping subproblems and storing their results to avoid recomputation, and it can be expressed either through memoization, a top-down approach that caches function call results, or through tabulation, a bottom-up approach that fills a table iteratively. A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Divide and conquer solves a problem in three steps: Divide, Conquer, and Combine. Backtracking incrementally builds a solution piece by piece, abandoning and removing partial solutions that fail to satisfy the problem's constraints. Branch and bound is a paradigm for discrete and combinatorial optimization that systematically enumerates candidate solutions through state space search, while meet-in-the-middle divides the search space into two roughly equal parts, searches each part separately, and combines results, often reducing exponential complexity from \(O(2^n)\) to \(O(2^{n/2})\).
Beyond these classical paradigms, several widely used patterns simplify specific problem classes. The two pointers technique uses two pointers that iterate through a data structure in tandem until one or both hit a stopping condition, and the sliding window technique performs an operation on a contiguous window of an array or linked list, such as finding the longest subarray containing all ones. Convex hull trick is a geometry-based optimization for DP transitions involving linear functions, often reducing complexity from \(O(n^2)\) to \(O(n \log n)\) or \(O(n)\). Binary lifting is a dynamic programming approach used to find the kth ancestor of a tree node or to compute the lowest common ancestor, the deepest node that has both v and w as descendants, efficiently in \(O(\log n)\) time. Huffman coding, which uses variable-length codes assigned to characters based on their frequencies for lossless data compression, and the A* algorithm, which combines graph traversal with a heuristic to achieve optimal pathfinding, often appear as building blocks in larger algorithmic systems. Classical number-theoretic tools such as the Sieve of Eratosthenes, the Euclidean algorithm, and modular exponentiation, along with the Fast Fourier Transform and Catalan numbers, are recurring primitives across many paradigms.
Many canonical optimization problems showcase how the paradigms interact. The knapsack problem asks for the subset of items, each with a weight and a value, that maximizes total value without exceeding a weight limit; in 0/1 knapsack items cannot be broken, while in fractional knapsack items can be split. The longest common subsequence problem finds the longest subsequence common to two or more sequences, the longest increasing subsequence problem finds the longest strictly increasing subsequence of a given sequence, the matrix chain multiplication problem determines the most efficient parenthesization of a chain of matrix multiplications, and the edit distance, or Levenshtein distance, between two strings is the minimum number of insertions, deletions, and substitutions needed to transform one into the other. Other classic problems include the traveling salesman problem, which asks for the shortest route that visits every city exactly once and returns to the origin, the vertex cover problem, which finds the smallest set of vertices such that every edge is incident to at least one chosen vertex, the set cover problem, which finds the smallest sub-collection of sets whose union equals the universe, and the clique problem, which finds a subset of vertices in which every pair is adjacent, with the maximum clique variant being NP-hard. Together these paradigms and problems illustrate how the same fundamental ideas reappear across diverse problem domains.