Algorithm Design Paradigms

Introduction

An algorithm is not merely a sequence of programming instructions; it is a systematic method for transforming input into output while satisfying correctness and resource requirements. For many problems, the central difficulty is not implementation but selecting an appropriate design strategy. Algorithm design paradigms provide reusable ways of organizing reasoning, decomposing problems, proving correctness, and analyzing efficiency.

This chapter examines six closely related paradigms: divide-and-conquer, greedy algorithms, dynamic programming, memoization, backtracking, and branch-and-bound. These paradigms are particularly important in artificial intelligence and machine learning because data processing, optimization, search, feature selection, scheduling, and model inference frequently require efficient problem-solving strategies.

No single paradigm is universally best. Divide-and-conquer often produces efficient recursive solutions; greedy methods are fast but require strong structural justification; dynamic programming exploits overlapping subproblems; memoization improves recursive algorithms by caching results; backtracking systematically explores feasible configurations; and branch-and-bound reduces optimization search by using bounds on attainable solutions.

Learning Objectives

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

1. Explain the purpose and characteristics of major algorithm design paradigms.

2. Design and analyze divide-and-conquer algorithms.

3. Identify optimal substructure and overlapping subproblems.

4. Distinguish greedy choice property from optimal substructure.

5. Apply dynamic programming and memoization to optimization problems.

6. Design backtracking algorithms for constraint-satisfaction problems.

7. Use branch-and-bound for combinatorial optimization.

8. Prove correctness using induction, exchange arguments, and invariants.

9. Compare time, space, implementation, and scalability trade-offs.

10. Select appropriate paradigms for practical AI, data, and software-engineering problems.

1. A Framework for Algorithm Design

A disciplined design process usually includes the following steps:

1. Specify the problem. Define inputs, outputs, constraints, and acceptable solutions.

2. Identify structure. Ask whether the problem contains independent subproblems, repeated subproblems, locally safe choices, or a search space of feasible candidates.

3. Choose a paradigm. Select the strategy whose assumptions match the problem structure.

4. Construct the algorithm. State base cases, recursive or iterative steps, and termination conditions.

5. Prove correctness. Show that the algorithm always produces a valid and, when required, optimal result.

6. Analyze resources. Estimate time and auxiliary space, including recursion and storage overhead.

7. Evaluate practical constraints. Consider input size, memory limits, parallelism, numerical precision, maintainability, and worst-case behavior.

Two structural properties recur throughout this chapter.

Optimal substructure

A problem has optimal substructure if an optimal solution can be constructed from optimal solutions to its subproblems. For example, if a shortest path from vertex A to vertex C passes through B, then the portion from A to B must itself be a shortest path; otherwise replacing it would improve the complete path.

Optimal substructure is necessary for many dynamic-programming and greedy solutions, but it is not sufficient by itself. A problem may have optimal substructure while still requiring dynamic programming rather than a greedy method.

Overlapping subproblems

Subproblems overlap when the same smaller problem is solved repeatedly during a naive recursive computation. Fibonacci computation is a standard example: calculating F(5) recursively recalculates F(3) and F(2) multiple times. Dynamic programming and memoization eliminate this repeated work by storing results.

Greedy-choice property

A problem has the greedy-choice property when a globally optimal solution can be obtained by making a locally optimal choice and then solving the remaining problem. This property must be proved; it cannot be assumed merely because a local choice appears attractive.

2. Divide-and-Conquer

Divide-and-conquer solves a problem through three stages:

• Divide: Partition the problem into smaller instances.
• Conquer: Solve the smaller instances, usually recursively.
• Combine: Merge their solutions into a solution to the original problem.

A general recurrence for a balanced divide-and-conquer algorithm is

\[

T(n)=aT(n/b)+f(n),

\]

where \(a\) is the number of subproblems, each of size approximately \(n/b\), and \(f(n)\) is the nonrecursive division and combination cost. The recurrence assumes that subproblem sizes and combination costs are represented accurately enough for asymptotic analysis.

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

\[

T(n)=2T(n/2)+\Theta(n).

\]

This yields \(T(n)=\Theta(n\log n)\). The recursion has approximately \(\log_2 n\) levels, and each level performs a total of \(\Theta(n)\) merging work.

Worked example: merge sort

Consider the array [38, 27, 43, 3]. It is divided into [38, 27] and [43, 3]. These are divided into single-element arrays. The single elements are merged to produce [27, 38] and [3, 43], and the final merge produces [3, 27, 38, 43].

