Algorithm Design Paradigms

Introduction

An algorithm is not merely a sequence of instructions; it is a structured method for transforming inputs into outputs while satisfying correctness, resource, and implementation requirements. Algorithm design paradigms are reusable patterns for constructing such methods. They help a designer recognize the structure of a problem, select an appropriate strategy, and justify why the resulting algorithm works.

This chapter examines eight central paradigms: divide-and-conquer, decrease-and-conquer, greedy algorithms, dynamic programming, memoization, backtracking, branch-and-bound, and state-space search. These paradigms are not mutually exclusive. For example, a branch-and-bound algorithm may use a best-first search policy, dynamic programming may be implemented through memoization, and a divide-and-conquer algorithm may be combined with greedy decisions.

At postgraduate level, algorithm design requires more than knowing standard procedures. A designer must identify assumptions, formulate recurrences or state representations, prove correctness, estimate complexity, understand failure conditions, and evaluate practical trade-offs such as memory locality, parallelism, approximation, and scalability.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Recognize the structural conditions that support major algorithm design paradigms.
2. Formulate and solve recurrence relations for divide-and-conquer algorithms.
3. Distinguish decrease-and-conquer from divide-and-conquer.
4. Design and justify greedy algorithms using exchange arguments.
5. Formulate dynamic-programming states, recurrences, and evaluation orders.
6. Explain memoization as a demand-driven form of dynamic programming.
7. Construct backtracking, branch-and-bound, and state-space search procedures.
8. Prove algorithm correctness using induction, invariants, exchange arguments, and optimal-substructure reasoning.
9. Select paradigms critically for practical and large-scale computing problems.

1. From Problem Structure to Design Strategy

A design paradigm is a general problem-solving pattern. The choice of paradigm depends on the structure of the problem rather than on superficial similarity to a familiar algorithm.

Important questions include:

• Can the problem be separated into independent subproblems?
• Does solving a smaller instance directly lead to a larger instance?
• Can a locally optimal decision be shown to preserve global optimality?
• Do subproblems overlap substantially?
• Is the goal to find one feasible solution, all feasible solutions, or an optimal solution?
• Can partial solutions be rejected using a bound or constraint?
• Is the search space explicit, implicit, finite, or potentially infinite?

A sound design normally proceeds through four activities:

1. Model the problem. Define inputs, outputs, constraints, and objective function.
2. Expose structure. Identify decomposition, monotonicity, optimal substructure, or constraints.
3. Construct the algorithm. Specify states, transitions, decisions, and termination.
4. Validate the design. Prove correctness and analyze time and space complexity.

Correctness and efficiency are separate properties. An algorithm can be correct but impractical, or fast on typical inputs but incorrect on a valid boundary case.

2. Divide-and-Conquer

2.1 Principle

Divide-and-conquer solves a problem by:

1. Dividing an instance into smaller instances.
2. Solving the smaller instances recursively.
3. Combining their solutions.

The subproblems are usually independent, although they may have equal or unequal sizes. The base case is solved directly.

A typical running-time recurrence is:

Here, n is the input size, a is the number of recursive subproblems, n/b is the size of each subproblem, and f(n) is the division and combination cost. The recurrence assumes approximately equal subproblem sizes and a uniform cost model.

For unequal divisions, a more accurate recurrence is:

where each n_i is the size of a subproblem.

2.2 Master-theorem interpretation

For the recurrence T(n) = aT(n/b) + f(n), define p = log_b a. Under the regularity assumptions of the Master Theorem:

• If f(n) grows asymptotically slower than n^p, then T(n) = Θ(n^p);
• If f(n) = Θ(n^p log^k n), then T(n) = Θ(n^p log^k+1 n) for fixed k ≥ 0;
• If f(n) grows asymptotically faster than n^p and the regularity condition holds, then T(n) = Θ(f(n)).

These cases are not universal substitutions for a proof. The theorem does not directly apply to every recurrence, especially those with unequal subproblem sizes, non-polynomial ratios, or irregular recursive costs.

2.3 Example: merge sort

