Algorithm Design Paradigms

Introduction

An algorithm design paradigm is a general way of organizing the reasoning used to construct an algorithm. Rather than memorizing isolated procedures, developers learn to recognize structural properties of a problem and select a suitable strategy. This chapter examines five major paradigms: divide-and-conquer, greedy algorithms, dynamic programming, backtracking, and branch-and-bound.

These paradigms are particularly important in full-stack development. Search, scheduling, routing, caching, recommendation, data validation, resource allocation, and database query processing all involve algorithmic design choices. A correct solution must address not only functional correctness but also time complexity, memory usage, scalability, and the possibility that an apparently efficient heuristic may fail to produce an optimal result.

Learning Objectives

By the end of this chapter, you should be able to:

• explain the structure and recurrence relations of major design paradigms;
• identify optimal substructure and overlapping subproblems;
• formulate divide-and-conquer, greedy, dynamic-programming, backtracking, and branch-and-bound solutions;
• distinguish exact algorithms from heuristics and approximation strategies;
• analyze time and space complexity;
• apply the paradigms to representative optimization and decision problems;
• select an appropriate approach for a practical software problem.

1. A Framework for Algorithm Design

A design process normally has five stages:

1. Precisely define the input, output, constraints, and objective.
2. Identify exploitable structure in the problem.
3. Select a paradigm and state its assumptions.
4. Prove correctness, usually through induction, an exchange argument, or exhaustive-state reasoning.
5. Analyze time and space complexity and evaluate implementation trade-offs.

Two structural properties are especially important.

Optimal substructure

A problem has optimal substructure when an optimal solution can be constructed from optimal solutions to appropriate subproblems. For example, if a shortest path from source s to destination v passes through u, then the portion from s to u must itself be a shortest path, assuming the path model permits replacement without violating constraints.

Optimal substructure is necessary for many dynamic-programming and greedy solutions, but it is not sufficient by itself. The algorithm must also combine subproblem solutions correctly, and a greedy algorithm additionally requires a proof that a locally safe choice can occur in some global optimum.

Overlapping subproblems

Subproblems overlap when the same subproblem is solved repeatedly by a naïve recursive algorithm. Dynamic programming stores each result once, using either memoization (top-down) or tabulation (bottom-up).

If there are m states and each state requires at most r work after its dependencies are available, the dynamic-programming cost is commonly O(mr), although the exact bound depends on state representation and transition computation.

2. Divide-and-Conquer

Divide-and-conquer divides an instance into smaller independent instances, solves them recursively, and combines their results. Its three stages are:

• Divide: partition the input.
• Conquer: solve each part recursively.
• Combine: merge the partial results.

A common recurrence is:

Here, n is input size, a is the number of subproblems, each of size approximately n/b, and f(n) is the nonrecursive divide-and-combine work. This recurrence applies when subproblem sizes and costs have the stated regular form; otherwise, a more specific analysis is required.

Merge sort

Merge sort divides an array into two halves, recursively sorts each half, and merges the sorted halves in linear time:

Therefore, T(n) = Θ(n log n). Its auxiliary space is Θ(n) for the usual merge implementation. Merge sort is stable, which is useful when records have a secondary ordering, but it generally requires more memory than in-place comparison sorts.

Quicksort

Quicksort partitions an array around a pivot. If the pivot produces subarrays of sizes k and n−k−1, the recurrence is:

Balanced partitions produce Θ(n log n) expected or best-case time. Repeatedly choosing an extreme pivot produces Θ(n²) time. Randomized pivot selection reduces the likelihood of consistently poor partitions but does not eliminate the worst-case theoretical bound. Quicksort is often attractive because partitioning can be performed in place and has good cache behavior.

Closest pair of points

For points in a plane, a divide-and-conquer algorithm sorts points by coordinates, divides them into two halves, recursively finds the closest pair in each half, and checks a narrow strip around the dividing line. With suitable presorting and strip processing, the running time is O(n log n), compared with Θ(n²) for checking every pair.