Merge sort has worst-case and average-case time complexity \(\Theta(n\log n)\). Its auxiliary array storage is \(\Theta(n)\), although carefully engineered variants can alter memory behavior. Merge sort is stable when equal keys are taken from the left subarray first during merging.

Correctness pattern

A standard proof uses induction on input size:

• Base case: An array of size zero or one is already sorted.
• Inductive hypothesis: Assume recursive calls correctly sort smaller arrays.
• Inductive step: The merge procedure correctly combines two sorted arrays into one sorted array, so the complete result is sorted.

Practical strengths and limitations

Divide-and-conquer is often easy to parallelize because independent subproblems can execute concurrently. It also supports cache-efficient implementations when subproblems become small enough to fit in fast memory. However, recursion introduces call overhead, unbalanced partitions can produce poor performance, and combination costs may dominate if not controlled.

Quicksort illustrates the effect of partition quality. Its recurrence is approximately \(T(n)=2T(n/2)+\Theta(n)\) for balanced partitions, giving \(\Theta(n\log n)\), but \(T(n)=T(n-1)+\Theta(n)\) for repeatedly unbalanced partitions, giving \(\Theta(n^2)\). Randomized pivots or median-based strategies reduce the likelihood of consistently poor partitions.

3. Greedy Algorithms

A greedy algorithm constructs a solution incrementally. At each stage it selects the best available local option according to a selection rule and never reverses that decision.

A greedy design generally requires:

1. A precisely defined feasible set.

2. An objective function.

3. A greedy selection rule.

4. Proof that the selection is safe.

5. A method for solving the residual problem.

Activity-selection problem

Suppose activities have start and finish times, and the objective is to select the maximum number of mutually compatible activities. The greedy rule is to repeatedly select the compatible activity with the earliest finish time.

The rule is correct by an exchange argument. Let activity \(g\) be a compatible activity with the earliest finish time, and let \(o\) be the first activity in some optimal solution. Since \(g\) finishes no later than \(o\), replacing \(o\) with \(g\) does not reduce the number of activities that can subsequently be selected. Therefore an optimal solution exists that begins with \(g\). The same reasoning applies recursively to the remaining activities.

Minimum spanning trees

Kruskal's algorithm repeatedly chooses the lightest edge that does not create a cycle. A disjoint-set data structure efficiently tests whether two vertices are already connected. The cut property supports correctness: for any cut of a weighted connected graph, a minimum-weight edge crossing that cut is safe to include in some minimum spanning tree.

Prim's algorithm grows one tree from a starting vertex, repeatedly adding the least-weight edge connecting the tree to an outside vertex. Both Kruskal's and Prim's algorithms are greedy, but they maintain different solution structures.

When greedy fails

For the fractional knapsack problem, items can be divided, and choosing greatest value-to-weight ratio first is optimal. For the 0/1 knapsack problem, items cannot be divided, and the same rule can fail. Consider capacity 10 and items (weight, value): (6, 30), (5, 26), and (5, 26). The ratio rule selects the first item, value 30, but selecting the two weight-5 items gives value 52. The 0/1 problem requires dynamic programming or another exact method.

Thus, an attractive local rule is not a correctness proof. Greedy algorithms are valuable when their structural conditions can be established; otherwise they may be fast heuristics rather than exact algorithms.

4. Dynamic Programming

Dynamic programming (DP) solves problems with optimal substructure and overlapping subproblems. Instead of repeatedly solving the same subproblem, DP solves each distinct subproblem once and stores its result.

A DP design has four central components:

1. State definition: What information uniquely identifies a subproblem?

2. Recurrence: How is a state computed from smaller states?

3. Base cases: What states are directly known?

4. Evaluation order: In what order can required states be computed?

0/1 knapsack formulation

Let \(K[i][w]\) denote the maximum value obtainable using the first \(i\) items with capacity at most \(w\). Item \(i\) has weight \(w_i\) and value \(v_i\). Assuming nonnegative integer capacities and weights, the recurrence is

\[

K[i][w]=

\begin{cases}

K[i-1][w], & w_i>w,\\

\max(K[i-1][w], K[i-1][w-w_i]+v_i), & w_i\leq w.

\end{cases}

\]

The first case excludes an item that cannot fit. The second compares excluding and including it. Base cases are \(K[0][w]=0\) for all capacities and \(K[i][0]=0\) for all item counts. The table requires \(\Theta(nC)\) time and \(\Theta(nC)\) space, where \(n\) is the number of items and \(C\) is the integer capacity. This is pseudo-polynomial because complexity depends on the numerical capacity, not only on its bit-length.

