11. Algorithm Design Paradigms

Introduction and Context

An algorithm is not merely a sequence of instructions; it is a structured way of reasoning about a computational problem. The choice of algorithmic strategy often matters more than the choice of programming language. Two programs written in C may produce the same output, yet differ enormously in execution time, memory consumption, scalability, maintainability, and resistance to unfavorable inputs. Algorithm design paradigms provide reusable ways of discovering such programs.

A design paradigm is a general problem-solving pattern. It does not prescribe one fixed algorithm. Instead, it identifies how a problem can be decomposed, how decisions should be made, what information must be retained, and how partial solutions can be combined or rejected. Divide-and-conquer, greedy algorithms, dynamic programming, backtracking, branch-and-bound, randomized algorithms, and approximation algorithms are among the most important paradigms in advanced data structures and algorithms.

These paradigms are closely related to topics studied earlier in the course. Recursion supplies the mechanism for divide-and-conquer and backtracking; trees and graphs provide the structures on which many paradigms operate; sorting and searching illustrate reduction and partitioning; and asymptotic analysis provides the language for comparing solutions. In professional development, the paradigm selected at the design stage influences software architecture, hardware requirements, testing strategy, and operational cost.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Explain the assumptions and design logic of major algorithmic paradigms.

2. Formulate recurrence relations and analyze divide-and-conquer algorithms.

3. Distinguish greedy-choice properties from optimal-substructure properties.

4. Design dynamic-programming solutions using memoization and tabulation.

5. Construct backtracking and branch-and-bound algorithms with effective pruning.

6. Explain the role of randomness and approximation in difficult computational problems.

7. Implement representative techniques in C using suitable data structures.

8. Justify correctness, time complexity, space complexity, and practical trade-offs.

9. Select an appropriate paradigm for a real computational situation.

A Framework for Choosing a Design Paradigm

A useful first step is to characterize the problem rather than immediately writing code. Ask whether the problem can be divided into independent subproblems, whether subproblems overlap, whether a locally best choice can be proved safe, whether the solution space is combinatorial, and whether exact optimization is computationally realistic.

The following distinctions are particularly important:

• Independent subproblems: If recursive subproblems do not substantially overlap, divide-and-conquer is often appropriate.
• Overlapping subproblems: If the same states recur, storing their solutions leads to dynamic programming.
• Greedy-choice property: If an optimal solution can begin with a locally optimal choice, a greedy method may be valid.
• Complete solution space: If candidates must be constructed incrementally, backtracking can enumerate only promising candidates.
• Optimization over a search tree: If partial solutions can be bounded, branch-and-bound can avoid exploring inferior regions.
• Acceptable probabilistic behavior: If randomization simplifies the algorithm or improves expected performance, randomized algorithms may be suitable.
• Computational intractability: If exact optimization is impractical, approximation algorithms offer solutions with a provable quality guarantee.

A paradigm is not selected solely by its average running time. Correctness conditions, input distribution, memory hierarchy, reproducibility, numerical precision, and the cost of implementation also matter.

Divide-and-Conquer: Solve Smaller Problems, Then Combine

Divide-and-conquer solves a problem in three stages: divide the instance into smaller instances, conquer the smaller instances recursively, and combine their solutions. The method is successful when the subproblems are substantially smaller and their solutions can be combined efficiently.

If a problem of size n creates a subproblems of size n/b and requires f(n) work outside recursion, its running time is commonly represented as

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

The Master Theorem provides standard conclusions for many such recurrences. If f(n) is asymptotically smaller than n^(log_b a), then T(n) is Θ(n^(log_b a)). If f(n) has the same order, an additional logarithmic factor commonly appears. If f(n) is asymptotically larger and satisfies a regularity condition, T(n) is Θ(f(n)). These cases must be applied carefully; unusual subproblem sizes or nonpolynomial terms may require substitution or recursion-tree analysis.

Merge Sort as a Model

Merge sort divides an array into two halves, recursively sorts each half, and merges the sorted halves. The recurrence is

T(n) = 2T(n/2) + Θ(n),

so the running time is Θ(n log n). Its correctness follows by induction: arrays of size one are sorted; assuming both recursive calls return sorted arrays, the merge procedure produces the sorted union by repeatedly selecting the smaller front element. Merge sort has predictable worst-case performance and is stable, but its ordinary array implementation requires Θ(n) auxiliary space.

Quicksort and Partitioning