3. Greedy Algorithms

A greedy algorithm constructs a solution incrementally, making the locally best feasible choice at each step. Greedy algorithms are usually fast, but local improvement alone does not prove global optimality.

A correct greedy method typically requires:

• optimal substructure; and
• the greedy-choice property: some optimal solution begins with the greedy choice.

The greedy-choice property is commonly proved by an exchange argument. One shows that any optimal solution can be transformed to include the greedy choice without making it worse.

Activity selection

Given activities with start and finish times, the goal is to select the maximum number of mutually compatible activities. The correct greedy rule is to repeatedly choose the compatible activity with the earliest finish time.

Suppose the activities are (1,3), (2,5), (4,7), (6,8), and (8,10). Choosing (1,3), (4,7), and (8,10) yields three activities. Choosing by earliest start time or shortest duration does not generally guarantee the maximum count.

The exchange argument is as follows. Let a be the activity with earliest finish time. In any optimal solution, replace its first selected activity with a if necessary. Since a finishes no later, the remaining activities remain compatible. The problem then reduces to selecting the maximum number of activities beginning after a finishes.

Fractional knapsack

In fractional knapsack, an item may be divided. For item i with value vᵢ and weight wᵢ, define density dᵢ = vᵢ/wᵢ. Sorting by decreasing density and taking as much as possible is optimal. The divisibility assumption is essential.

This rule does not solve 0/1 knapsack, in which each item must be taken completely or not at all. For example, let capacity be 10 and items be:

A density-first 0/1 choice takes B, leaving capacity 5 and then takes C, obtaining value 52; this happens to be optimal. To demonstrate failure, use instead capacity 10 and items A=(6,30), B=(5,26), C=(5,25). Density-greedy selects B first and then C, obtaining 51, while A alone has value 30, so this still does not fail. A valid failure example is capacity 10 with A=(10,60), B=(6,36), C=(4,23): densities are 6, 6, and 5.75. If ties are resolved by choosing B first, the result is 59, while A gives 60. Thus density is not a proof of optimality for 0/1 knapsack. Tie handling is part of the specified algorithm, and the example illustrates that even a density-leading item can block a better complete item.

Minimum spanning trees

For a connected, weighted, undirected graph, Kruskal’s algorithm sorts edges by nondecreasing weight and adds an edge when it does not create a cycle. A disjoint-set data structure makes cycle testing efficient. Prim’s algorithm grows one tree from a starting vertex by repeatedly adding the cheapest edge crossing from the current tree to an unvisited vertex. Both are greedy and produce a minimum spanning tree under the usual graph assumptions.

4. Dynamic Programming

Dynamic programming is appropriate when a problem has optimal substructure and overlapping subproblems. The central design task is to define a state that contains enough information to determine future decisions but not unnecessary history.

A sound formulation specifies:

• state meaning;
• base cases;
• transition equation;
• evaluation order;
• reconstruction method, if the actual choices are required.

0/1 knapsack

Let V[i,w] be the maximum value obtainable using the first i items with integer capacity w. Item i has weight wᵢ and value vᵢ. The recurrence is:

The base cases are V[0,w] = 0 for every w ≥ 0 and V[i,0] = 0 for every i. A table implementation takes O(nW) time and O(nW) space, where n is the number of items and W is capacity. A one-dimensional implementation reduces space to O(W), provided capacities are processed in descending order so that an item is not reused in the same iteration.

For items (weight, value) = (2,12), (1,10), and (3,20), with capacity 3, the best solution is the first and second items, value 22. The first and third items weigh 5 and are infeasible; the second and third weigh 4 and are also infeasible.

Bellman–Ford and bounded-edge shortest paths

Bellman–Ford handles directed graphs that may contain negative edge weights, provided no reachable negative-weight cycle is relevant to the requested shortest path. To make the state precise, let d_k(v) denote the minimum cost of a path from source s to vertex v using at most k edges. Initialize:

