Design techniques: greedy, dynamic programming, divide-and-conquer

Algorithm design paradigms

Definition. A design paradigm is a reusable way to structure an algorithm around problem properties. Divide-and-conquer splits into independent smaller problems; greedy algorithms commit to a locally preferred choice; dynamic programming stores answers to overlapping subproblems. Correctness depends on proving the paradigm's required properties.

Example. Merge sort divides, solves each half, and merges; activity selection greedily chooses an earliest-finishing activity.

Exam point. Similar-looking problems can require different paradigms because their subproblem structure differs.

Divide-and-conquer structure

Definition. A divide-and-conquer algorithm divides an input into smaller subproblems, solves them recursively, then combines their results. Its recurrence records the number and size of subproblems and combine work. The subproblems should be sufficiently smaller to ensure termination.

Example. Binary search has one half-size subproblem and constant additional work.

Exam point. Include the combine cost, even if the recursive calls are straightforward.

Binary search as divide-and-conquer

Definition. Binary search compares a key to the middle element and recursively searches one half of a sorted random-access sequence. Its recurrence is $T(n)=T(n/2)+Θ(1)$, giving Θ(log n) time. The sortedness precondition is essential.

Example. Searching a middle value terminates in one comparison.

Exam point. A linked list does not provide constant-time midpoint access, so the standard array complexity does not transfer directly.

Solved trace. Search for 26 in [3,8,12,17,21,26,30,35,40] using inclusive bounds.

1. low=0,high=8,mid=4; value 21. Search right half, low=5.
2. low=5,high=8,mid=6; value 30. Search left, high=5.
3. low=5,high=5,mid=5; value 26. Found. Answer. Index 5 in three comparisons.

Merge sort recurrence and trace

Definition. Merge sort on n items makes two calls on size n/2 and does Θ(n) merge work. The recurrence $T(n)=2T(n/2)+Θ(n)$ solves to Θ(n log n). Its array implementation uses linear auxiliary storage and is stable with a tie rule favoring the left run.

Example. Sorting [7,2,5,1] recursively sorts [7,2] and [5,1], then merges.

Exam point. The recursion tree has Θ(log n) levels, each with Θ(n) total merge work.

Solved trace. Merge-sort [7,3,6,2,5,1].

1. Split into [7,3,6] and [2,5,1].
2. Sort left: [7] and [3,6]; merge [3,6], then [3,6,7].
3. Sort right: [2] and [5,1]; merge [1,5], then [1,2,5].
4. Merge [3,6,7] with [1,2,5]: take 1,2,3,5,6,7. Answer. [1,2,3,5,6,7].

Quicksort partition analysis

Definition. Quicksort's partition step places a pivot in its final position and separates keys according to a comparison rule. If partitions have sizes near n/2, the recurrence is Θ(n log n); if one side has size n−1 repeatedly, it is Θ(n²). Randomized pivot selection gives expected Θ(n log n) comparisons on distinct keys under the standard random-permutation model.

Example. An already sorted input with last-element pivot can produce maximally unbalanced partitions.

Exam point. State pivot rule and key distribution when giving expected or worst-case bounds.

Solved recurrence. For balanced quicksort, solve $T(n)=2T(n/2)+cn$.

1. At each level, total partition work is cn.
2. There are $\log_2n$ levels before constant-size subarrays.
3. Leaves contribute Θ(n) total. Answer. Θ(n log n).

Greedy algorithm structure

Definition. A greedy algorithm builds a solution one choice at a time using a local criterion. It is correct only when a greedy-choice property and suitable optimal substructure hold. A plausible local rule is not a proof; counterexamples can disprove it.

Example. Choosing the earliest finishing compatible activity leaves the most room for later activities.

Exam point. Prove why an optimal solution can be transformed to include the greedy choice.

Activity selection

Definition. Given activities with start and finish times, choose a maximum-size subset of mutually nonoverlapping activities. With activities sorted by nondecreasing finish time, repeatedly select the first activity whose start is at least the finish of the last selected activity. This rule is optimal for the unweighted maximum-cardinality version.

Example. For intervals [1,3] and [3,5], both can be selected if touching endpoints are allowed.