For three items with capacity 7—(weight 3, value 4), (weight 4, value 5), and (weight 5, value 7)—the best choice is the first and third items: total weight 8, which is invalid. The best valid choice is the second and third items only if their total weight is 9, also invalid; therefore the maximum is value 7 from the third item, or value 5 from the second plus value 4 from the first gives weight 7 and value 9. Thus the optimum is 9.

Longest common subsequence

For strings \(X\) and \(Y\), let \(L[i][j]\) be the length of a longest common subsequence of their first \(i\) and first \(j\) characters. If the final characters match, they can extend a common subsequence:

\[

L[i][j]=L[i-1][j-1]+1.

\]

If they do not match:

\[

L[i][j]=\max(L[i-1][j],L[i][j-1]).

\]

The recurrence is valid because when final characters differ, at least one of them is excluded from an optimal subsequence. The algorithm takes \(\Theta(mn)\) time for strings of lengths \(m\) and \(n\).

Bottom-up and top-down DP

Bottom-up DP fills a table from smaller states to larger states. It avoids recursion overhead and makes computation order explicit. Top-down DP, usually called memoization, begins with the original problem and recursively computes only states that are reached, storing each result. Bottom-up is often preferable when most states are needed; memoization can be more efficient when the reachable state space is sparse.

5. Memoization

Memoization is a top-down optimization technique. A recursive function checks a cache before solving a subproblem. If the result is present, it returns the cached value; otherwise it computes, stores, and returns the result.

For Fibonacci numbers, the naive recurrence

\[

F(n)=F(n-1)+F(n-2),\quad F(0)=0,\quad F(1)=1

\]

has exponential running time when implemented without storage because of repeated calls. Memoization reduces the time to \(\Theta(n)\) and uses \(\Theta(n)\) cache space, excluding recursion-stack conventions. An iterative bottom-up implementation can also use \(\Theta(1)\) auxiliary space when only the previous two values are needed.

Memoization is especially useful when:

• the recurrence is naturally expressed recursively;
• only a fraction of possible states will be visited;
• the state space is irregular or difficult to enumerate;
• preserving the recursive problem structure improves clarity.

Its limitations include recursion depth, cache-management overhead, and potentially high memory consumption. Cache keys must represent all information that affects the result; omitting a relevant parameter produces incorrect answers.

6. Backtracking

Backtracking searches through a space of candidate solutions by making a choice, recursively extending the partial solution, and undoing the choice when it cannot lead to a valid completion. It is particularly suitable for constraint-satisfaction problems such as N-Queens, Sudoku, graph coloring, and generating permutations.

A backtracking algorithm typically follows this pattern:

```text

search(partial):

if partial is a complete solution:

report partial

else:

for each candidate choice:

if choice is feasible:

make choice

search(updated partial)

undo choice

```

The feasibility test is a pruning rule. It does not estimate objective value; it simply removes partial assignments that already violate constraints.

N-Queens example

The N-Queens problem places \(n\) queens on an \(n\times n\) chessboard so that no two queens share a row, column, or diagonal. A row-by-row algorithm chooses a column for each row. A placement is safe if its column and two diagonal identifiers are unused. For a cell at row \(r\), column \(c\), the two diagonal identifiers can be represented by \(r-c\) and \(r+c\).

The algorithm places a queen, recursively processes the next row, and removes the queen if the subsequent search fails. In the worst case, the search is exponential, although constraint checks greatly reduce the explored tree in practice.

Backtracking differs from dynamic programming because it searches configurations rather than aggregating repeated subproblem values. It differs from branch-and-bound because its primary pruning criterion is feasibility, whereas branch-and-bound prunes using objective bounds.

7. Branch-and-Bound

Branch-and-bound is an exact optimization framework for exploring a search tree while avoiding subtrees that cannot improve the best solution found so far.

• Branch: Divide the problem into subproblems.
• Bound: Compute an optimistic bound on the best solution possible in each subproblem.
• Prune: Discard a subproblem if its bound is no better than the current incumbent solution.

For maximization, if a node has upper bound \(U\) and the best known feasible value is \(B\), the node can be pruned when \(U\leq B\). For minimization, a lower bound \(L\) allows pruning when \(L\geq B\). These conditions assume that the bound is valid: an upper bound must never underestimate the best possible value in a maximization subtree, and a lower bound must never overestimate it in a minimization subtree.