Merge sort divides an array of n elements into two halves, recursively sorts each half, and merges the sorted halves. The merge operation takes Θ(n) time, so:

Since a = 2, b = 2, and n^{log_b a} = n, the balanced case gives:

The algorithm uses Θ(n) auxiliary space for the merge operation, although implementation details affect stack and allocation behavior.

2.4 Correctness by induction

A standard proof for merge sort uses strong induction on n. The base case, an array of size zero or one, is already sorted. Assume recursively that both halves are sorted. The merge procedure repeatedly selects the smallest remaining element from the two sorted halves. At every selection, no unselected element can be smaller than the selected element; therefore the output remains sorted. When both halves are exhausted, every element appears exactly once in sorted order. Thus the algorithm is correct.

2.5 Strengths and limitations

Divide-and-conquer often provides logarithmic recursion depth, supports parallel execution, and yields clean correctness proofs. Its weaknesses include recursive overhead, additional memory for combining, and poor suitability when subproblems overlap heavily. Naïve recursive Fibonacci illustrates the latter problem: the same values are recomputed repeatedly, making dynamic programming more appropriate.

3. Decrease-and-Conquer

Decrease-and-conquer solves one smaller instance and extends its solution to the original instance. The reduction may be by one element, by a constant factor, or according to a variable amount.

3.1 Types

• Decrease by a constant: solve size n−1 and extend, as in insertion sort.
• Decrease by a constant factor: solve size n/2, as in binary search.
• Variable-size decrease: reduce by an amount determined by the input, as in Euclid’s algorithm.

Insertion sort is a decrease-by-one algorithm. After sorting the first i−1 elements, it inserts the ith element into its correct position. In the worst case, the total number of shifts is:

The equality assumes the worst-case reverse ordering and unit-cost comparisons or shifts. Insertion sort uses Θ(1) auxiliary space in its standard in-place form.

Binary search is decrease-by-a-factor algorithm. Each comparison discards approximately half the remaining interval, producing the recurrence:

Its precondition is that the searched sequence is sorted and that the indexing model permits constant-time access.

3.2 Distinction from divide-and-conquer

Divide-and-conquer creates multiple subproblems and combines their solutions. Decrease-and-conquer normally creates one smaller subproblem and extends its solution. The distinction is useful because it influences proof structure, stack depth, and opportunities for parallelism.

4. Greedy Algorithms

A greedy algorithm constructs a solution incrementally, making the locally best feasible choice according to a specified selection rule. It does not normally reconsider earlier decisions.

A greedy design is justified only when two properties are established:

1. Greedy-choice property: some globally optimal solution begins with the greedy choice.
2. Optimal substructure: after that choice, the remaining problem has an optimal solution that completes the partial solution.

4.1 Activity-selection example

Suppose activities have start time s_i and finish time f_i, and two activities are compatible when one starts no earlier than the other finishes. The goal is to select the maximum number of mutually compatible activities.

The correct greedy rule is to choose the compatible activity with the earliest finish time. After selecting it, discard activities that start before its finish and repeat.

The rule is not “choose the shortest activity” or “choose the activity with the earliest start.” Those alternatives can leave less room for future activities.

4.2 Exchange proof

Let g be an activity with the earliest finish time among all available activities, and let O be an optimal schedule whose first activity is o. Since f_g ≤ f_o, replacing o with g cannot make any later activity incompatible: every activity following o starts at or after f_o, and therefore also at or after f_g. The replacement preserves the number of selected activities. Thus there exists an optimal solution beginning with the greedy choice. Applying the same argument recursively to the remaining activities proves correctness.

This is an exchange argument: transform an arbitrary optimal solution into one containing the greedy choice without reducing its quality.

4.3 Fractional knapsack

In fractional knapsack, item portions may be selected. If item i has value v_i and weight w_i, its value density is:

Assuming weights and values are nonnegative and fractions are allowed, sorting by nonincreasing ρ_i is optimal. If a solution contains a lower-density portion while a higher-density item remains available, exchanging equal weights increases or preserves value. This exchange argument fails for 0–1 knapsack because indivisible items prevent arbitrary replacement.

4.4 Minimum spanning trees

