Module 08: Algorithm design

Divide a problem into smaller instances, solve them, then combine. Merge sort satisfies T(n)=2T(n/2)+Θ(n) for balanced splits: each level does linear merge work and there are logarithmically many levels. Binary search solves only one half, so its recurrence is T(n)=T(n/2)+Θ(1). The number of subproblems and combine cost matter; saying 'uses recursion' alone does not identify a growth rate.

A greedy algorithm commits to a locally attractive choice. For maximum-count nonoverlapping intervals, choose earliest finish, then repeat on compatible intervals. An optimal schedule's first interval can be replaced by the earliest-finishing one without delaying any remaining start; this exchange leaves the count unchanged and reduces to the same residual problem. Earliest start lacks that argument: one long early interval can block many short ones. Maximising total interval value is a different problem and generally needs more than this rule.

Backtracking extends a partial solution, rejects impossible branches and undoes a choice before trying alternatives. For subsets of n items, there are 2^n choices before pruning. A constraint can reduce actual exploration without changing the worst-case exponential bound. Exhaustive search is useful as a small-instance oracle: compare a fast algorithm's answer with all feasible possibilities. Pruning must be justified; rejecting a merely unattractive partial choice can lose the optimum.

Dynamic programming reuses overlapping subproblem answers. For minimum coin count, define best[v] as the minimum count for amount v. Base best[0]=0; impossible states are infinity. Transition best[v]=min(best[v−c]+1) over positive coins c≤v. Compute increasing v so dependencies are ready. With k coin types and target A, time is O(kA), storage O(A). This is pseudo-polynomial in numeric A, not polynomial in the bit length of A. Greedy largest-coin-first fails for [1,3,4] at six: 4+1+1 loses to 3+3.

An optimum value alone may not tell the user what to do. Store the chosen predecessor at each improved state, then walk backwards to reconstruct decisions. Check feasibility independently: coin totals must equal the amount; intervals must not overlap. For a small case, compare optimality with exhaustive enumeration. This distinguishes implementation defects from a wrong recurrence. Specify unreachable and empty outcomes explicitly: amount zero has an empty valid solution, while an impossible positive amount has no solution.

Download each script and run it in a terminal with Python 3.11 or later: python m08_greedy.py. On Windows, py -3 is an alternative; on some systems use python3. The labs use only the standard library. Predict the result before running, then complete the variations. Run without -O so assertions remain enabled. Outputs below were captured by the builder. Code and output are identical in both language editions.

Maximise the count of compatible half-open intervals. Adjacent endpoints may touch. Exhaustive search checks this small instance.

Download m08_greedy.py

"""Earliest-finish interval scheduling, checked against exhaustive search."""
from itertools import combinations
def compatible(intervals):
    ordered = sorted(intervals)
    return all(a[1] <= b[0] for a, b in zip(ordered, ordered[1:]))
def schedule(intervals):
    result, end = [], float("-inf")
    for start, finish in sorted(intervals, key=lambda item: item[1]):
        if start >= finish:
            raise ValueError("nonempty intervals required")
        if start >= end:
            result.append((start, finish)); end = finish
    return result

jobs = [(0, 4), (1, 2), (2, 3), (3, 5), (4, 6)]
chosen = schedule(jobs)
optimal = max(len(subset) for size in range(len(jobs)+1) for subset in combinations(jobs, size) if compatible(subset))
print("chosen:", chosen, "optimal count:", optimal)
assert len(chosen) == optimal == 3
assert schedule([]) == []

chosen: [(1, 2), (2, 3), (3, 5)] optimal count: 3

1. Choose earliest start instead and construct a failure.
2. Add a zero-duration job and explain rejection.
3. Attach values to jobs and explain why the oracle must change.

Inspect every state for amount six and reconstruct the selected coins. Infinity marks unreachable states.

Download m08_dynamic.py

"""Minimum coin count with reconstruction; impossible values return None."""
def min_coins(coins, amount):
    if amount < 0 or any(c <= 0 for c in coins):
        raise ValueError("nonnegative amount and positive coins required")
    best, previous = [0] + [float("inf")] * amount, [None] * (amount + 1)
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and best[value - coin] + 1 < best[value]:
                best[value] = best[value - coin] + 1; previous[value] = coin
    if best[amount] == float("inf"):
        return None
    selected = []
    while amount:
        coin = previous[amount]
        selected.append(coin); amount -= coin
    return selected

for coins, amount in [([1, 3, 4], 6), ([2, 4], 3), ([1, 3, 4], 0)]:
    result = min_coins(coins, amount)
    print(coins, amount, "->", result)
    if result is not None: assert sum(result) == amount
assert min_coins([1, 3, 4], 6) == [3, 3]
assert min_coins([2, 4], 3) is None

[1, 3, 4] 6 -> [3, 3]
[2, 4] 3 -> None
[1, 3, 4] 0 -> []

1. Try [2,5] at amounts 1 and 7.
2. Compare greedy with DP for [1,3,4].
3. Add a count-only version and compare memory responsibilities.

Try before opening the solution. ★ applies an idea; ★★ combines ideas; ★★★ asks for design or proof.

Choose an answer for feedback; reset to retry. A text answer key is available without JavaScript.

• MIT algorithm materials — Read dynamic programming; identify state, base and transition in an example.

For a new optimisation task, define its objective, feasible solutions and state before choosing a strategy. Module 09 investigates the machine that executes these procedures.