and d₀(v) = +∞ for every v ≠ s, where +∞ is a sentinel meaning that no path within the stated edge bound is known. For k ≥ 1:

The first term is essential: it allows a path using fewer than k edges to remain optimal. An unreachable predecessor with value +∞ contributes nothing useful; implementations must avoid arithmetic overflow when adding a finite edge weight to an infinity sentinel.

After |V|−1 iterations, d_{|V|−1}(v) gives shortest simple-path distances when no reachable negative cycle exists. A further relaxation that improves a reachable distance indicates a reachable negative cycle. The standard time complexity is O(|V||E|), and the space complexity is O(|V|) when only the preceding distance array is retained.

If instead a state is defined for exactly k edges, the recurrence is different: it uses only d_{k−1}(u)+w(u,v), and initialization must represent exact-edge paths. Mixing the “exactly” and “at most” definitions is a common source of errors.

Longest common subsequence

For sequences X and Y, let L[i,j] be the length of a longest common subsequence of prefixes X[1..i] and Y[1..j]. If the final characters match, they can be included; otherwise one of them must be omitted:

With L[0,j] = L[i,0] = 0, the table takes O(mn) time and space for sequence lengths m and n. LCS is used in version comparison, file-difference tools, and bioinformatics, although specialized algorithms may be preferable for very large inputs.

5. Backtracking

Backtracking searches a space of partial solutions. It extends a partial candidate, checks whether the candidate can still lead to a feasible complete solution, and abandons it when it cannot. The method is exact but may have exponential worst-case complexity.

A generic recursive structure is:

search(partial):
    if partial is complete:
        record or evaluate it
    else:
        for each legal choice:
            apply choice
            if promising(partial):
                search(partial)
            undo choice

N-queens

The N-queens problem places N queens on an N×N board so that no two share a row, column, or diagonal. A row-by-row backtracking algorithm tries each column in the current row and rejects a placement if its column or either diagonal is occupied. State can be represented by occupied-column and diagonal sets, enabling constant-time conflict tests. The search remains exponential in the worst case, but pruning makes it practical for considerably larger N than naïve permutation enumeration.

Subset sum

Given nonnegative integers and a target T, backtracking branches on including or excluding each item. If the current sum exceeds T, the branch can be pruned. For nonnegative values sorted in descending order, an additional bound based on the remaining possible sum can improve practical performance. Such pruning is valid only when its assumptions hold; negative numbers would invalidate the simple “current sum exceeds target” rule.

6. Branch-and-Bound

Branch-and-bound is an exact optimization technique. It branches into subproblems and computes an optimistic bound on the best solution possible in each subproblem. A maximization node can be discarded when its upper bound is no greater than the best complete solution already found. For minimization, a node is discarded when its lower bound is no smaller than the incumbent.

Backtracking primarily prunes infeasible partial solutions. Branch-and-bound prunes solutions that cannot improve the current objective, even when they remain feasible. The two ideas can be combined.

Travelling salesperson problem

For a complete weighted graph, the travelling salesperson problem seeks a minimum-cost tour visiting each city once and returning to the start. A branch-and-bound algorithm fixes successive city choices. A lower bound may be obtained from the cost already accumulated plus a minimum possible connection estimate for unvisited cities. The bound must never overestimate the cost of a completion; otherwise, a genuinely optimal branch could be incorrectly discarded.

Worst-case complexity remains exponential, but strong bounds, good initial tours, and effective branching orders can substantially reduce explored nodes.

7. Comparative Analysis

Paradigm selection should follow the problem structure, not fashion. A shortest-path problem with negative edges suggests Bellman–Ford, while a problem with small integer capacity may suit knapsack dynamic programming. A large problem with no known polynomial exact algorithm may require approximation, heuristics, or domain-specific constraints.

8. Applied Case: Delivery Planning for a Web Retailer

Background

This illustrative case concerns a web retailer that must plan deliveries from a depot to several customers. The service needs a route that visits each customer once and returns to the depot while minimizing distance.

Problem

