An algorithm design technique is a way to organize a proof as well as a way to organize a computation. A greedy algorithm needs a reason one local choice can be committed permanently. Divide and conquer needs independent smaller problems and a correct combination step. Dynamic programming needs subproblem values that retain all information needed by later decisions. Learning those obligations is more useful than memorizing a list of algorithm names.
Motivation
Suppose a single room can host one activity at a time. Each activity has a starting and finishing time. If every activity is equally valuable, choosing an activity that finishes soon seems sensible because it leaves more of the future available. If activities have different values, however, one short low-value activity can block a much more valuable one. The input objects barely changed, but the objective changed enough to invalidate the greedy proof.
Weighted scheduling will lead to dynamic programming. Sorting activities by finishing time reveals a useful boundary: after choosing an activity, every compatible earlier activity lies in a particular prefix of the sorted list. A subproblem can therefore be summarized by one prefix index. Without identifying that sufficient state, “try dynamic programming” is merely a slogan.
Sorting itself provides a divide-and-conquer example. We can sort two halves independently and merge their sorted outputs. The central proof is not that each recursive call is smaller; that establishes termination. Correctness additionally needs a merge invariant showing that each selected next element really is the next element in the total sorted order.
Definitions
Definition 3.1.1
(Activities, compatibility and the two objectives)
An activity occupies a half-open interval with . Finishing exactly when another activity starts is allowed. Two activities are compatible when their intervals do not overlap. The unweighted scheduling problem maximizes the number selected; the weighted version assigns nonnegative integer weights and maximizes the sum of selected weights. The empty selection is always feasible.
Definition 3.1.2
(Predecessor index and the prefix optimum)
Sort the activities so , breaking ties by any fixed rule. For weighted scheduling define as the largest index with , or zero if none exists. Since , every compatible earlier activity belongs to the prefix ending at . Let be the maximum weight obtainable using only activities , with .
Definition 3.1.3
(Optimal substructure)
A subproblem has optimal substructure when an optimal solution of the larger problem uses optimal solutions of the relevant smaller problems, after fixing the surrounding choice. This property needs proof: replacing a smaller solution must preserve feasibility and improve the global objective if the smaller solution was inferior.
Definition 3.1.4
(Comparison sorting and the operation count)
A comparison sorting algorithm learns order by comparing input keys. For the lower bound below, the keys are distinct and all permutations are permitted. For the stated upper bounds, a comparison or an elementary arithmetic operation is counted as one operation. Bit complexity can require additional factors when numbers grow or input coordinates have long encodings.
Theorem/proposition
Theorem 3.1.5
(Earliest finishing time is optimal for unweighted scheduling)
Repeatedly choose an activity of earliest finishing time among the activities compatible with the choices already made. The resulting compatible set has maximum cardinality. This theorem concerns the unweighted objective and half-open intervals with strictly positive length.
Theorem 3.1.6
(Weighted scheduling recurrence)
For ,
After sorting and finding all predecessor indices, the table is computable in increasing order and an optimal set can be reconstructed by following the maximizing choices.
The distinction is the commitment. Greedy permanently chooses a first activity because an exchange argument proves that some optimum shares that choice. Dynamic programming keeps both the include and exclude possibilities until their best achievable values have been compared. It does not enumerate every selection explicitly, because many choices ask for the same smaller-prefix optimum.
Proposition 3.1.7
(Merge sort is correct and uses comparisons)
Merge sort returns a sorted rearrangement of its input and performs comparisons on keys. An array implementation uses extra storage.
Theorem 3.1.8
(Comparison sorting needs comparisons)
Every deterministic comparison sorting algorithm that is correct on all orderings of distinct keys makes at least comparisons on some input, and .
Proof sketch or proof idea
Proof
(Exchange the first activity of an optimum)
Let be a globally earliest-finishing activity, and take an optimal unweighted schedule ordered chronologically. If it is nonempty, call its first activity . Replace by . Since , every later activity, whose start is at least , remains compatible with . No earlier activity needs accommodation because was first. The replacement preserves the number selected. Thus an optimum beginning with exists. The remaining activities must start at or after , and the same argument applies recursively to that smaller problem. Each choice removes at least one activity, so the procedure terminates with an optimum. Empty instances are immediate.
Proof X-ray
Where the exchange argument uses its hypotheses
The key move is to start from an arbitrary optimum and change only its first activity. It is legal for three reasons. Since finishes no later than any activity, , so every later activity of the optimum, which starts at or after , also starts at or after . Half-open intervals matter here: an activity that starts exactly when another finishes is compatible. Strictly positive lengths make "first in chronological order" well defined.
The objective enters in one place only: the swap replaces one activity by one activity, so the count is unchanged. For weights the swap would also need , which nothing guarantees. The argument closes by induction on the number of activities: after committing to , the remaining problem consists of activities starting at or after and has fewer activities, and the optimum found there combined with is optimal for the whole instance.
Proof
(Include or exclude the last activity)
For weighted scheduling, partition feasible schedules in the prefix by whether they include . Those excluding it have maximum value . Those including it can contain only earlier activities finishing by , all lying in the prefix . Their remaining selection can be replaced by an optimum for that prefix without creating overlap. Their maximum value is therefore , and both candidate values are feasible. Taking their maximum proves equality. Since , increasing-index evaluation uses only values already computed.
Proof
(Reconstruction follows the maximizing branch)
To reconstruct, start at . If the exclusion branch attains , move to . Otherwise include and move to . Ties may be resolved either way, provided the selected branch attains the optimum value. The index strictly decreases, so the process terminates. The recurrence ensures that the accumulated selected weight is the original optimum, and every inclusion moves to a compatible prefix. This proves the output set, rather than only its objective value, is correct.
Proof X-ray
Why a small state is enough
The prefix index works because choosing activity restricts earlier choices by one finishing-time boundary. We do not need to remember the entire history of rejected activities. In a different scheduling problem with multiple resources or extra dependencies, a prefix index might discard essential information. A recurrence is justified only after the state has been shown to describe every remaining constraint.
Proof
(Merging preserves a sorted prefix, and levels bound the cost)
For merge sort, split a list into two parts of nearly equal length, recursively sort them, and merge. During merging, maintain that the output is sorted and consists of the smallest elements already removed from the two sorted inputs. The smaller current front is no greater than any remaining element in either input; appending it preserves the invariant. Once one input is exhausted, the rest of the other can be appended in order. Every element is removed once, giving linear merge cost. Induction on list length proves sorting correctness, and smaller recursive inputs prove termination.
At every recursion level, the total lengths of the sublists are at most , and the height is at most before singleton leaves. Linear combination work per level gives operations for . This level argument avoids assuming an exact power-of-two input length. An auxiliary array implementation uses extra storage; a naive implementation that copies data unnecessarily may have different constants and storage behavior.
Proof
(Counting the leaves of a decision tree)
The comparison-model lower bound explains why this cost is significant. There are possible orders of distinct keys. A deterministic binary comparison decision tree must have at least leaves, so some path has length at least . For , at least factors in the factorial are at least , giving an bound as grows. This is a worst-case lower bound for comparison sorting, not for algorithms using additional information such as bounded integer digits.
Worked examples
Worked example 3.1.9
(One input, two objective calculations)
Take activities , , , , with weights . The finishing-time order is already displayed, and the predecessor indices are . The weighted table is , followed by . Backtracking selects , then , then , of total weight seventeen. Earliest-finish greedy also selects here, but their agreement on this example is not a proof that greedy solves the weighted problem.
Counterexample mode
Earliest-finish greedy fails once weights differ
One might expect that a rule proved optimal for counting activities remains optimal for maximizing weight. Take the overlapping activities with weight one and with weight one hundred. Earliest-finish greedy takes , which conflicts with the other, so its value is one. The single activity is feasible with value one hundred. The table agrees: the predecessor indices are , so and . The unweighted exchange proof still preserves cardinality when swapping the first activities, but it does not preserve total weight. The failed proof obligation identifies exactly which theorem ceased to apply. The repaired method is the recurrence, which compares both branches instead of committing.
Worked example 3.1.10
(Merging with an explicit tie convention)
Merge the sorted lists and . Taking the smaller front and choosing the left front on ties gives . If keys carry original positions, choosing the left half on equal keys preserves their original order across halves, so merge sort can be stable. Stability is an additional property beyond sortedness; it should be proved from the tie convention rather than inferred from the word merge.
Worked example 3.1.11
(A tie in the table and a reconstruction)
Take with weight five, with weight five and with weight ten. In finishing-time order, breaking the tie between and by listing first, the activities are . The predecessor indices are , because , and because . Then
The two branches tie at . Reconstruction may take either. Taking exclusion moves to , where exclusion gives , so is included and we move to , where is included: the selected set is of weight ten. Taking inclusion at selects , also of weight ten. Both outputs are optimal, and touch at the boundary point without overlapping, which is the half-open convention at work.
Sorting takes comparisons, and binary searching the sorted finishes finds all in comparisons. The dynamic-programming table and reconstruction then use arithmetic operations and memory entries. If each weight has at most bits, every table value is at most times the maximum weight and needs at most bits. The arithmetic phase is not constant-cost in the bit model. Endpoint comparison costs likewise depend on the representation of times; the operation-count statement should not hide that choice.
Common mistakes
Common mistake
(Optimal substructure is not a greedy proof)
Optimal substructure does not by itself prove that a greedy rule is valid. A dynamic program can use optimal substructure while retaining several possible first choices. Greedy needs the stronger exchange or stays-ahead argument for its specific permanent decision.
Common mistake
(A state that forgets a constraint)
Do not memoize by a state that omits a constraint. For example, a recurrence indexed only by the number of remaining activities generally fails if it forgets which finishing-time boundary has already been imposed. Two subproblems with the same number of activities can have different feasible schedules.
Common mistake
(A recurrence is not yet an efficient algorithm)
The existence of a recurrence also does not ensure an efficient implementation. Direct recursive evaluation of weighted scheduling can revisit the same prefixes many times. A table evaluates each state once. Conversely, a large table with an unproved recurrence can efficiently compute the wrong answer.
Summary
Exchange arguments justify safe greedy commitments. Divide and conquer separates independent smaller inputs and proves the combination step. Dynamic programming identifies sufficient subproblem states, proves a recurrence by exhaustive cases, and avoids repeated evaluation. Correctness, reconstruction, termination and the cost model are distinct parts of an algorithm's explanation.
Exercises
Exercise 3.1.12
(Show that choosing the shortest interval first need not maximize the number of compatible activities.)
Foundation
Solution(3)
- 1
Choose the intervals
Take , and , with lengths , and .
- 2
Run the shortest-first rule
The shortest interval is . It meets in and in , so after choosing it nothing else is compatible. The rule selects one activity.
- 3
Compare with an optimum
The intervals and are compatible, because the first finishes exactly when the second starts. Two activities are possible, so shortest-first is not optimal. Short duration and early finishing time are genuinely different greedy rules; earliest finish would choose and then .
Exercise 3.1.13
(Compute the weighted table for , , with weights . Give an optimal set.)
Core
Solution(3)
- 1
Find the predecessor indices
The finishing times are already sorted as . Then . For , and , so . For , and while , so .
- 2
Fill the table in increasing order
Key step
- 3
Reconstruct an optimal set
At the exclusion branch attains , so move to . There exclusion gives , so include and move to . The optimal set is with weight . The two outer intervals are compatible but have total weight eight, so maximizing cardinality would solve a different objective.
Exercise 3.1.14
(For coin denominations one, three and four, show that repeatedly taking the largest possible coin fails for amount six. Give a correct recurrence for the minimum number of coins.)
Core
Solution(4)
- 1
Run the greedy rule
Greedy takes , then , then : three coins. But uses two coins, so greedy is not optimal for amount six.
- 2
State the recurrence
Key step
Because: Every nonempty solution has a last coin, and removing it leaves a solution of the smaller amount.
- 3
Check the recurrence on small amounts
, , , , , and , matching .
- 4
Justify correctness
Deleting the last coin of an optimum leaves a solution of that must itself be optimal, otherwise replacing it would improve the whole. Conversely, appending to an optimum for is feasible. Positive denominations make every argument smaller, and denomination one guarantees that every amount is reachable.
Quick check
(Explain why the sorting lower bound does not contradict counting sort on integers in .)
Ask what information counting sort uses besides comparisons.
Solution · Answer
Counting sort uses the integer values to index counts and exploits the bounded key universe. Its information is not obtained only through binary comparisons between input keys, so the comparison decision-tree hypothesis does not apply. Its cost includes the universe size, typically , which can be large if is large.