Algorithm Design Paradigms

Introduction

An algorithm design paradigm is a general strategy for constructing algorithms. Instead of inventing every solution from first principles, programmers recognize the structure of a problem and select a suitable paradigm. The choice affects correctness, running time, memory use, implementation complexity, and maintainability.

This chapter examines seven important paradigms: brute force, decrease-and-conquer, divide-and-conquer, greedy algorithms, dynamic programming, memoization, and branch-and-bound. These approaches are not mutually exclusive. For example, memoization is an implementation technique commonly used to realize dynamic programming, while branch-and-bound may use a recursive decomposition resembling divide-and-conquer.

A useful design process is:

1. Define the problem precisely, including inputs, outputs, and constraints.
2. Identify the structure of possible solutions.
3. Determine whether the problem has optimal substructure, overlapping subproblems, or a useful bound.
4. Select a paradigm and justify the choice.
5. Prove or argue correctness.
6. Analyze time and space complexity.
7. Implement, test, and evaluate practical trade-offs.

Learning Objectives

After studying this chapter, you should be able to:

• explain the principal algorithm design paradigms;
• implement representative algorithms in Java and Python;
• distinguish optimal substructure from overlapping subproblems;
• derive and interpret recurrence relations;
• justify the selection of a design paradigm;
• compare recursive, iterative, memoized, and tabulated solutions;
• apply branch-and-bound to constrained optimization problems; and
• evaluate practical issues such as memory, input size, data representation, and reproducibility.

1. Brute Force: Establishing a Reliable Baseline

A brute-force algorithm systematically examines all candidate solutions, or applies the most direct procedure suggested by the problem definition. It does not exploit sophisticated structure. Its principal strengths are simplicity, transparency, and reliability as a reference implementation.

For example, linear search examines items from left to right until a target is found. Its worst-case running time is O(n), where n is the number of items. Brute-force substring matching compares a pattern at every possible starting position. If the text has length n and the pattern has length m, its worst-case time is O((n − m + 1)m), commonly written O(nm), with constant extra space.

Brute force is appropriate when:

• the input is small;
• the problem is used infrequently;
• implementation risk is more important than speed;
• a baseline is needed for testing an optimized algorithm; or
• no exploitable structure is known.

Its weakness is combinatorial growth. If n items can be arranged in every possible order, there are n! candidates. If each of n binary decisions may be selected or rejected, there are 2ⁿ candidates. Such growth quickly becomes impractical.

A brute-force solution is not automatically poor engineering. A simple exhaustive algorithm may be the best choice for a small configuration problem, a test oracle, or a safety-critical prototype whose behavior must be easy to audit.

2. Decrease-and-Conquer

Decrease-and-conquer solves a problem by reducing it to one smaller instance, solving that instance, and extending its solution. The reduction may decrease the problem size by one, by a constant factor, or by another known amount.

2.1 Insertion sort

Insertion sort is a decrease-by-one algorithm. It sorts the first n − 1 elements and inserts the nth element into its correct position. The recurrence for worst-case time is:

Here T(n) is running time for n elements. The Θ(n) term represents the worst-case shifting and comparisons required to insert one element. Expanding the recurrence gives Θ(n²). In the best case, when the input is already sorted, only one comparison is needed per insertion, so the time is Θ(n). Insertion sort uses Θ(1) auxiliary space and is stable when implemented by shifting larger elements rather than swapping equal elements.

Python implementation:

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

The same logic in Java uses an array or ArrayList, with explicit types and a while loop. The algorithm is especially useful for small arrays and as the base case of hybrid sorting algorithms.

2.2 Decrease-by-a-factor: binary search

Binary search applies to a sorted array. It compares the target with the middle item and discards half the remaining interval. If n is the number of candidates, its recurrence is:

Therefore its time complexity is Θ(log n), and its iterative version uses Θ(1) auxiliary space. The precondition that the data are sorted is essential. Applying binary search to unsorted data does not produce a valid result.

In production code, midpoint calculation should avoid integer overflow. A safe expression in Java is low + (high - low) / 2. Python integers do not overflow under ordinary integer semantics, but the same expression clearly communicates intent.

3. Divide-and-Conquer

Divide-and-conquer divides a problem into two or more smaller independent subproblems, solves them recursively, and combines their results. The general recurrence is:

where a is the number of subproblems, n/b is the approximate size of each subproblem, and f(n) is the cost of dividing and combining. The recurrence applies when subproblem sizes and combination costs fit these assumptions; otherwise, a more precise recurrence is required.

3.1 Merge sort

Merge sort divides an array into two halves, recursively sorts both halves, and merges the sorted halves. Merging costs Θ(n), producing:

The algorithm has worst-case Θ(n log n) time and Θ(n) auxiliary space for the usual array implementation. It is stable if the merge operation chooses the left element first when equal keys are encountered.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

In Python, slicing creates additional lists; an industrial implementation often uses one auxiliary array. In Java, repeated object allocation should likewise be avoided for performance-sensitive code.

3.2 Quicksort

Quicksort partitions an array around a pivot, then recursively sorts the two partitions. If the pivot produces balanced partitions, the recurrence is approximately 2T(n/2) + Θ(n), giving Θ(n log n). If each partition has sizes 0 and n − 1, the recurrence becomes T(n − 1) + Θ(n), giving Θ(n²).

Randomized pivot selection or a robust pivot strategy reduces the likelihood of consistently poor partitions, but does not change the fact that the worst-case bound is quadratic for standard quicksort. Quicksort usually has low auxiliary memory requirements and excellent cache behavior, which can make it faster than merge sort in practice.

3.3 Choosing divide-and-conquer

Divide-and-conquer is suitable when subproblems are largely independent and can be combined efficiently. It is less suitable when many recursive calls solve the same subproblem. In that situation, dynamic programming or memoization may remove repeated work.

4. Greedy Algorithms

A greedy algorithm constructs a solution step by step, making the locally best admissible choice at each stage. Once a choice is made, it is normally not reconsidered. Greedy methods are efficient, but local optimality does not automatically imply global optimality.

Two properties commonly support a greedy proof:

• Greedy-choice property: some globally optimal solution begins with a locally optimal choice.
• Optimal substructure: after that choice, the remaining part of an optimal solution is itself optimal for the reduced problem.

4.1 Activity selection

Suppose each activity has a start and finish time, and the objective is to select the largest set of mutually compatible activities. Sort activities by increasing finish time. Repeatedly select the next activity whose start time is at least the finish time of the last selected activity.

The algorithm runs in O(n log n) time because of sorting and O(n) time after sorting. Its correctness follows from an exchange argument: among all activities compatible with the beginning of an optimal schedule, choosing the one that finishes earliest cannot reduce the maximum number of activities that can follow it.

4.2 Fractional knapsack

In fractional knapsack, an item may be divided. If item i has value vᵢ and weight wᵢ, its value density is vᵢ/wᵢ. Selecting items in non-increasing density order is optimal. This is not true for the 0/1 knapsack problem, where an item must be taken whole or not at all.

This distinction is a central design lesson: a small change in problem constraints can invalidate a previously correct paradigm.

4.3 Minimum spanning trees

Kruskal’s and Prim’s algorithms are greedy algorithms for finding a minimum spanning tree of a connected, weighted, undirected graph. Kruskal repeatedly chooses the lightest edge that does not create a cycle, commonly using a disjoint-set data structure. Prim grows one tree by repeatedly adding the lightest edge leaving the current tree.

Greedy algorithms are attractive because they are usually fast and memory-efficient. However, a proposed greedy rule must be justified by a proof, not merely by successful examples.

5. Dynamic Programming

Dynamic programming (DP) solves optimization, counting, or decision problems by storing solutions to smaller subproblems and reusing them. Two characteristics are especially important:

• Optimal substructure: an optimal solution can be composed from optimal solutions to subproblems.
• Overlapping subproblems: the recursive formulation solves the same subproblems repeatedly.

Optimal substructure alone is not enough to require DP. Merge sort has independent subproblems and a form of compositional structure, but its subproblems do not overlap; ordinary divide-and-conquer is adequate.

5.1 The 0/1 knapsack problem

Given n items, item i has value vᵢ and weight wᵢ, and the capacity is W. The goal is to maximize total value without exceeding W. Define V(i, c) as the maximum value obtainable using the first i items with capacity c. The recurrence is:

when wᵢ ≤ c. If wᵢ > c, item i cannot be selected, so V(i, c) = V(i − 1, c). Base cases are V(0, c) = 0 and V(i, 0) = 0. The standard table has O(nW) time and O(nW) space. With careful iteration, only the previous row is required, reducing auxiliary space to O(W), although reconstructing the chosen items then requires additional information or a second pass.

The pseudo-polynomial complexity is important: O(nW) is polynomial in the numerical capacity W, but W may be exponentially large relative to the number of bits needed to represent W.

5.2 Longest common subsequence

For sequences X and Y, the longest common subsequence (LCS) is the longest sequence appearing in both without requiring contiguous positions. Let L(i, j) be the LCS length of the prefixes X[1..i] and Y[1..j]. If the final characters match, they contribute one:

Otherwise:

The table requires O(|X||Y|) time and space in the straightforward implementation. LCS is used in file comparison, version control, text analysis, and bioinformatics, although specialized applications may use more efficient algorithms.

6. Memoization and Tabulation

Memoization is a top-down technique. A recursive function computes a subproblem only once and stores its result in a map or array. Tabulation is a bottom-up technique. It fills a table in an order that ensures every required smaller result is already available.

Consider Fibonacci numbers defined by F(0) = 0, F(1) = 1, and F(n) = F(n − 1) + F(n − 2). Naive recursion takes exponential time because it recomputes the same values. Memoization reduces the time to Θ(n), while tabulation also takes Θ(n) time and can use Θ(1) space when only the previous two values are needed.

Python memoization:

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Python also provides functools.lru_cache. In Java, memoization can use an array, HashMap<Integer, Long>, or another appropriate cache. Recursion depth, integer overflow, cache lifetime, and thread safety must be considered.

Memoization is preferable when only a small portion of the state space is reached or when the recurrence is naturally expressed recursively. Tabulation is preferable when all states are needed, predictable memory access matters, or recursion depth may be unsafe.

7. Branch-and-Bound

Branch-and-bound is an exact search technique for optimization problems. It explores a state-space tree, but uses bounds to discard a partial solution when it cannot improve the best complete solution found so far.

Each node represents a partial decision. Branching generates possible extensions. A bound estimates the best result achievable below that node. For a maximization problem, if the upper bound is no greater than the current best value, the node can be pruned. For minimization, a lower bound no better than the current best permits pruning.

The method is exact provided that the bound is valid. A bound that is too weak remains correct but prunes little. A bound that is incorrectly optimistic or pessimistic in the wrong direction can cause an incorrect answer.

Branch-and-bound does not generally guarantee polynomial time. Its practical performance depends on:

• the quality of the bound;
• the order in which nodes are explored;
• the initial incumbent solution;
• the size and structure of the search space; and
• the problem instance.

A priority queue can implement best-first branch-and-bound, exploring the most promising node first. Depth-first search uses less memory and may find a good incumbent early.

8. Worked Comparison: The Knapsack Family

Consider three items with values and weights (60, 10), (100, 20), and (120, 30), and capacity 50.

For fractional knapsack, densities are 6, 5, and 4. Select the first two items and 20 units of the third item. The total value is:

For 0/1 knapsack, the third item cannot be divided. Selecting items 2 and 3 gives weight 50 and value 220; selecting items 1 and 2 gives value 160; all three exceed capacity. Thus the optimum is 220. The greedy density rule, if applied without modification, would choose items 1 and 2 and fail to find the 0/1 optimum.

This example demonstrates why paradigm selection depends on the precise problem definition. Fractional knapsack has a greedy solution; 0/1 knapsack is naturally solved using dynamic programming or branch-and-bound.

9. Applied Case: Delivery Planning for a Small Courier

The following is an illustrative case.

Background

A courier must deliver packages to several locations. Travel times are known, vehicles have capacity limits, and customers have delivery time windows. The company wants a practical route that is short, feasible, and generated quickly each morning.

Problem analysis

A brute-force method could enumerate all delivery orders, but with n destinations there may be n! routes. This becomes unusable even for moderate n. The problem also contains several constraints, so a route that is short but violates a time window is unacceptable.

Proposed solution