The exact problem is a travelling salesperson problem. Brute-force enumeration considers approximately (n−1)! tours when the depot is fixed, which becomes impractical quickly.

Analysis

The company first constructs a feasible tour using a nearest-neighbour heuristic. This gives an incumbent upper bound for a minimization branch-and-bound search. The exact search then branches on the next customer and computes a lower bound using the current route cost plus inexpensive minimum connection estimates. Any branch whose lower bound is at least the incumbent is discarded.

For a small number of customers, the company can verify the optimum with branch-and-bound. For thousands of customers, it may use clustering, local search, integer programming, or approximation methods, because worst-case exponential search is unsuitable for real-time operation.

Outcome

The hybrid strategy provides an exact answer for small regional instances and a high-quality practical route for large instances. The incumbent tour is valuable even before the exact search finishes, while the lower bound provides a defensible stopping criterion when a time limit is imposed.

Learning points

• A fast feasible solution can improve exact search.
• Bounds must be mathematically safe, not merely plausible.
• A production system should expose whether a result is exact, approximate, or time-limited.
• Operational constraints such as delivery windows may require richer states and can change the appropriate algorithmic model.

9. Engineering, Ethical, and Contemporary Considerations

Algorithmic efficiency affects cloud cost, battery use, latency, and carbon emissions. A theoretically efficient method may perform poorly if it causes excessive memory allocation or has poor cache locality. Profiling on representative workloads is therefore essential.

Optimization objectives can also encode unfairness. A scheduling algorithm that minimizes distance may systematically assign inconvenient shifts to a particular group if fairness constraints are omitted. A recommendation or routing system should document objectives, constraints, data limitations, and fallback behavior.

AI-assisted programming tools can suggest implementations of dynamic programming or search algorithms, but generated code must be tested against boundary cases: empty inputs, zero capacity, unreachable vertices, negative edges, repeated values, and disconnected graphs. Formal reasoning remains the developer’s responsibility.

Best practice includes stating the problem model explicitly, proving or testing the pruning rule, using safe numeric sentinels, measuring actual performance, and distinguishing worst-case guarantees from empirical behavior.

Chapter Summary

Algorithm design paradigms provide reusable strategies for constructing solutions. Divide-and-conquer recursively solves independent subproblems and analyzes their cost through recurrences. Greedy algorithms make locally attractive choices, but optimality requires a greedy-choice proof in addition to optimal substructure. Dynamic programming stores overlapping subproblem results and requires precise states, base cases, and transitions. Bellman–Ford illustrates the importance of defining whether a state refers to exactly or at most a given number of edges; for “at most,” the recurrence must retain the previous state. Backtracking explores feasible partial solutions and prunes impossible branches, whereas branch-and-bound prunes optimization branches that cannot improve a known incumbent. In practice, paradigm choice depends on correctness requirements, input constraints, complexity, memory, and whether an exact result is necessary.

Key Terms

Algorithm design paradigm: A general strategy for constructing algorithms.

Divide-and-conquer: Solving smaller independent instances and combining their results.

Recurrence: An equation defining a problem’s cost in terms of smaller instances.

Greedy algorithm: An algorithm that repeatedly makes a locally preferred feasible choice.

Exchange argument: A proof that replaces part of an optimal solution with a chosen element without worsening it.

Optimal substructure: The property that an optimal solution contains optimal solutions to subproblems.

Overlapping subproblems: Repeated occurrence of identical subproblems.

Memoization: Top-down storage of previously computed results.

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

State: A compact representation of information needed to solve a subproblem.

Transition: A rule deriving a state from smaller or earlier states.

0/1 knapsack: A selection problem in which each item is either fully selected or rejected.

Fractional knapsack: A selection problem allowing fractions of items.

Backtracking: Systematic search that abandons nonpromising partial solutions.

Branch-and-bound: Exact optimization search using valid objective bounds for pruning.

Incumbent: The best complete solution currently known.

Upper bound: For maximization, a value no smaller than any completion’s possible value.