Kruskal’s and Prim’s algorithms are greedy algorithms for minimum spanning trees of connected, undirected, weighted graphs. Kruskal repeatedly chooses the lightest edge that does not form a cycle. The cut property states that a minimum-weight edge crossing any cut is safe: it belongs to at least one minimum spanning tree. This property supplies the correctness basis.

Greedy methods are attractive because they are usually simple and efficient. However, local optimality alone is never a proof. A greedy rule must be connected to a structural theorem or a valid exchange argument.

5. Dynamic Programming and Memoization

Dynamic programming (DP) applies when a problem has:

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

DP stores subproblem results so that each relevant state is solved once.

5.1 Formulating a DP solution

A disciplined formulation identifies:

1. The state and its meaning.
2. The recurrence or transition rule.
3. Base cases.
4. Evaluation order or dependency order.
5. The final answer and reconstruction method, if required.

5.2 0–1 knapsack

Given items with weights w_i, values v_i, capacity W, and the restriction that each item is either selected or rejected, define DP[i][c] as the maximum value obtainable using the first i items and capacity c.

The second term is applicable only when w_i ≤ c. The first term excludes item i. Base cases are DP[0][c] = 0 and DP[i][0] = 0. The table has (n+1)(W+1) entries, giving time Θ(nW) and space Θ(nW) in the two-dimensional implementation. This is pseudo-polynomial, not polynomial in the bit-length of W, because W may be exponentially larger than its binary representation length.

A one-dimensional implementation updates capacities in descending order:

DP[0..W] ← 0
for each item i:
    for c from W down to w_i:
        DP[c] ← max(DP[c], DP[c − w_i] + v_i)

Descending order prevents the current item from being reused in the same iteration. Space becomes Θ(W), but reconstruction of the selected items requires additional information or a separate strategy.

5.3 Memoization versus tabulation

Memoization is top-down: a recursive procedure computes a state only when requested and caches the result. Tabulation is bottom-up: states are filled in an order that guarantees their dependencies are already available.

Memoization can be preferable when only a small fraction of the theoretical state space is reachable. Tabulation often has lower call overhead, predictable memory access, and easier iterative deployment. Both have the same conceptual recurrence and can have the same asymptotic complexity.

5.4 Correctness through optimal substructure

For 0–1 knapsack, consider an optimal solution for state (i,c). Either it excludes item i, in which case its value is at most DP[i−1][c], or it includes the item, leaving a solution for (i−1,c−w_i). If that remaining solution were not optimal, replacing it with a better one would improve the original solution, contradicting optimality. Therefore the recurrence considers all and only optimal alternatives.

6. Backtracking

Backtracking systematically explores a space of partial solutions and abandons a partial solution as soon as it violates a constraint. It is especially useful for constraint-satisfaction problems such as N-Queens, graph coloring, Sudoku, and exact subset selection.

A generic backtracking procedure is:

search(partial):
    if complete(partial):
        report partial
    else:
        for each candidate x allowed next:
            if consistent(partial, x):
                add x
                search(partial)
                remove x

The algorithm is complete if every possible candidate extension is eventually considered and pruning removes only inconsistent states.

For N-Queens, place one queen per row and reject a placement if another queen occupies the same column or diagonal. A column test can be represented by a Boolean array. Diagonal conflicts can be checked using row−column and row+column indices. These constant-time tests reduce repeated scanning, although worst-case time remains exponential because the search space is inherently large.

Backtracking differs from dynamic programming because it explores alternatives in a search tree rather than merging equivalent states automatically. Memoization can be added when different paths reach the same state, producing a hybrid of backtracking and DP.

7. Branch-and-Bound

Branch-and-bound is an optimization-oriented search technique. It branches on decisions, computes a bound on the best objective value achievable below each partial solution, and prunes a node when that bound cannot improve the incumbent solution.

For a maximization problem, let U(x) be an upper bound on any completion of partial solution x, and let B be the value of the best complete solution found so far. If:

then the subtree rooted at x can be safely discarded. For minimization, a lower bound is compared with the incumbent upper value.