Knapsack illustration

In 0/1 knapsack, a node may represent decisions about the first several items. An upper bound can be computed by optimistically allowing fractional use of remaining items, filling unused capacity according to value-to-weight ratio. Because the fractional problem permits more choices than the 0/1 problem, its value is at least as large as the true integral optimum. If this upper bound is no greater than the current best feasible value, the node cannot improve the solution and may be pruned.

Branch-and-bound can be dramatically faster than exhaustive enumeration, but its worst-case time remains exponential for many NP-hard problems. Performance depends on the quality of bounds, the order in which nodes are explored, and the quality of the initial feasible solution.

8. Comparing the Paradigms

| Paradigm | Main structure | Typical guarantee | Common cost | Representative problems |

|---|---|---|---|---|

| Divide-and-conquer | Independent smaller instances | Often polynomial or logarithmic-depth recursion | Recursion and combine overhead | Merge sort, binary search |

| Greedy | Irreversible local choices | Optimal only with proven greedy property | Usually low time and space | Activity selection, MST |

| Dynamic programming | Repeated states and optimal substructure | Exact optimum when recurrence is correct | Table size can be large | Knapsack, LCS |

| Memoization | Recursive repeated states | Same as corresponding DP recurrence | Cache and recursion overhead | Fibonacci, top-down search |

| Backtracking | Feasible configuration search | Exact enumeration with pruning | Often exponential worst case | N-Queens, Sudoku |

| Branch-and-bound | Optimization search with bounds | Exact optimization | Often exponential worst case | TSP, integer knapsack |

The paradigms can also be combined. A branch-and-bound algorithm may use a greedy heuristic to obtain a strong initial incumbent. A divide-and-conquer algorithm may use memoization when its subproblems overlap. Backtracking can use dynamic-programming tables to avoid repeated states. In practical systems, hybrid designs are common.

9. Detailed Applied Case: Feature Subset Selection in an AI Pipeline

Background

An illustrative case concerns a classification system with 40 candidate features. Training and inference become expensive when all features are used, while irrelevant or redundant features may reduce generalization performance. The engineering team seeks a small feature subset that maintains predictive quality under a computational budget.

Problem

Selecting the best subset of features is combinatorial: there are \(2^{40}\) possible subsets. Exhaustive evaluation is impractical. The objective may combine validation error, model latency, and the number of selected features.

Analysis

A greedy forward-selection method begins with no features and repeatedly adds the feature producing the largest measured improvement. It is computationally attractive, but it can miss a pair of features that is useful jointly although neither is useful alone. Therefore greedy selection is a heuristic unless a suitable structural guarantee exists.

A backtracking method can explore subsets and prune those violating a strict feature-count constraint. However, without strong bounds, its search may still be exponential. A branch-and-bound method can maintain the best validation score found and compute an optimistic bound for each partial subset. If even the optimistic score cannot exceed the incumbent, the branch is pruned.

Dynamic programming is appropriate only if the evaluation objective decomposes into a manageable state representation, such as additive costs over discrete groups. General validation accuracy does not normally have this property, because interactions among features and model-training effects make the objective nonadditive.

Approach and solution

The team uses a hybrid strategy:

1. A greedy procedure quickly constructs an initial high-quality subset.

2. Features are ordered using domain-informed and statistical screening.

3. Branch-and-bound explores promising additions and exclusions.

4. An optimistic bound is computed using a relaxed model or an upper estimate of attainable utility.

5. Cross-validation evaluates only surviving candidates.

6. The final subset is tested on a held-out test set used once for unbiased reporting.

Outcome

The hybrid method does not guarantee a fast solution in every dataset, but it reduces search substantially compared with enumeration. The initial greedy solution improves the incumbent early, making more pruning possible. The final model is selected not solely for validation accuracy but also for latency, interpretability, and stability across data splits.

Learning points

The case demonstrates that paradigm selection depends on objective structure. Greedy methods provide strong initial solutions, branch-and-bound provides exactness when bounds are valid, and empirical AI objectives may not satisfy the assumptions required by classical dynamic programming. It also illustrates that an algorithmic optimum is not automatically a production optimum: data leakage, unstable validation, fairness, and maintenance costs must be considered.

10. Correctness, Complexity, and Engineering Trade-offs