Quicksort selects a pivot, partitions the array into elements smaller and larger than the pivot, and recursively sorts the partitions. If partitions are balanced, its recurrence is approximately 2T(n/2)+Θ(n), giving Θ(n log n). If the pivot repeatedly produces partitions of sizes zero and n−1, the worst case is Θ(n²). Random pivot selection does not remove the worst-case possibility, but it gives expected Θ(n log n) time for many input models and prevents an adversary from easily predicting the partition pattern.

The correctness argument uses a loop invariant for partitioning: at each stage, elements already placed on the left satisfy the pivot relation, elements on the right satisfy the opposite relation, and unprocessed elements remain between the scanning indices. Once partitioning ends, the pivot is in its final sorted position.

Divide-and-Conquer in C

A recursive function should have an explicit base case and should make measurable progress toward it. For example, a merge-sort routine may receive an array and inclusive indices `left` and `right`; it returns immediately when `left >= right`, computes `mid = left + (right-left)/2` to avoid index overflow, recursively processes both intervals, and calls a merge routine. In production code, allocation failures, integer overflow in size calculations, and the cost of repeated temporary allocation must also be considered.

Greedy Algorithms: Irreversible Choices with a Proof Obligation

A greedy algorithm constructs a solution step by step, selecting what appears best at the current stage and normally never revising that choice. Greedy algorithms are attractive because they are often simple and efficient. Their danger is equally clear: local improvement does not generally imply global optimality.

Two properties support a greedy proof. The greedy-choice property means that some optimal solution begins with the greedy choice. Optimal substructure means that after making that choice, the remaining problem has an optimal solution that completes the overall optimum. Optimal substructure alone is insufficient; many dynamic-programming problems have it without admitting a valid greedy strategy.

Activity Selection

In activity selection, each activity has a start and finish time, and the objective is to select the maximum number of mutually compatible activities. Sorting by increasing finish time and repeatedly selecting the next compatible activity is optimal. The exchange argument is central: consider an optimal schedule whose first activity may differ from the earliest-finishing activity. Replacing its first activity with the earliest-finishing one cannot reduce the room available for the remaining activities. The problem then reduces to selecting activities after that finish time.

Fractional Knapsack

In fractional knapsack, items may be divided. Sorting by value-to-weight ratio and taking the highest ratio first is optimal. The exchange argument replaces any lower-ratio material in a proposed optimum with higher-ratio material until the greedy choice is satisfied. This reasoning fails for 0/1 knapsack, where an item must be taken whole or rejected. That distinction is a standard example of why a small change in problem definition can invalidate a paradigm.

Minimum Spanning Trees

Kruskal’s algorithm repeatedly chooses the lightest edge that does not create a cycle. A disjoint-set union structure tests whether two vertices already belong to the same component. Prim’s algorithm grows one tree by choosing the least-weight edge crossing from the current tree to an unvisited vertex. Both are justified by the cut property: for any cut of a weighted connected graph, a lightest edge crossing that cut is safe for some minimum spanning tree. Kruskal generally takes O(E log E) time because of sorting; with a binary heap, Prim’s algorithm commonly takes O(E log V).

Greedy methods can fail for shortest paths when negative edges exist. Dijkstra’s algorithm is correct for nonnegative edge weights because the smallest tentative distance is final; a negative edge can later produce a shorter route and destroy that reasoning.

Dynamic Programming: Remembering the Right States

Dynamic programming (DP) applies when a problem has overlapping subproblems and optimal substructure. Instead of repeatedly solving the same subproblem, DP records its answer. Memoization is top-down: recursion is retained and results are cached. Tabulation is bottom-up: states are computed in an order that guarantees their dependencies are already available.

A disciplined DP design has four components:

1. Define a state precisely, such as `dp[i]` or `dp[i][w]`.

2. Derive a recurrence from the final decision or transition.

3. Establish base cases and an evaluation order.

4. Identify the required final state and reconstruct choices if necessary.

0/1 Knapsack

Let `dp[i][w]` be the maximum value obtainable using the first i items with capacity w. For item i of weight `weight[i]` and value `value[i]`, the recurrence is

`dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])`,

when the item fits; otherwise it equals `dp[i-1][w]`. The table requires O(nW) time and O(nW) space, where W is capacity. Space can be reduced to O(W) by processing capacities in descending order. Descending order is essential: ascending order would allow the same item to be used more than once and would change the problem into unbounded knapsack.