The bound must be optimistic: for maximization it must never underestimate the best possible completion. A bound that is too weak produces little pruning; a bound that is incorrect can eliminate the optimum and invalidate the algorithm.

In 0–1 knapsack, a common upper bound fills the remaining capacity fractionally after sorting remaining items by value density. Because the fractional version permits more choices than the 0–1 version, its value is at least as large as the best integral completion, making it a valid upper bound. The method can be much faster than exhaustive enumeration, but its worst-case time remains exponential.

Search order matters operationally. Best-first branch-and-bound expands the live node with the strongest bound, often finding a high-quality incumbent early. Depth-first search uses less memory and may find a feasible incumbent quickly, but can spend considerable time in an unpromising branch.

8. State-Space Search

State-space search represents a problem as a graph whose nodes are states and whose edges are legal transitions. A state may be explicit, such as a vertex in a graph, or implicit, such as a partial assignment in a scheduling problem.

• Breadth-first search (BFS) explores by increasing depth and finds a shortest path in an unweighted graph.
• Depth-first search (DFS) explores one branch deeply before backtracking and supports cycle detection, topological ordering, and exhaustive exploration.
• Uniform-cost search expands the least-cost frontier node and is optimal when edge costs are nonnegative.
• A\ uses f(n) = g(n) + h(n), where g(n) is cost from the start and h(n) estimates the remaining cost. If h(n) is admissible, meaning it never overestimates the true remaining cost, A\ is optimal under standard conditions. If the heuristic is also consistent, graph-search implementations need not reopen already expanded states under the usual assumptions.

State-space search emphasizes representation. Poor state definitions create duplicate work, while incomplete transition rules create incorrect results. A visited set is essential when cycles are possible. For large problems, compact encodings, symmetry reduction, heuristic ordering, and transposition tables can substantially improve performance.

9. Correctness Proof Techniques

9.1 Mathematical induction

Induction is natural for recursive and incremental algorithms. Establish a base case, assume correctness for smaller instances, and show that the algorithm correctly constructs the larger instance. Strong induction permits reliance on all smaller instances rather than only the immediately preceding one.

9.2 Loop invariants

A loop invariant is a statement that remains true before and after every iteration. A proof establishes initialization, maintenance, and termination. For insertion sort, the invariant is that before iteration i, the prefix containing positions 1 through i−1 is sorted and contains exactly the original elements of that prefix.

9.3 Exchange arguments

Exchange arguments establish that a local decision can appear in an optimal solution. They are central to activity selection, fractional knapsack, and minimum spanning trees.

9.4 Optimal-substructure proofs

For DP, partition an optimal solution according to a decision. Show that the residual component must itself be optimal; otherwise a superior residual solution would improve the whole solution. The recurrence must also include every feasible decision, not merely a plausible one.

9.5 Pruning safety

For backtracking, prove that pruned nodes violate a necessary constraint. For branch-and-bound, prove that the bound cannot permit a better solution than the incumbent. These proofs are distinct: feasibility pruning uses logical impossibility, whereas bounding uses objective-value impossibility.

10. Integrated Case Study: Cloud-Job Scheduling

The following is an illustrative case study. A cloud provider must schedule jobs on a resource pool. Each job has a release time, deadline, processing requirement, and expected value. The provider wants to maximize value while respecting capacity and service constraints.

Background and problem

A small batch contains jobs that compete for limited CPU capacity. Some jobs are divisible through elastic execution, while others are indivisible. The provider also needs a feasible schedule rather than merely a value estimate.

Analysis

Different components exhibit different structures:

• Selecting the largest number of non-overlapping service windows resembles activity selection and may admit a greedy earliest-finish strategy.
• Allocating divisible capacity by value per CPU-hour resembles fractional knapsack.
• Selecting indivisible jobs under a capacity budget resembles 0–1 knapsack and requires DP or branch-and-bound.
• Generating schedules subject to precedence and deadline constraints is naturally a state-space search or backtracking problem.
• If jobs have repeated resource-state configurations, memoization can merge equivalent subproblems.

Approach

