Second training battery: design. Here we work out the four strategies of Module 3 — divide and conquer (03-01), greedy (03-02), dynamic programming (03-03) and backtracking (03-04) — on new RutaBus problems, different from the ones we solved during the course. The classics from Module 4 will serve as reference (you will see more than one reappear in disguise).
How to work through this lesson: in design, looking at the solution too early is especially harmful, because the value of the exercise lies in the exploration time: trying an approach, seeing it fail, changing course. Spend at least 20–30 minutes on each problem with paper and editor before reading the solution. And when you do read it, don't just validate the code: compare your reasoning with the reasoning laid out.
Contents
- Divide and conquer: measuring the disorder of arrivals.
- Greedy: reinforcements for saturation slots (with justification) and transfer passes (with counterexample).
- Dynamic programming: the inspector's optimal fare, with table and reconstruction.
- Backtracking with pruning: line review committees.
- Diagnosis: three mini-problems — which strategy fits each one?
Exercise 1: Measuring the disorder of arrivals (divide and conquer)
Difficulty: medium
L1 buses leave the depot in order: bus 0 first, then bus 1, and so on. The list arrivals contains the instant (in minutes) at which each bus arrived at North Station: arrivals[i] is the arrival of the bus that departed in position i. An overtake is a pair i < j such that arrivals[i] > arrivals[j] (a bus that left earlier arrived later). The number of overtakes measures the "disorder" of the line and is used as a quality indicator.
arrivals = [12, 9, 21, 14, 30, 18]
# overtakes: (0,1) 12>9, (2,3) 21>14, (2,5) 21>18, (4,5) 30>18 -> 4Write count_overtakes(arrivals) in Θ(n log n) using divide and conquer. The brute-force version (comparing all pairs) is Θ(n²), as you already know from exercise 1 in 06-01.
Hint: it is exactly the structure of
merge_sort(04-03). Ask yourself what information about crossed pairs you can get for free at merge time, when both halves are already sorted.
Solution
The key to divide and conquer (03-01) is finding the decomposition: overtakes come in three kinds — both indices in the left half, both in the right half, or crossed (i on the left, j on the right). The first two are handled by the recursion. The crossed ones would be Θ(n²) to count by brute force... unless the halves are sorted: then, during the merge step (04-03), every time we take an element from the right half before one from the left, that right element is smaller than everything remaining on the left, and each of those elements forms an overtake with it.
def count_overtakes(arrivals):
def sort_and_count(v):
if len(v) <= 1:
return v, 0
middle = len(v) // 2
left, left_count = sort_and_count(v[:middle])
right, right_count = sort_and_count(v[middle:])
# Merge while counting crossed pairs
result, crossed = [], 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
crossed += len(left) - i # everything left pending overtakes it
result.extend(left[i:]); result.extend(right[j:])
return result, left_count + right_count + crossed
return sort_and_count(arrivals)[1]
print(count_overtakes([12, 9, 21, 14, 30, 18])) # 4Why it works: when right[j] < left[i], since left is sorted, right[j] is also smaller than left[i+1], ..., left[-1]. That is len(left) - i overtakes counted at a stroke, in O(1). No pair is counted twice (each crossed pair is detected exactly when its right element leaves the merge) and none escapes.
Complexity: the recurrence is the same as merge_sort's, T(n) = 2T(n/2) + Θ(n), which we already solved in 04-03: Θ(n log n). Auxiliary space is Θ(n) for the merge lists.
Common mistakes: (1) counting only adjacent out-of-order pairs — a vector can have 1 adjacent disorder and n²/4 total overtakes; (2) adding len(left) - i in the wrong branch (when the left element leaves there is no overtake); (3) counting but not returning the sorted list, so the halves are never sorted and the crossed count is wrong.
Exercise 2: Reinforcements and passes (greedy: when yes and when no)
Difficulty: medium
Two independent problems; in one, greedy is correct and you must justify it; in the other it is incorrect and you must give a counterexample. Start from the assumption that you don't know which is which.
Part A — Reinforcement slots. The monitoring system produces the sorted list of minutes of the day when L2 was saturated, e.g. critical = [485, 490, 510, 545, 700, 715] (minutes since midnight). A reinforcement bus covers exactly 30 minutes from its start time: if it joins at minute t, it covers [t, t+30]. Design an algorithm that computes the minimum number of reinforcements (and their times) so that every critical minute is covered.
Part B — Transfer passes. A user will make exactly 8 trips this month. Fares: single ticket €2.00; 5-trip pass €6.00 (€1.20/trip); 8-trip pass €10.40 (€1.30/trip). A colleague proposes this greedy: "always buy the ticket type with the lowest price per trip among those that do not exceed the remaining trips; top up with singles". Is it correct? Justify or refute it.
Solution
Part A — greedy is correct. Strategy: walk through the critical minutes in order; when you find one not yet covered, start a reinforcement exactly at that minute (as late as possible while still covering it), and skip all the critical minutes that fall inside its window.
def plan_reinforcements(critical):
reinforcements = []
coverage_end = float("-inf")
for m in critical: # critical comes sorted
if m > coverage_end:
reinforcements.append(m) # bus joining at minute m
coverage_end = m + 30
return reinforcements
print(plan_reinforcements([485, 490, 510, 545, 700, 715]))
# [485, 545, 700] -> 3 reinforcements: they cover [485,515], [545,575], [700,730]Justification (exchange argument, as in 03-02): let m₁ be the first critical minute. Every valid solution has some bus with start t ≤ m₁ (someone must cover m₁). If in that solution we replace that bus with one starting exactly at m₁, its window [m₁, m₁+30] covers everything [t, t+30] covered among the critical minutes (there are no critical minutes before m₁, and the window shifts to the right, where the rest are). The solution remains valid and of the same size. Repeating the argument with the next uncovered critical minute, any optimal solution transforms into the greedy one without adding buses: the greedy is optimal. Cost: Θ(n) if the list comes sorted (Θ(n log n) if it must be sorted).
Part B — greedy is incorrect. We follow the rule with 8 trips: the lowest price per trip is the 5-trip pass (€1.20). We buy it (3 trips remain); neither the 5-trip nor the 8-trip pass "fits" within 3 remaining trips, so we top up with 3 singles.
| Strategy | Purchase | Cost |
|---|---|---|
| Proposed greedy | 5-trip pass + 3 singles | 6.00 + 6.00 = €12.00 |
| Optimal | 8-trip pass | €10.40 |
Counterexample found: the greedy pays €12.00 when the optimum costs €10.40. The failure is the usual one (remember greedy_change in 03-02): the local criterion "best price per trip" cannot see that splitting the purchase forces topping up with the most expensive ticket type. This problem has optimal substructure and overlapping decisions: it is dynamic programming territory, which is exactly what we do in the next exercise.
Common mistake: "I tried the greedy on two examples and it worked, therefore it's correct". Greedy demands a proof (exchange) or a counterexample; favorable examples prove nothing.
Exercise 3: The inspector's optimal fare (dynamic programming)
Difficulty: high
A RutaBus inspector must travel on days days = [1, 2, 4, 5, 6, 9, 10, 11, 12, 20, 21] of the month. Fares: day ticket €2 (covers 1 day), weekly pass €9 (covers 7 consecutive days), monthly pass €28 (covers 30 consecutive days). Using dynamic programming (tabulation, like min_cost_tab in 03-03), design an algorithm that computes the minimum cost to cover all travel days, and reconstructs which ticket types to buy and on which day. Give the subproblem definition, the recurrence, the table and the complexity.
Hint: define the subproblem by calendar day, not by index into the trip list: "minimum cost to cover all travel days up to day d".
Solution
Subproblem: dp[d] = minimum cost to cover all travel days ≤ d, with d from 0 to the last travel day.
Recurrence: if there is no travel on day d, nothing new needs buying: dp[d] = dp[d-1]. If there is, there are three possible decisions, and we keep the cheapest:
- day ticket:
dp[d-1] + 2 - weekly pass ending on d (covers d−6..d):
dp[max(0, d-7)] + 9 - monthly pass ending on d:
dp[max(0, d-30)] + 28
def optimal_fare(days, prices=(2, 9, 28), durations=(1, 7, 30)):
travels = set(days)
last_day = max(days)
dp = [0] * (last_day + 1)
choice = [None] * (last_day + 1) # for reconstruction
for d in range(1, last_day + 1):
if d not in travels:
dp[d] = dp[d - 1]
continue
dp[d] = float("inf")
for price, dur in zip(prices, durations):
cost = dp[max(0, d - dur)] + price
if cost < dp[d]:
dp[d] = cost
choice[d] = (price, dur)
# Backward reconstruction
purchases, d = [], last_day
while d > 0:
if d not in travels:
d -= 1
else:
price, dur = choice[d]
purchases.append((max(1, d - dur + 1), price, dur))
d = max(0, d - dur)
return dp[last_day], list(reversed(purchases))
cost, purchases = optimal_fare([1, 2, 4, 5, 6, 9, 10, 11, 12, 20, 21])
print(cost) # 21
print(purchases) # [(1, 9, 7), (9, 2, 1), (10, 2, 1), (11, 2, 1), (12, 2, 1),
# (20, 2, 1), (21, 2, 1)]Table trace (only the interesting days):
| d | travel? | dp[d] | best decision |
|---|---|---|---|
| 1 | yes | 2 | ticket |
| 2 | yes | 4 | ticket |
| 4 | yes | 6 | ticket |
| 5 | yes | 8 | ticket |
| 6 | yes | 9 | weekly pass (covers days 1–7): dp[0]+9=9 < dp[5]+2=10 |
| 9 | yes | 11 | ticket: dp[8]+2 |
| 10–12 | yes | 13, 15, 17 | tickets |
| 20 | yes | 19 | ticket (the weekly would give dp[13]+9=26) |
| 21 | yes | 21 | ticket |
Result: €21 — a weekly pass covering days 1–7 (€9) plus six day tickets (9, 10, 11, 12, 20, 21). Compare it with the naive alternatives: 11 individual tickets = €22, monthly pass = €28. (On days 10–12 there are ties: four tickets after the weekly pass cost the same as other combinations; the table keeps the first minimal option.)
Complexity: Θ(D · 3) = Θ(D) time and Θ(D) space, with D the last day (here 21). Note that it depends on the calendar, not on the number of trips.
Common mistakes: (1) proposing the greedy "buy the pass if there are ≥ 5 trips in the week" — it fails in borderline configurations, as exercise 2B demonstrated; (2) forgetting the max(0, d - dur) and accessing negative indices (which in Python don't raise an error: they read from the end of the list and silently corrupt the result!); (3) storing only the cost and not the choice, making the reconstruction — which is what the app needs to show the user — impossible, as we insisted with upgrade_knapsack in 03-03.
Exercise 4: Line review committees (backtracking with pruning)
Difficulty: high
Internal audit requires forming a 2-person review committee for each line (L1, L2, L3). Available inspectors: Anna, Bruno, Carla, Diego and Elena. Constraints:
- Nobody may review the line they drive on: Anna drives L1; Bruno and Carla drive L2; Diego drives L3.
- Each inspector may sit on at most 2 committees.
- Elena and Diego have incompatible shifts: they cannot be on the same committee together.
Write form_committees() with backtracking (03-04) that returns a valid assignment (or None), and include at least one pruning that cuts futureless branches before exploring them.
Solution
State space: for each line, choose a pair of inspectors. Without constraints there would be C(5,2)³ = 10³ = 1000 combinations; the constraints and the pruning reduce it drastically.
from itertools import combinations
INSPECTORS = ["Anna", "Bruno", "Carla", "Diego", "Elena"]
DRIVES = {"Anna": "L1", "Bruno": "L2", "Carla": "L2", "Diego": "L3"}
LINES = ["L1", "L2", "L3"]
MAX_COMMITTEES = 2
def form_committees():
usage = {r: 0 for r in INSPECTORS}
assignment = {}
def is_valid(line, pair):
for r in pair:
if DRIVES.get(r) == line: # constraint 1
return False
if usage[r] >= MAX_COMMITTEES: # constraint 2
return False
if "Elena" in pair and "Diego" in pair: # constraint 3
return False
return True
def solve(i):
if i == len(LINES):
return True # all lines covered
# Capacity PRUNING: seats still needed vs. remaining capacity
seats_pending = 2 * (len(LINES) - i)
capacity = sum(MAX_COMMITTEES - usage[r] for r in INSPECTORS)
if capacity < seats_pending:
return False # futureless branch: cut now
line = LINES[i]
for pair in combinations(INSPECTORS, 2):
if is_valid(line, pair):
assignment[line] = pair # choose
for r in pair:
usage[r] += 1
if solve(i + 1):
return True
for r in pair: # undo (backtrack)
usage[r] -= 1
del assignment[line]
return False
return dict(assignment) if solve(0) else None
print(form_committees())
# {'L1': ('Bruno', 'Carla'), 'L2': ('Anna', 'Diego'), 'L3': ('Anna', 'Bruno')}Reasoning: the skeleton is the choose → recurse → undo pattern from 03-04 (identical in spirit to assign_shifts). The is_valid check is the constraint pruning: it discards the pair before descending a level. The capacity pruning is more interesting: if 2 lines remain to cover (4 seats) but among all inspectors only capacity for 3 participations remains, no future combination can work — we cut without enumerating the ~100 nodes of that subtree. It is the same principle as the N-Queens pruning: detect the impossibility as early as possible.
A valid solution the algorithm finds: L1 = {Bruno, Carla} (both drive L2, so they may review L1), L2 = {Anna, Diego}, L3 = {Anna, Bruno} — Anna and Bruno end up with 2 committees (right at the limit), Diego never shares a committee with Elena, and nobody reviews their own line.
Complexity: the theoretical worst case is still exponential in the number of lines — O(C(r,2)^L) —, like all backtracking; prunings don't change the worst case, they change the actual case. That's why we insisted in 03-04: backtracking without pruning is brute force by another name.
Common mistakes: (1) forgetting to undo usage[r] -= 1 when backtracking — the state becomes corrupt and the algorithm declares solvable cases impossible; (2) validating the complete assignment only at the end (at i == len(LINES)) instead of pruning at each level: correct but exponentially slower; (3) mutating assignment and returning it without copying, so the later del can empty the result.
Exercise 5: Diagnosis — which strategy fits?
Difficulty: medium
For each mini-problem, decide which design strategy you would use (divide and conquer, greedy, dynamic programming or backtracking) and justify in 3–5 lines why, leaning on the comparison table at the end of 03-04. Nothing needs implementing: this exercise trains diagnosis, which in professional practice is the hard part.
A) RutaBus has 6 reserve vehicles to distribute among L1, L2 and L3. An empirical table says how many extra passengers each line captures depending on how many vehicles it receives (the returns are not proportional: on L1, 1 vehicle brings 300 passengers but 2 bring only 380; on L3, 1 brings 100 and 3 bring 900). The 6 vehicles must be distributed maximizing the total extra passengers.
B) The sales department has n advertising requests for the Main Square bus shelter, each with a start and end date, all paying the same. The maximum number of requests must be accepted without overlaps.
C) The auditor's quarterly visit to 8 specific stops must be planned, honoring precedences ("Central Hospital before River Park") and time windows per stop, and all valid plans must be listed so management can choose.
Solution
A) Dynamic programming. Signals: sequential decisions (how many vehicles I give each line), a bounded resource being consumed (the 6 vehicles: it is the "weight" of a knapsack), optimal substructure (the best split between L2 and L3 of what remains does not depend on how I used what was assigned to L1, only on how much) and overlapping subproblems (many paths lead to "3 vehicles left for 2 lines"). Incremental greedy ("give each vehicle to the line that improves most") fails precisely because the returns are not concave: on L3 the third vehicle contributes more than the first, and the greedy never gets to see it. It is the knapsack of upgrade_knapsack (03-03) disguised as a distribution problem.
B) Greedy. It is activity selection (03-02, assign_trips): intervals, all of equal value, maximize how many fit without overlapping. The criterion "always accept the request that ends earliest among the compatible ones" has an optimality proof by exchange. No DP is needed (there are no distinct weights or values forcing comparison of combinations) nor backtracking (we don't want all solutions, just one optimal one, and greedy finds it in Θ(n log n)).
C) Backtracking. Unmistakable signals: combined constraints (precedences + windows), and above all the requirement to enumerate all valid solutions — greedy and DP produce one (optimal) solution, not a catalog. The state space is the permutations of 8 stops (8! = 40,320), unmanageable with pure brute force if it grows, but very prunable: as soon as a partial plan violates a precedence or a window, the whole branch is cut, as in inspection_routes (03-04).
Common mistake in diagnosis: choosing the strategy by the problem's domain ("it's about intervals, therefore greedy") instead of by its properties (safe local choice? overlapping subproblems? need to enumerate?). B is greedy and A is DP, and both could be described as "distributing resources": what decides is the structure, not the wording.
Conclusion
You have designed from scratch with the four strategies: divide and conquer exploiting merge_sort's merge to count overtakes in Θ(n log n); greedy with the two faces it always has — proof by exchange when it works, counterexample when it doesn't —; dynamic programming with subproblem, recurrence, table and reconstruction for the inspector's fares; and backtracking with constraint and capacity prunings for the committees. And, perhaps most importantly, you have practiced diagnosis: looking at a new problem and recognizing which strategy it calls for, which is the skill that actually gets used in daily work.
With analysis (06-01) and design (this lesson) trained, the third muscle of the course remains: in the next lesson we will practice optimization — taking slow, realistic RutaBus code and applying, with discipline, the method of Module 5.