Longest Common Subsequence

For strings X and Y, `dp[i][j]` may denote the length of an LCS of the prefixes ending at positions i and j. If the characters match, the value is one plus `dp[i-1][j-1]`; otherwise it is the maximum of `dp[i-1][j]` and `dp[i][j-1]`. The table gives O(mn) time and space, while storing predecessor decisions permits reconstruction of an actual subsequence.

Bellman–Ford and State Relaxation

Shortest-path computation can also be understood as DP over the number of edges in a path. Bellman–Ford relaxes every edge repeatedly, up to |V|−1 times, and detects a reachable negative cycle if an additional relaxation remains possible. Its O(VE) worst-case time is higher than Dijkstra’s, but it supports negative edge weights.

DP is not automatically efficient. A state containing many dimensions may create an exponential table. The relevant measure is the number of distinct states multiplied by the transition cost. A compact state representation is therefore a major design decision.

Backtracking: Systematic Exploration with Pruning

Backtracking constructs a candidate incrementally. When a partial candidate cannot lead to a feasible complete solution, the algorithm abandons it and returns to the latest decision point. It is especially useful for constraint-satisfaction and enumeration problems such as n-queens, graph coloring, subset generation, and Sudoku.

A generic pattern is:

```c

void search(State *s) {

if (complete(s)) {

record(s);

return;

}

for (each candidate c) {

if (consistent(s, c)) {

apply(s, c);

search(s);

undo(s, c);

}

}

}

```

The `undo` operation is not an implementation detail; it restores the exact state expected by the next branch. Efficient feasibility tests are crucial. In n-queens, three Boolean arrays can record occupied columns and diagonals, reducing conflict checks to O(1) per candidate instead of scanning previously placed queens.

Backtracking is complete: if it explores every candidate not eliminated by a valid feasibility rule, it will find every solution. Its worst-case time is often exponential, but ordering decisions and strong pruning can make practical instances manageable. A common mistake is to use a pruning condition that is only plausible rather than logically safe; such a condition may silently remove valid solutions.

Branch-and-Bound: Optimization Through Bounds

Backtracking primarily prunes infeasible candidates. Branch-and-bound extends this idea to optimization. Each node represents a partial solution, and a bound estimates the best objective value that could still be achieved from that node. For a maximization problem, a node can be discarded when its upper bound is no greater than the value of the best complete solution already found. For minimization, a lower bound is compared with the current incumbent.

The method includes three choices: how to branch, how to compute bounds, and which live node to explore next. Depth-first search uses little memory and may quickly find a good incumbent. Best-first search, often implemented with a priority queue, expands the node with the most promising bound but can consume substantial memory.

For 0/1 knapsack, a fractional-knapsack calculation supplies an upper bound: pretend that remaining items may be divided. Since the fractional problem is at least as optimistic as the integral problem, it is safe as an upper bound. If the bound does not exceed the current best value, the node is pruned. The quality of the bound determines performance; a loose bound gives little pruning, while an incorrectly tight bound destroys correctness.

Branch-and-bound is exact, unlike approximation. Nevertheless, its worst-case running time remains exponential for many problems. It is best viewed as an intelligent reduction of search, not as a guarantee of polynomial complexity.

Randomized Algorithms: Using Probability as a Design Resource

A randomized algorithm makes random choices during execution or receives a randomly selected input transformation. In a Las Vegas algorithm, the answer is always correct, while running time is random; randomized quicksort is an example. In a Monte Carlo algorithm, running time is bounded or controlled, but a small probability of error is permitted. The distinction must be made explicit in a system specification.

Randomization is useful for avoiding predictable worst cases, sampling large data sets, load balancing, hashing, geometric computation, and distributed coordination. Randomized quicksort has expected O(n log n) time when the pivot is selected independently and suitably. Its expected analysis averages over the algorithm’s random choices for every fixed input; this differs from an average-case analysis that assumes a probability distribution over inputs.

Hash tables illustrate another principle. A carefully chosen randomized hash function can make systematic collision patterns unlikely. However, randomization does not excuse poor engineering: a secure application may require a cryptographically appropriate generator, while a simulation may require a reproducible seed. Random choices also complicate debugging, testing, and auditability. Production systems should record seeds or provide deterministic replay when failures must be investigated.

Approximation Algorithms: When Exactness Is Too Expensive