The provider first applies constraint propagation to remove jobs whose deadlines are impossible. It then uses a greedy heuristic to construct an initial feasible schedule, establishing an incumbent value. A branch-and-bound search explores alternative selections. At each partial schedule, a fractional-capacity relaxation provides an optimistic upper bound. States are canonicalized by remaining capacity, current time, and the set of completed prerequisites; equivalent states are memoized.

Outcome

The hybrid approach produces an exact solution for the batch while examining far fewer alternatives than exhaustive enumeration. For large production workloads, the provider may impose a time limit and return the best feasible solution found, clearly labeling it as time-bounded rather than proven optimal.

Learning points

No single paradigm dominates the entire problem. Greedy construction provides a good incumbent, DP handles repeated resource states, branch-and-bound proves optimality for manageable instances, and state-space search represents precedence constraints. The final design depends on the objective, constraints, input scale, and required guarantee.

11. Practical Selection and Contemporary Issues

A useful selection guide is:

Modern systems introduce additional concerns. Parallel divide-and-conquer must balance tasks and control synchronization. DP tables may exceed cache or accelerator memory, making tiling, compression, or approximate methods necessary. Cloud and AI systems often use heuristics whose empirical performance is strong but whose worst-case guarantees are weak. Reproducibility requires recording tie-breaking rules, random seeds, hardware assumptions, and stopping criteria.

Algorithmic decisions may also have governance implications. A scheduling algorithm can distribute opportunities unevenly; a search heuristic can encode domain bias; and an optimization objective can reward a proxy rather than the true organizational goal. Therefore, practitioners should document objectives, constraints, data assumptions, failure modes, and human override procedures. For safety-critical or regulated applications, explainable bounds and verifiable correctness may be more important than average speed.

Best Practices

1. Define the state precisely before writing code.
2. Separate feasibility constraints from optimization objectives.
3. State preconditions, including sorting, nonnegative weights, or graph connectivity.
4. Prove the pruning rule before implementing it.
5. Use the weakest sufficient complexity claim; distinguish worst-case, average-case, and empirical performance.
6. Test empty inputs, singleton inputs, duplicate values, ties, disconnected graphs, and maximum capacities.
7. Record whether a result is exact, approximate, heuristic, or time-bounded.
8. Use profiling to identify real bottlenecks rather than assuming asymptotic analysis predicts all system costs.

Chapter Summary

Algorithm design paradigms provide reusable structures for solving complex computational problems. Divide-and-conquer separates independent subproblems and combines their solutions, while decrease-and-conquer solves one smaller instance and extends it. Greedy algorithms make local choices and require a greedy-choice proof, commonly through an exchange argument. Dynamic programming exploits optimal substructure and overlapping subproblems; memoization implements the same principle top-down, whereas tabulation proceeds bottom-up.

Backtracking explores partial solutions and prunes infeasible branches. Branch-and-bound extends this idea to optimization by pruning nodes whose optimistic bounds cannot improve the incumbent. State-space search models configurations and transitions, supporting BFS, DFS, uniform-cost search, and heuristic methods such as A\*. Correctness may be established through induction, loop invariants, exchange arguments, optimal-substructure reasoning, and safe-pruning proofs. Effective postgraduate design combines these paradigms, evaluates their assumptions, and reports both theoretical guarantees and practical limitations.

Key Terms

Algorithm design paradigm: A general strategy for constructing algorithms.

Divide-and-conquer: Solving multiple smaller subproblems and combining their solutions.

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

Recurrence: An equation describing the running time or value of a recursive process.

Greedy-choice property: The existence of an optimal solution beginning with a specified local choice.

Exchange argument: A proof that replaces a decision in an optimal solution without worsening it.

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

Overlapping subproblems: Repeated occurrence of the same subproblem.

Dynamic programming: Solving and storing subproblem results to avoid repeated computation.

Memoization: Top-down caching of results for states that are actually requested.

Tabulation: Bottom-up evaluation of DP states.

Backtracking: Systematic search that abandons partial solutions violating constraints.

Branch-and-bound: Optimization search using objective bounds to prune subtrees.

State space: The set of configurations reachable through legal transitions.