Lower bound: For minimization, a value no greater than any completion’s possible cost.

Negative cycle: A cycle whose total edge weight is negative.

Heuristic: A practical method that may lack an optimality guarantee.

Review Questions

Short Answer Questions

1. What are the divide, conquer, and combine stages of divide-and-conquer?
2. Why does a greedy-choice property require proof rather than assumption?
3. Distinguish memoization from tabulation.
4. What does +∞ represent in Bellman–Ford initialization?
5. How does branch-and-bound differ from ordinary backtracking?

Long Answer Questions

1. Derive the merge-sort recurrence and explain why its solution is Θ(n log n).
2. Explain the exchange argument for the earliest-finish-time activity-selection algorithm.
3. Define the 0/1-knapsack dynamic-programming state, base cases, recurrence, and complexity.
4. Explain why density ordering is optimal for fractional knapsack but not generally for 0/1 knapsack.
5. Compare backtracking and branch-and-bound using the travelling salesperson problem.

Analytical / Application Questions

1. Design a Bellman–Ford table for a graph containing a negative edge but no reachable negative cycle. State the initialization, unreachable convention, and update rule.
2. A scheduling system must maximize the number of non-overlapping jobs. Explain which greedy rule you would test, how you would prove it, and why two plausible alternative rules may fail.
3. A route-planning service must choose between exact branch-and-bound and a heuristic for 500 locations. Analyze the trade-off using solution guarantees, time limits, bounds, and operational consequences.

Multiple Choice Questions with Answers

Question 1

Which property means that an optimal solution contains optimal solutions to its subproblems?

A. Optimal substructure

B. Randomization

C. Hash consistency

D. Amortized allocation

Correct Answer: A. Optimal substructure

Question 2

What is the worst-case running time of merge sort on n elements?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n² log n)

Correct Answer: C. Θ(n log n)

Question 3

Which rule gives an optimal solution for the fractional knapsack problem?

A. Choose the lightest item first

B. Choose items by decreasing value density

C. Choose items by increasing value

D. Choose the item with the latest input position

Correct Answer: B. Choose items by decreasing value density

Question 4

For Bellman–Ford defined with d_k(v) as the shortest distance using at most k edges, which term must appear in the recurrence?

A. d_{k−1}(v)

B. d_{k+1}(v)

C. d_0(u) for every predecessor only

D. The maximum edge weight

Correct Answer: A. d_{k−1}(v)

Question 5

What is the standard time complexity of the table-based 0/1-knapsack algorithm with n items and integer capacity W?

A. O(n + W)

B. O(log(nW))

C. O(nW)

D. O(2^W)

Correct Answer: C. O(nW)

Question 6

In backtracking, a partial solution is normally pruned when it is:

A. Feasible and potentially optimal

B. Unable to lead to a feasible complete solution

C. The first solution found

D. Stored in a hash table

Correct Answer: B. Unable to lead to a feasible complete solution

Question 7

For a minimization branch-and-bound problem, a node can be discarded when its valid lower bound is:

A. Less than the incumbent cost

B. Equal to zero only

C. At least the incumbent cost

D. Based on an infeasible estimate

Correct Answer: C. At least the incumbent cost

Question 8

If each divide-and-conquer level performs Θ(n) total combine work and there are Θ(log n) levels, what is the total combine contribution?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: D. Θ(n log n)

Question 9

What does +∞ conventionally indicate for an unreachable vertex in a shortest-path dynamic-programming table?

A. The vertex has distance zero

B. No path within the considered state has been found

C. The vertex has a negative cycle

D. The edge weights must be positive

Correct Answer: B. No path within the considered state has been found

Question 10

Which statement about 0/1 knapsack is correct?

A. Density ordering always proves an optimal solution

B. Items may be divided freely

C. Dynamic programming can solve it in O(nW) time for integer capacity W

D. It has no overlapping subproblems

Correct Answer: C. Dynamic programming can solve it in O(nW) time for integer capacity W