Many important optimization problems are NP-hard, making exact polynomial-time algorithms unlikely under widely accepted complexity assumptions. An approximation algorithm runs efficiently and returns a solution with a provable relationship to the optimum.

For a minimization problem, an algorithm has approximation ratio ρ if its result is at most ρ times the optimum. For a maximization problem, the result is commonly at least OPT/ρ, or is described by a fraction of OPT. The ratio must be stated with the correct direction.

A classical example is the metric travelling-salesperson problem, where distances satisfy symmetry and the triangle inequality. Constructing a minimum spanning tree, performing a preorder traversal, and shortcutting repeated vertices gives a tour no more than twice the optimal tour length. The shortcutting is safe because the triangle inequality ensures that replacing a path by a direct edge does not increase cost.

The metric condition is essential. Without the triangle inequality, shortcutting may be arbitrarily expensive. This illustrates a central principle of approximation design: guarantees depend on explicit assumptions. Other approaches include greedy algorithms with charging arguments, linear-programming relaxation followed by rounding, and polynomial-time approximation schemes (PTAS), which trade running time for an arbitrarily small error parameter.

Correctness, Complexity, and Implementation Discipline

A design paradigm is academically incomplete without a correctness argument. Induction is natural for recursive algorithms and DP. Exchange arguments support many greedy algorithms. Loop invariants establish the behavior of iterative procedures. A search-tree argument proves that backtracking or branch-and-bound does not omit an admissible optimum, while a bound proof establishes safe pruning. Approximation proofs compare the constructed solution with an optimal or relaxed solution.

Complexity analysis should identify input parameters rather than hide them in a single n. A graph algorithm may depend on V and E; knapsack DP depends on n and capacity W; string algorithms depend on two lengths; branch-and-bound depends strongly on the strength of its bound and may still have exponential worst-case behavior. Space includes recursion stack, tables, queues, temporary arrays, and data structures such as disjoint-set forests.

In C, algorithm design must also account for pointer validity, array bounds, integer overflow, memory ownership, recursion depth, and initialization. A theoretically correct recurrence can be implemented incorrectly through an off-by-one index or an uninitialized table. Unit tests should include empty and singleton inputs, duplicate values, already sorted data, extreme weights, disconnected graphs, negative edges where relevant, and instances designed to trigger worst-case behavior.

An Illustrative Case Study: Selecting a Route-Planning Strategy

Background

Consider a logistics company that must plan routes among distribution centers. The system initially uses a single shortest-path routine for every request. As the service expands, the input conditions become diverse: road weights may represent travel time, some data feeds may contain temporary negative adjustments, and management occasionally asks for a near-optimal tour visiting many locations.

Situation and Analysis

Using Dijkstra’s algorithm for all requests is unsafe when negative edge weights are possible. Applying an exact travelling-salesperson algorithm to large tour requests is computationally unrealistic. Recomputing the same route states for repeated capacity-constrained delivery decisions wastes time. A single paradigm cannot properly address all three requirements.

Strategy

The engineering team first classifies requests. For ordinary nonnegative road networks, Dijkstra’s algorithm with a binary heap is selected. For networks that may contain negative edges, Bellman–Ford is used on smaller instances, together with validation for reachable negative cycles. Delivery loading decisions use dynamic programming when capacity is moderate, while a branch-and-bound version is reserved for smaller instances where an exact answer is required and a strong bound is available. For large tour-planning requests under metric distances, a spanning-tree-based 2-approximation is offered, with the approximation status disclosed to users.

Randomized pivot selection is used in an internal sorting component, and deterministic replay is retained through recorded seeds. Every implementation includes a correctness rationale, parameterized complexity documentation, and tests for invalid input conditions.

Outcome

The resulting system avoids applying an algorithm outside its assumptions. Exact methods are retained where instance sizes permit them, while approximation is used transparently for larger planning tasks. The design also makes operational trade-offs visible: users can request an exact solution for a small problem or a bounded-quality solution under a time limit.

Learning Points

The case demonstrates that algorithm selection is a classification and modeling task. The relevant question is not which paradigm is universally best, but which assumptions describe the problem, which guarantees are required, and what resources are available. It also shows why documenting approximation ratios, randomization behavior, and negative-weight restrictions is part of professional software engineering.

Challenges, Risks, and Common Errors