Exam point. The algorithm changes if activities have weights or if endpoints conflict by convention.

Solved trace. Activities are A(1,4), B(3,5), C(0,6), D(5,7), E(8,9), F(5,9). Sort by finish and choose greedily.

1. Finish order is A(1,4), B(3,5), C(0,6), D(5,7), E(8,9), F(5,9).
2. Select A first; last finish=4.
3. B and C start before 4, so skip them.
4. D starts at 5≥4, select; last finish=7.
5. E starts at 8≥7, select; F starts at 5<7, skip. Answer. Select A,D,E: three activities.

Greedy proof by exchange argument

Definition. An exchange argument proves a greedy choice safe by taking an optimal solution and replacing one of its choices with the greedy choice without making the solution worse. Repeating this argument shows the greedy prefix can be extended to an optimal full solution. The replacement must preserve feasibility.

Example. In activity selection, replace the first activity of an optimal schedule with the earliest-finishing activity; it finishes no later.

Exam point. Show both feasibility and no loss of objective value after the exchange.

Solved proof sketch. Why is selecting the earliest-finishing activity safe in maximum-cardinality activity selection?

1. Let g be the activity with earliest finish and let O be an optimal schedule whose first selected activity is x.
2. Since g finishes no later than x, any activity compatible after x also starts after g finishes.
3. Replace x by g; all later activities remain compatible and count is unchanged.
4. Thus some optimal solution begins with g; solve the remaining compatible suffix recursively. Answer. Earliest finish preserves feasibility and leaves at least as much remaining time.

Fractional knapsack

Definition. Fractional knapsack allows taking any fraction of an item. For positive weights and values, sort by value-to-weight ratio and take items in descending ratio until capacity is filled; this is optimal because any lower-ratio mass can be exchanged for higher-ratio mass. The rule is not valid for 0/1 knapsack.

Example. If capacity remains 2 and an item weighs 5, take 2/5 of it.

Exam point. Verify that fractions are allowed before using the ratio greedy rule.

Solved calculation. Capacity 20; items (weight,value) are A(10,60), B(15,75), C(5,30). Find maximum fractional value.

1. Ratios: A=6, B=5, C=6.
2. Take A fully: weight 10, value 60; remaining capacity 10.
3. Take C fully: weight 5, value 30; remaining capacity 5.
4. Take 5/15 of B: value $75(1/3)=25$.
5. Total value is 115. Answer. 115.

Why the ratio rule fails for 0/1 knapsack

Definition. In 0/1 knapsack, each item is either taken whole or omitted. A high value/weight ratio does not guarantee the best combination because a fractional remainder cannot be used. Dynamic programming or another exact method is needed for the general problem.

Example. Capacity 10; items (6,30),(5,24),(5,24). Ratio-greedy first takes the 6-weight item for value 30, but the two 5-weight items yield 48.

Exam point. Do not transfer the fractional-knapsack proof to indivisible items.

Solved comparison. Capacity 10 and items A(6,30), B(5,24), C(5,24). Compare ratio-greedy and optimum.

1. Ratios: A=5, B=C=4.8, so ratio-greedy takes A and has value 30.
2. A plus either B or C exceeds capacity.
3. B+C weighs 10 and has value 48.
4. No single item exceeds 30, and A cannot pair with another item. Answer. Greedy value 30; optimum 48 from B and C.

Dynamic programming principle

Definition. Dynamic programming (DP) solves problems with overlapping subproblems and optimal substructure by storing subproblem answers. A recurrence defines each state from smaller states; a base case anchors the table. Memoization stores results top-down, while tabulation fills them bottom-up.

Example. Fibonacci values can be computed once each in a bottom-up array.

Exam point. Define state and recurrence before filling a table.

Fibonacci dynamic programming

Definition. With $F_0=0,F_1=1$, each value satisfies $F_i=F_{i-1}+F_{i-2}$ for i≥2. Bottom-up computation takes Θ(n) additions and Θ(n) space; retaining only two previous values reduces auxiliary space to Θ(1).

Example. F6=8.

Exam point. State whether the table includes F0 and how indexing is defined.

Solved table. Compute F0 through F7.