The system first uses a greedy insertion heuristic to create a feasible initial route. It then applies branch-and-bound to search for an improved route. The current greedy route supplies an incumbent solution, while a lower bound based on minimum possible connection costs allows poor partial routes to be pruned. For repeated daily planning, dynamic programming may be suitable for smaller subproblems, such as calculating optimal travel between a restricted set of locations.

If the organization requires a guaranteed optimum for a small number of stops, complete branch-and-bound is appropriate. If hundreds of stops must be planned within seconds, a heuristic or hybrid method is more realistic, and the system should report that the result is feasible or near-optimal rather than claiming optimality without evidence.

Outcome and learning points

The case illustrates that professional algorithm design is a trade-off. Greedy construction supplies speed and a good incumbent; branch-and-bound supplies exact improvement when the instance permits it; dynamic programming may solve recurring subproblems. Requirements, not labels, determine the appropriate combination.

10. Selecting and Evaluating a Paradigm

A sound justification should state the problem structure, correctness rationale, expected complexity, memory cost, and implementation risks. Benchmarking should use representative inputs, include worst-case patterns, and distinguish algorithmic time from input parsing, allocation, and I/O.

11. Implementation Practices in Java and Python

Use clear representations of states. In Python, dictionaries are convenient for sparse memoization, while lists provide faster indexed access for dense tables. In Java, arrays are efficient for dense numeric states, and HashMap is appropriate when state keys are sparse or composite.

Avoid accidental copying. Python slicing, list concatenation, and immutable string construction may create hidden costs. In Java, repeated object creation, boxing, and poorly sized collections can similarly affect performance.

Use sufficiently wide numeric types. Java int overflow is silent, so values, costs, and path lengths may require long. Python integers grow automatically, but very large values still consume time and memory. Validate assumptions such as sorted input, nonnegative weights, graph connectivity, and legal capacities.

Test both correctness and complexity. Include empty inputs, one-element inputs, duplicate values, boundary capacities, already sorted and reverse-sorted data, and cases designed to trigger worst behavior. For optimization algorithms, compare against brute force on small instances; this creates a practical test oracle.

12. Limitations, Ethics, and Contemporary Practice

Algorithmic efficiency does not guarantee socially desirable outcomes. A route optimizer may reduce cost while producing unfair workloads. A scheduling system may systematically disadvantage a group if its objective function or data reflect historical bias. Developers should document objectives, constraints, data sources, and known failure modes.

In safety-sensitive applications, a heuristic must not be presented as an exact algorithm. Reproducible seeds for randomized methods, version-controlled code, recorded benchmarks, and independent tests improve auditability. Privacy should be preserved when input data contain personal information.

Contemporary software commonly combines paradigms. Parallel merge sort uses divide-and-conquer; modern compilers use dynamic programming for optimization decisions; artificial-intelligence systems use search, heuristics, and memoized state evaluation. Machine-learning tools may help estimate bounds or guide search order, but they do not replace proof when exact correctness is required.

Chapter Summary

Algorithm design paradigms provide reusable ways to construct efficient and understandable solutions. Brute force is simple and valuable as a baseline, but may suffer combinatorial growth. Decrease-and-conquer reduces one instance to a smaller instance, as in insertion sort and binary search. Divide-and-conquer solves independent subproblems and combines their results, as in merge sort.

Greedy algorithms make locally attractive choices and require a proof that those choices can lead to a global optimum. Dynamic programming applies when optimal substructure and overlapping subproblems permit stored subproblem results. Memoization is a top-down implementation technique, while tabulation is bottom-up. Branch-and-bound performs exact optimization search while pruning states that cannot improve the incumbent solution.

Paradigm selection must follow the problem’s constraints and structure. The 0/1 and fractional knapsack comparison shows that a small change in admissible decisions can change the correct paradigm. In professional practice, hybrid algorithms, careful complexity analysis, testing, documentation, and honest communication of optimality are as important as the core algorithm.

Key Terms

Algorithm design paradigm: A general strategy for constructing algorithms.

Brute force: Systematic enumeration or direct processing of candidate solutions.

Decrease-and-conquer: Solving one smaller instance and extending its solution.

Divide-and-conquer: Dividing a problem into independent smaller subproblems and combining results.

Recurrence: An equation defining running time or another quantity in terms of smaller instances.

Greedy-choice property: The existence of an optimal solution beginning with a locally best admissible choice.