Several errors recur across paradigms. First, a greedy algorithm is often accepted because it works on a few examples, without proving the greedy-choice property. Second, a DP implementation may use an ambiguous state or an incorrect iteration order, accidentally permitting repeated use of an item. Third, backtracking may prune a branch using a condition that is not necessary for infeasibility. Fourth, branch-and-bound may compare an upper bound and incumbent in the wrong direction. Fifth, randomized performance may be described as guaranteed rather than expected.

Other risks arise from modeling. A change from fractional to integral decisions can change a polynomial greedy problem into an NP-hard one. A negative edge can invalidate Dijkstra’s reasoning. A metric assumption can be necessary for an approximation guarantee. Memory limits may make a theoretically acceptable DP table impractical. Finally, recursion can exhaust the call stack even when its asymptotic analysis is sound.

Professional and Ethical Considerations

Algorithmic choices affect people as well as machines. A randomized or approximate decision procedure should disclose uncertainty and quality limits when it influences finance, transportation, health, employment, or access to services. Reproducibility is important in regulated or safety-critical environments. Data structures and algorithms should be tested for adversarial inputs, denial-of-service risks, and unintended information leakage.

Engineers should not claim optimality when only a heuristic or approximation has been implemented. Complexity guarantees should identify assumptions, and benchmark results should not be presented as universal evidence. In collaborative projects, code review should examine both implementation and proof obligations: an elegant-looking algorithm with an invalid invariant is a technical liability.

Current Directions and Best Practices

Modern systems increasingly combine paradigms. A machine-learning pipeline may use randomized sampling, dynamic programming for sequence alignment, greedy selection for feature construction, and branch-and-bound for constrained search. Parallel hardware favors divide-and-conquer when subproblems can run independently, while memory-locality considerations may favor iterative DP over recursive memoization.

Effective practice includes the following:

• State the problem model and assumptions before choosing an algorithm.
• Separate feasibility, optimization objective, and output reconstruction.
• Write the recurrence, invariant, exchange argument, or bound before coding.
• Measure both time and memory using realistic input distributions.
• Use exact algorithms for small or high-consequence instances and bounded approximations when scale demands them.
• Preserve reproducibility for randomized methods.
• Test adversarial, boundary, malformed, and representative inputs.
• Document guarantees, failure conditions, and parameter dependence.

Chapter Summary

Algorithm design paradigms organize the search for efficient and correct solutions. Divide-and-conquer recursively solves smaller, usually independent instances and combines their answers. Greedy algorithms make irrevocable local choices, but require proofs such as exchange arguments and cut properties. Dynamic programming stores solutions to overlapping subproblems and depends on a precise state, recurrence, and evaluation order. Backtracking explores a solution space while pruning infeasible partial candidates; branch-and-bound adds objective bounds to prune candidates that cannot improve the incumbent. Randomized algorithms use probability to obtain expected performance, robustness, or simpler designs, while approximation algorithms provide efficient solutions with explicit quality guarantees when exact optimization is too costly.

The central professional skill is paradigm selection. Correctness depends on problem assumptions, and complexity depends on both the theoretical model and implementation details. A sound design documents its proof, resource bounds, limitations, and operational consequences rather than treating an algorithm as an isolated code fragment.

Key Terms

Algorithmic paradigm: A general strategy for designing algorithms for a class of problems.

Divide-and-conquer: A method that divides a problem, recursively solves subproblems, and combines their results.

Recurrence: An equation expressing the cost of a recursive algorithm in terms of smaller inputs.

Greedy-choice property: The property that an optimal solution can begin with a locally optimal choice.

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

Exchange argument: A proof technique that replaces part of an optimal solution with a chosen alternative without worsening the result.

Dynamic programming: A method that stores solutions to overlapping subproblems.

Memoization: Top-down dynamic programming using cached recursive results.

Tabulation: Bottom-up dynamic programming using an explicitly constructed table.

State: A compact description of the information needed to solve a DP subproblem.

Backtracking: Systematic construction of candidates with reversal when a partial candidate cannot succeed.

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

Branch-and-bound: Optimization search using bounds on the best possible completion of a partial solution.

Incumbent: The best complete solution currently known in an optimization search.

Las Vegas algorithm: A randomized algorithm that always returns a correct answer but has random running time.

Monte Carlo algorithm: A randomized algorithm with controlled running time and a possible, usually bounded, error probability.

Approximation ratio: A bound relating the value of an approximate solution to the optimum.

Metric TSP: Travelling-salesperson problem with distances satisfying the triangle inequality.

Loop invariant: A property that remains true before and after each iteration of a loop.

Review Questions

