Algorithm Design: Greedy, Dynamic Programming and Search

Algorithm design begins before code. A problem must state its input, required output, constraints and the conditions that make an answer valid or optimal. The designer then identifies structure: Can the input be divided? Do the same smaller problems recur? Can a locally best choice be proved safe? Can impossible candidates be rejected early? The answers suggest a design technique.

An algorithm is not selected only by its asymptotic label. Correctness, input size, memory, numeric range, worst-case requirements, ease of implementation and the need to reconstruct a solution all matter. A clear design records its invariant or recurrence and separates the proof of correctness from the analysis of resource use.

Brute Force

Brute force systematically examines candidate solutions or applies the most direct definition. Linear search is a polynomial brute-force scan. Enumerating every subset is an exponential brute-force search and enumerating every permutation has factorial growth.

The technique is useful when inputs are small, when no stronger structure is known and as a correctness reference for a more complex algorithm. A slow exhaustive solver can generate exact answers for small random cases; comparing an optimized solver against it often reveals subtle errors.

A candidate generator must be complete and avoid accidental duplication. If each of n items may be selected or omitted, there are 2^n subsets. If all arrangements of n distinct items matter, there are n! permutations. Polynomial work performed for every candidate multiplies these counts rather than replacing them.

Brute force can still include simple pruning. It stops being pure enumeration when structural rules reject large candidate families, but it remains a useful starting point from which backtracking and branch-and-bound are derived.

Divide and Conquer

Divide and conquer has three stages:

1. Divide an instance into smaller subproblems.
2. Conquer them recursively.
3. Combine their solutions.

Merge sort divides an array in half, sorts both halves and merges them. Binary search chooses only one half and needs almost no combining. Quicksort spends its main work partitioning before recursive calls.

The subproblems are commonly independent. If a size-n problem makes a subproblems of size n/b and performs f(n) other work, its time follows

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

The balance of recursive sizes matters. Merge sort creates balanced halves and runs in Theta(n log n). Quicksort can create extremely unequal parts and take Theta(n²).

Correctness is usually proved by induction: assume recursive calls correctly solve smaller instances, then prove the divide and combine steps produce the correct whole answer. Termination requires every recursive subproblem to be strictly smaller and eventually reach a base case.

Greedy Algorithms

A greedy algorithm builds a solution by repeatedly committing to a locally preferred feasible choice. It normally does not revisit earlier decisions. This can be efficient, but a plausible local rule is not enough; the problem must have a property proving that the choice can be part of an optimal solution.

Two common proof styles are an exchange argument and a stays-ahead argument. An exchange proof takes an optimal solution that differs from the greedy choice and shows how to replace part of it with the greedy choice without worsening the result. Repeating the exchange transforms an optimum into the greedy solution. A stays-ahead proof shows that after every step, the greedy partial solution is at least as good as any competitor under an appropriate measure.

Activity selection is a classic example. To schedule the maximum number of nonoverlapping activities on one resource, choose the compatible activity that finishes earliest. Any optimal schedule’s first activity can be exchanged for this one without reducing the room remaining for later activities.

Fractional knapsack also supports a greedy rule. Items may be divided, so sorting by value per unit weight and taking the highest ratios first is optimal. The same rule is not generally correct for 0/1 knapsack, where an item must be taken whole or omitted.

Coin change exposes the danger of assuming greediness. Choosing the largest coin first works for some denomination systems. With coins 1, 3, 4 and amount 6, greedy takes 4 + 1 + 1, while the optimum is 3 + 3. One counterexample disproves a proposed universal greedy rule.

Prim’s and Kruskal’s algorithms are greedy, with correctness supplied by the cut property. Dijkstra is greedy under nonnegative weights. Each succeeds because of a problem-specific proof, not because local choices are inherently optimal.

Dynamic Programming

Dynamic programming or DP, solves a family of related subproblems and stores their results so each relevant state is evaluated once. It is valuable when the problem has:

• optimal substructure, meaning an optimal solution is composed from optimal solutions of suitable smaller states;
• overlapping subproblems, meaning naive recursion requests the same states repeatedly.

A complete DP design answers five questions:

1. What does each state mean?
2. What recurrence or transition computes it?
3. What are the base cases?
4. In what order are dependencies available?
5. Which state or combination of states is the final answer?

State meaning should be written as a sentence before code. For coin change, dp[a] might mean the minimum number of coins needed to form amount a, with infinity representing an unreachable amount. A transition considers each coin c and uses 1 + dp[a - c] when a ≥ c. A vague state leads to incorrect transitions and initialization.

Memoization and Tabulation

Memoization is top-down. A recursive function computes a requested state and stores its result; a later request returns the cached value. It naturally follows a recurrence and may avoid states that the initial problem never reaches. It retains recursion overhead and call-depth limits.