Correctness proofs should match the paradigm. Divide-and-conquer commonly uses induction. Greedy algorithms often require exchange arguments or cut properties. Dynamic programming requires demonstrating that the recurrence considers all relevant alternatives and that each stored state has the stated meaning. Backtracking correctness follows from showing that every feasible solution is generated unless a branch is pruned only after violating a valid constraint. Branch-and-bound additionally requires proving that every discarded node cannot contain a better solution.

Asymptotic complexity describes growth as input size increases, but engineering decisions also depend on constants, memory locality, parallelism, input distribution, and implementation language. A theoretically superior algorithm may be slower for small inputs. For example, a practical sorting library may use a hybrid algorithm that switches to insertion sort on small subarrays.

Space complexity must include tables, caches, recursion stacks, graph representations, and stored candidate solutions. In AI systems, memory bandwidth and repeated model evaluation may dominate arithmetic operation counts. Time complexity should therefore be supplemented by profiling on representative workloads.

11. Ethical and Governance Considerations

Algorithm design paradigms are mathematically neutral, but their use in AI systems can produce social consequences. A greedy allocation rule may systematically disadvantage groups if its objective ignores fairness. A feature-selection algorithm may remove variables that support accessibility or fairness monitoring. Branch-and-bound or dynamic programming may optimize a proxy objective that conflicts with human welfare.

Professional practice requires:

• defining objectives transparently;
• documenting assumptions and constraints;
• testing performance across relevant demographic and operational conditions;
• avoiding leakage of protected information while preserving fairness evaluation;
• recording random seeds, versions, and data provenance;
• monitoring deployed systems for drift and unintended effects;
• retaining human oversight for high-impact decisions.

Optimization should not be treated as justification for ignoring legal, ethical, privacy, or safety requirements.

12. Contemporary Developments and Best Practices

Modern implementations increasingly combine classical paradigms with parallel computing, probabilistic heuristics, learned heuristics, and hardware-aware optimization. GPU systems favor decompositions exposing parallel subproblems. Large-scale data processing uses distributed divide-and-conquer patterns. Learned cost models can guide branch ordering, although they must not invalidate mathematical bounds when exactness is required.

Recommended practices include:

1. State the invariant or meaning of every major data structure.

2. Separate feasibility checks from objective evaluation.

3. Prove pruning rules before relying on them.

4. Use strong initial solutions in branch-and-bound.

5. Detect whether subproblems truly overlap before adopting DP.

6. Test greedy algorithms against adversarial counterexamples.

7. Guard recursive algorithms against excessive stack depth.

8. Measure memory as well as running time.

9. Use approximation or heuristics explicitly when exact computation is infeasible.

10. Validate algorithmic results independently on realistic data.

Chapter Summary

Algorithm design paradigms provide systematic strategies for constructing correct and efficient algorithms. Divide-and-conquer decomposes problems into smaller instances and combines their solutions. Greedy algorithms make locally attractive choices and require proof of the greedy-choice property. Dynamic programming stores solutions to overlapping subproblems and relies on a correct recurrence, base cases, and evaluation order. Memoization is a top-down implementation of repeated-subproblem optimization. Backtracking explores feasible configurations while undoing unsuccessful choices. Branch-and-bound explores optimization alternatives but prunes nodes using valid optimistic or pessimistic bounds.

Optimal substructure appears in greedy and dynamic-programming solutions, but greedy choice requires the additional guarantee that a local decision can safely begin an optimal solution. Correctness proofs and complexity analysis are central to professional algorithm design. In applied AI, hybrid approaches are common, and practical quality also depends on memory, validation, fairness, interpretability, and deployment constraints.

Key Terms

Optimal substructure: Property that an optimal solution contains optimal solutions to relevant subproblems.

Overlapping subproblems: Repeated occurrence of the same smaller problem during computation.

Greedy-choice property: Property that a locally optimal choice can lead to a globally optimal solution.

Divide-and-conquer: Paradigm that divides a problem, solves subproblems, and combines results.

Recurrence: Equation describing the running time or value of a recursive computation.

Memoization: Top-down caching of results from solved subproblems.

Dynamic programming: Optimization method that stores solutions to subproblems.

State: Information that uniquely identifies a DP subproblem.

Base case: Directly solvable case that terminates recursion or initializes a table.

Backtracking: Systematic search that extends and reverses partial solutions.

Constraint satisfaction: Problem type requiring assignments that obey specified restrictions.

Pruning: Eliminating a search branch that cannot produce a useful or valid solution.

Branch-and-bound: Optimization search using bounds to discard noncompetitive subproblems.