Admissible heuristic: A heuristic that never overestimates the true remaining cost.

Loop invariant: A statement preserved throughout loop execution.

Incumbent: The best complete solution currently known.

Pseudo-polynomial time: Complexity polynomial in a numeric value, but not necessarily in its encoded bit length.

Review Questions

Short Answer Questions

1. What distinguishes divide-and-conquer from decrease-and-conquer?
2. Why is earliest finish time the appropriate greedy rule for activity selection?
3. Define optimal substructure and overlapping subproblems.
4. What makes a branch-and-bound upper bound safe for a maximization problem?
5. State the condition under which BFS returns a shortest path.

Long Answer Questions

1. Derive the running time of merge sort and provide an induction-based correctness argument.
2. Explain the greedy-choice property and exchange argument using fractional knapsack.
3. Formulate the 0–1 knapsack dynamic-programming recurrence and discuss its pseudo-polynomial complexity.
4. Compare backtracking and branch-and-bound in terms of goals, pruning, and correctness.
5. Explain A\* search, including the roles of g(n), h(n), admissibility, and consistency.

Analytical / Application Questions

1. Design a hybrid algorithm for a scheduling problem with precedence constraints, limited capacity, and repeated resource states. Justify the paradigms selected.
2. A proposed greedy algorithm selects the shortest available activity rather than the earliest-finishing activity. Construct a counterexample and explain why the greedy proof fails.
3. For a branch-and-bound optimization algorithm, propose an optimistic bound, a node-ordering policy, and a correctness argument for pruning. Discuss what happens when the bound is weak but valid.

Multiple Choice Questions with Answers

Question 1

Which recurrence characterizes merge sort on an input of size n?

A. T(n) = T(n−1) + Θ(1)

B. T(n) = 2T(n/2) + Θ(n)

C. T(n) = T(n/2) + Θ(n²)

D. T(n) = 2T(n−1) + Θ(1)

Correct Answer: B. T(n) = 2T(n/2) + Θ(n)

Question 2

Which property is essential for proving that a greedy choice can begin an optimal solution?

A. Randomized pivoting

B. Greedy-choice property

C. Constant auxiliary space

D. Overlapping subproblems

Correct Answer: B. Greedy-choice property

Question 3

In 0–1 knapsack, why is the one-dimensional capacity loop processed in descending order?

A. To sort items by value

B. To ensure negative capacities are visited

C. To prevent reusing the current item in the same iteration

D. To convert the algorithm into recursion

Correct Answer: C. To prevent reusing the current item in the same iteration

Question 4

For a maximization branch-and-bound problem, when may a node with upper bound U be pruned if B is the incumbent value?

A. When U > B

B. When U = 0 only

C. When U ≤ B

D. Whenever the node is at depth one

Correct Answer: C. When U ≤ B

Question 5

What is the worst-case time complexity of binary search under the standard comparison model?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: B. Θ(log n)

Question 6

Which statement correctly describes memoization?

A. It evaluates every possible state before execution begins

B. It caches results of recursively requested states

C. It always uses less space than tabulation

D. It applies only to greedy algorithms

Correct Answer: B. It caches results of recursively requested states

Question 7

Which condition makes a heuristic admissible for A* search?

A. It always overestimates remaining cost

B. It never overestimates remaining cost

C. It is unrelated to the goal

D. It is always equal to the path cost so far

Correct Answer: B. It never overestimates remaining cost

Question 8

What does backtracking primarily prune?

A. All states with high objective value

B. Partial solutions that violate constraints

C. Every state at even depth

D. Completed feasible solutions

Correct Answer: B. Partial solutions that violate constraints

Question 9

The standard dynamic-programming solution for 0–1 knapsack with n items and capacity W has which time complexity?

A. Θ(n + W)

B. Θ(log(nW))

C. Θ(nW)

D. Θ(2ⁿ/W)

Correct Answer: C. Θ(nW)

Question 10

Which proof technique replaces part of an optimal solution with a greedy choice without reducing quality?

A. Exchange argument

B. Dimensional analysis

C. Hash collision analysis

D. Amortized accounting only

Correct Answer: A. Exchange argument