Tabulation is bottom-up. It fills states iteratively in an order that guarantees dependencies are already available. It avoids recursive frames and often makes memory compression easier, but may compute states that are not needed.

Naive Fibonacci recursion has exponential call growth because it recomputes the same arguments. Memoization or a table reduces time to O(n) and uses O(n) stored results. Since each Fibonacci value depends only on the previous two, an iterative implementation can keep two values and use O(1) auxiliary space.

0/1 Knapsack

For items with weights and values and capacity C, a two-dimensional state dp[i][c] can represent the best value using the first i items within capacity c. The transition either omits item i or, if it fits, takes it and adds its value to a state using earlier items.

Space can be compressed to one dimension. Capacities must then be processed from C downward for each item. Backward iteration reads states from before the current item was used, preventing one item from being counted multiple times. Forward iteration changes the meaning to an unbounded variant in which repeated use is allowed.

DP time is number of states multiplied by work per state. A knapsack bound of O(nC) is pseudo-polynomial because C is a numeric value whose binary representation has only log C digits. This distinction matters when capacities can be very large.

Reconstructing a DP Solution

An optimal value may not be enough. To recover chosen items, edits or path steps, store the decision or predecessor used for each state, then trace backward from the final state. Alternatively, compare neighboring table values to infer decisions. Memory optimization that discards old rows can prevent reconstruction unless additional information is retained.

Backtracking

Backtracking performs depth-first search over partial candidates. It applies a choice, tests whether the partial state remains feasible, recursively explores it and undoes the choice. A branch is pruned when a constraint proves it cannot lead to any valid complete solution.

N-Queens prunes a placement as soon as a queen shares a column or diagonal with an earlier queen. Sudoku prunes digits that violate row, column or box constraints. Generating permutations marks which elements are already used and restores that state after each branch.

Worst-case time is often exponential, but pruning, variable ordering and choice ordering can make realistic instances much smaller. Choose the most constrained variable first to expose failure early. Try promising values first when only one solution is needed. These heuristics change search order and practical cost; correctness still requires that no feasible choice be omitted.

Branch and Bound

Branch and bound searches for an optimal solution. It keeps an incumbent, the best complete solution found so far and computes a bound on the best result any completion of a partial state could achieve. If that optimistic bound cannot beat the incumbent, the branch is discarded.

For minimization, a lower bound estimates the least possible cost from a node. If it is already at least the incumbent cost, the node cannot improve the answer. For maximization, an upper bound plays the symmetric role. A bound must be safe: an invalid bound can prune the branch containing the true optimum. A tighter safe bound prunes more work but may cost more to compute.

Nodes may be explored depth-first to find a feasible incumbent quickly or best-first through a priority queue ordered by bound. Backtracking prunes primarily by feasibility; branch and bound additionally prunes by objective potential.

Randomized and Stochastic Algorithms

A randomized algorithm uses random choices to affect execution. A Las Vegas algorithm always returns a correct result, but its running time is random. Randomized quicksort is an example under the usual model: any pivot sequence still sorts correctly, while expected time is O(n log n).

A Monte Carlo algorithm has a bounded running plan but permits a controlled probability of error. Repetition can often reduce that probability. Claims about correctness or expected time depend on assumptions about random independence and distribution, which should be stated.

Randomization can prevent fixed input patterns from consistently triggering bad behavior, sample huge data and support approximate solutions. It does not eliminate worst cases automatically and predictable generators may be unsuitable against adversarial input.

Selecting a Technique

Start with the simplest exact method that fits the constraints. Use brute force as a baseline when the candidate space is small. Use divide and conquer when subproblems are separable and combining is efficient. Consider greedy design when a safe-choice proof is available. Use DP when a compact state captures overlapping subproblems. Use backtracking for constraint satisfaction and branch and bound for exact optimization with meaningful bounds.

Sometimes techniques combine. A divide-and-conquer routine may use insertion sort on small subarrays. A branch-and-bound solver may use a greedy heuristic to find an early incumbent and a DP relaxation to compute bounds. A graph algorithm may use a priority queue and union–find as supporting data structures.

Analysis and Verification

Analyze best, average and worst cases only when their input models are defined. Account for time, auxiliary space, output size, recursion depth, preprocessing and numeric representation. An algorithm that reports all k solutions necessarily spends at least Omega(k) output work.

Prove loop invariants, induction steps, greedy exchanges or DP recurrences before relying on examples. Then test base cases, unreachable states, ties, overflow boundaries and adversarial arrangements. For optimization, verify feasibility independently and compare small instances with exhaustive search. Store enough predecessor information when the required result includes an actual solution rather than only its value.

Algorithm design is the process of matching problem structure with a justified method. The strongest solution is one whose state, choices, invariants, correctness argument and complexity all describe the same computation.