Incumbent: Best feasible solution currently known in an optimization search.

Upper bound: Value that cannot be lower than the best possible value in a maximization subtree.

Exchange argument: Proof technique that replaces a solution choice with a greedy choice without worsening quality.

Pseudo-polynomial time: Complexity polynomial in a numerical value such as capacity, rather than its encoding length.

Optimality: Property of achieving the best value according to a specified objective.

Review Questions

Short Answer Questions

1. What are the three stages of divide-and-conquer?

2. Define optimal substructure and overlapping subproblems.

3. Why does a greedy algorithm require a correctness proof?

4. What is the difference between memoization and bottom-up dynamic programming?

5. Distinguish feasibility pruning in backtracking from bound-based pruning in branch-and-bound.

Long Answer Questions

1. Explain merge sort, derive its recurrence, and prove its correctness by induction.

2. Describe the greedy-choice property using activity selection as an example.

3. Formulate the dynamic-programming recurrence for 0/1 knapsack and explain its complexity.

4. Compare backtracking and branch-and-bound in terms of search tree, pruning, and guarantees.

5. Discuss how memory, validation, fairness, and interpretability influence algorithm selection in AI systems.

Analytical / Application Questions

1. Construct a counterexample showing why value-to-weight ratio is not always optimal for 0/1 knapsack.

2. Design a branch-and-bound strategy for selecting a constrained subset of features, specifying an incumbent and a valid pruning bound.

3. Given a recursive algorithm with many repeated states, determine whether memoization, bottom-up dynamic programming, or divide-and-conquer is most appropriate and justify your choice.

Multiple Choice Questions with Answers

Question 1

Which condition is especially associated with dynamic programming?

A. The problem has only independent subproblems

B. The problem has overlapping subproblems and optimal substructure

C. Every local choice is guaranteed to be optimal

D. No feasible solution can be rejected

Correct Answer: B. The problem has overlapping subproblems and optimal substructure

Question 2

What is the worst-case time complexity of standard quicksort with consistently unbalanced partitions?

A. Theta(log n)

B. Theta(n)

C. Theta(n log n)

D. Theta(n^2)

Correct Answer: D. Theta(n^2)

Question 3

In activity selection, which greedy rule produces an optimal maximum-cardinality schedule?

A. Choose the activity with the longest duration

B. Choose the activity with the earliest start time

C. Choose the compatible activity with the earliest finish time

D. Choose the activity with the greatest numerical label

Correct Answer: C. Choose the compatible activity with the earliest finish time

Question 4

For 0/1 knapsack with n items and integer capacity C, the standard table-based dynamic program takes which time complexity?

A. Theta(nC)

B. Theta(n log C)

C. Theta(C^n)

D. Theta(log n)

Correct Answer: A. Theta(nC)

Question 5

What does memoization primarily eliminate?

A. All recursion

B. Repeated computation of identical subproblems

C. The need for base cases

D. The need to define a state

Correct Answer: B. Repeated computation of identical subproblems

Question 6

In backtracking, a branch is normally pruned when it:

A. Has a partial assignment violating a constraint

B. Contains the first candidate considered

C. Uses recursion

D. Has a feasible partial assignment

Correct Answer: A. Has a partial assignment violating a constraint

Question 7

For a maximization branch-and-bound problem, a node with upper bound U can be pruned when:

A. U is greater than the incumbent

B. U equals the number of variables

C. U is no greater than the incumbent

D. The node has not yet been expanded

Correct Answer: C. U is no greater than the incumbent

Question 8

Which proof technique is commonly used to establish the correctness of many greedy algorithms?

A. Exchange argument

B. Random sampling

C. Hash collision analysis

D. Dimensionality reduction

Correct Answer: A. Exchange argument

Question 9

A valid upper bound for a maximization branch-and-bound node must:

A. Underestimate every possible solution in the node

B. Be at least as large as the best value attainable in the node

C. Equal the value of the first feasible solution

D. Ignore the remaining capacity

Correct Answer: B. Be at least as large as the best value attainable in the node

Question 10

Which statement best distinguishes a greedy algorithm from dynamic programming?

A. Greedy algorithms always use recursion, whereas DP never does

B. Greedy algorithms make irreversible local choices, whereas DP compares stored subproblem results

C. Greedy algorithms cannot solve optimization problems

D. Dynamic programming never requires optimal substructure

Correct Answer: B. Greedy algorithms make irreversible local choices, whereas DP compares stored subproblem results