Short Answer Questions

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

2. Why does optimal substructure alone not justify a greedy algorithm?

3. Distinguish memoization from tabulation.

4. What is the purpose of a bound in branch-and-bound?

5. Differentiate Las Vegas and Monte Carlo randomized algorithms.

Long Answer Questions

1. Derive and analyze the recurrence for merge sort, and provide a correctness argument.

2. Explain activity selection using the greedy-choice property and an exchange argument.

3. Design a dynamic-programming solution for 0/1 knapsack and explain why capacity is processed in descending order in the one-dimensional version.

4. Compare backtracking and branch-and-bound with respect to feasibility tests, objective bounds, and worst-case complexity.

5. Explain how a minimum-spanning-tree method gives a 2-approximation for metric travelling salesperson tours.

Analytical / Application Questions

1. A proposed greedy solution to 0/1 knapsack works on several test cases. Construct a counterexample or explain what proof would still be required before accepting it.

2. Select an algorithm for a shortest-path system containing nonnegative edges in one deployment and possible negative edges in another. Justify the choice and complexity implications.

3. A branch-and-bound knapsack program explores nearly every node. Analyze two possible causes and propose changes to branching, bounding, or incumbent generation.

22. Multiple Choice Questions with Answers

Question 1

Which condition most directly distinguishes a suitable divide-and-conquer problem from a dynamic-programming problem?

A. The problem uses integer inputs.

B. Its recursive subproblems are largely independent rather than substantially overlapping.

C. Its solution requires a graph.

D. Its implementation uses a loop.

Correct Answer: B. Its recursive subproblems are largely independent rather than substantially overlapping.

Question 2

Why is earliest finish time the safe greedy choice in activity selection?

A. It always has the smallest duration.

B. It maximizes the value of the first activity.

C. Replacing the first activity of an optimum with it does not reduce the remaining available time.

D. It avoids all recursion.

Correct Answer: C. Replacing the first activity of an optimum with it does not reduce the remaining available time.

Question 3

In a one-dimensional 0/1 knapsack DP table, capacities are processed in descending order because this

A. sorts items by value.

B. prevents the current item from being used more than once.

C. reduces the number of items.

D. guarantees a greedy optimum.

Correct Answer: B. prevents the current item from being used more than once.

Question 4

A branch-and-bound algorithm for a maximization problem may safely prune a node when

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

B. its lower bound is positive.

C. its depth is even.

D. its partial solution is feasible.

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

Question 5

Which statement about randomized quicksort is correct?

A. Random pivoting eliminates the worst-case input entirely.

B. It always runs in linear time.

C. It can provide expected O(n log n) time while retaining a possible O(n²) outcome.

D. It cannot sort duplicate values.

Correct Answer: C. It can provide expected O(n log n) time while retaining a possible O(n²) outcome.

Question 6

What makes a fractional-knapsack ratio strategy valid but generally invalid for 0/1 knapsack?

A. Fractional items permit exchange of portions, whereas integral choices may make local ratios globally unsuitable.

B. 0/1 knapsack has no objective function.

C. Fractional knapsack cannot be sorted.

D. The 0/1 version always has negative weights.

Correct Answer: A. Fractional items permit exchange of portions, whereas integral choices may make local ratios globally unsuitable.

Question 7

Which proof technique is most naturally associated with a greedy algorithm?

A. Exchange argument

B. Pointer alias analysis

C. Random seed replay

D. Stack unwinding

Correct Answer: A. Exchange argument

Question 8

For Dijkstra’s algorithm, a negative edge is problematic because it can

A. make the graph disconnected.

B. invalidate the claim that the currently smallest tentative distance is final.

C. prevent use of a priority queue.

D. increase the number of vertices.

Correct Answer: B. invalidate the claim that the currently smallest tentative distance is final.

Question 9

What does an approximation ratio for a minimization problem usually express?

A. The probability that the algorithm fails.

B. The number of recursive calls.

C. An upper bound on the algorithm’s cost relative to the optimum.

D. The amount of auxiliary memory only.

Correct Answer: C. An upper bound on the algorithm’s cost relative to the optimum.

Question 10

Which implementation issue is especially important in backtracking?

A. The undo operation must restore the exact state before the recursive branch.

B. Every branch must be explored even when infeasible.

C. The algorithm must always use a hash table.

D. The recursion must have no base case.

Correct Answer: A. The undo operation must restore the exact state before the recursive branch.