Optimal substructure: The property that optimal solutions contain optimal solutions to subproblems.

Overlapping subproblems: Repeated occurrence of the same smaller problem.

Dynamic programming: Solving and storing subproblems to avoid repeated computation.

Memoization: Top-down caching of recursive results.

Tabulation: Bottom-up computation of a dynamic-programming table.

State: A precise description of a subproblem and its relevant parameters.

Branch-and-bound: Exact search using bounds to prune unpromising partial solutions.

Incumbent: The best complete solution currently known during search.

Bound: An estimate limiting the best possible solution below a search node.

Pseudo-polynomial: Polynomial in a numeric value rather than in its encoded input length.

Exchange argument: A proof technique showing that a local choice can replace part of an optimum without worsening it.

Stable sorting: Sorting that preserves the relative order of equal-key elements.

Heuristic: A practical method that may produce good solutions without guaranteeing optimality.

Review Questions

Short Answer Questions

1. What is the principal difference between decrease-and-conquer and divide-and-conquer?
2. Define optimal substructure and overlapping subproblems.
3. Why is binary search not valid on an unsorted array?
4. What is the purpose of an incumbent solution in branch-and-bound?
5. Distinguish memoization from tabulation.

Long Answer Questions

1. Explain merge sort, derive its recurrence, and discuss its time and space complexity.
2. Explain the greedy-choice property using activity selection as an example.
3. Describe the dynamic-programming formulation of 0/1 knapsack and explain its pseudo-polynomial complexity.
4. Compare brute force, dynamic programming, and branch-and-bound for an optimization problem.
5. Discuss implementation considerations that may cause Java and Python programs with the same asymptotic complexity to perform differently.

Analytical / Application Questions

1. A proposed algorithm chooses the item with the greatest value-to-weight ratio for 0/1 knapsack. Construct a counterexample and explain why the greedy rule fails.
2. Design a branch-and-bound strategy for a small route-planning problem. Specify a valid bound, branching rule, and pruning condition.
3. Given a recursive problem whose state is described by two indices and whose calls repeatedly revisit the same index pairs, justify whether memoization, tabulation, or divide-and-conquer is most appropriate.

Multiple Choice Questions with Answers

Question 1

Which property specifically indicates that the same subproblems are solved repeatedly?

A. Optimal substructure

B. Overlapping subproblems

C. Stable ordering

D. Randomized partitioning

Correct Answer: B. Overlapping subproblems

Question 2

What is the worst-case time complexity of binary search on a sorted array?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 3

Which algorithm is a decrease-by-one algorithm?

A. Merge sort

B. Insertion sort

C. Kruskal’s algorithm

D. Fractional knapsack

Correct Answer: B. Insertion sort

Question 4

What is the usual worst-case time complexity of merge sort?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 5

The density rule is guaranteed to solve which problem optimally?

A. 0/1 knapsack

B. Fractional knapsack

C. LCS

D. Unweighted graph coloring

Correct Answer: B. Fractional knapsack

Question 6

What does memoization do?

A. Sorts states before processing them

B. Caches results of solved subproblems

C. Removes all recursion

D. Guarantees constant time

Correct Answer: B. Caches results of solved subproblems

Question 7

In a maximization branch-and-bound algorithm, when can a node be pruned?

A. When its upper bound is no greater than the incumbent value

B. Whenever it has two children

C. When its depth is odd

D. Only when it is a leaf

Correct Answer: A. When its upper bound is no greater than the incumbent value

Question 8

For 0/1 knapsack with n items and capacity W, the standard dynamic-programming time complexity is:

A. O(log(nW))

B. O(n + W)

C. O(nW)

D. O(2ⁿW²)

Correct Answer: C. O(nW)

Question 9

Which condition is essential for ordinary binary search?

A. The array must contain distinct values

B. The array must be sorted

C. The array must have even length

D. The array must be stored in a linked list

Correct Answer: B. The array must be sorted

Question 10

What is the main risk of applying a greedy rule without a proof?

A. The algorithm cannot use memory

B. A locally best choice may prevent a globally optimal solution

C. The input must always be randomized

D. The algorithm necessarily becomes recursive

Correct Answer: B. A locally best choice may prevent a globally optimal solution