Up to here you have trained each muscle separately: analysis (06-01), design (06-02) and optimization (06-03). The three projects in this lesson use them all at once: they are complete pieces of RutaBus, end to end, like the ones you would build on a real team.
How to work through this lesson: each project comes with context, requirements, a phased plan (with the course module each phase applies), a starter skeleton and a self-assessment checklist. Implement the whole project before looking at the reference solution, and use the checklist as the criterion for "done". The reference solution is not "the" solution: it is one correct, reasoned solution to contrast yours against. If your approach differs but meets the checklist, it is just as valid.
Contents
- Project 1: Trip planner (M4 + M2).
- Project 2: Fleet dashboard (M2 + M4 + M5).
- Project 3: Shift and reinforcement planner (M3).
- Course conclusion.
Project 1: Trip planner
Difficulty: medium · Integrates: Module 4 (Dijkstra, Floyd-Warshall) + Module 2 (analysis to decide).
Context. The RutaBus app needs to answer "how do I get from A to B?" while accounting for transfers: changing lines at a stop costs 5 minutes. The network:
- L1: Main Square —3— North Station —4— Central Hospital —6— River Park
- L2: North Station —5— Old Market —4— University —3— River Park
- L3: Main Square —7— University —4— South Sports Center
(the numbers are minutes between consecutive stops; all lines run in both directions).
Functional requirements.
- Model the network as a weighted graph that captures the transfers.
best_trip(origin, destination): total minutes and the complete itinerary (stops and line changes).- Precompute the all-pairs time table with Floyd-Warshall.
- Decide, with complexity arguments, which approach the app should use in production.
Phased plan.
| Phase | Task | Applies |
|---|---|---|
| 1 | Model: the trick is that the node is not the stop, but the pair (stop, line) | 01-02, 05-02 (dict vs matrix) |
| 2 | Dijkstra with heap + path reconstruction | 04-05 |
| 3 | Floyd-Warshall over the same nodes | 04-06 |
| 4 | Compare cost/memory of both and decide | M2, 05-01 |
Starter skeleton.
import heapq
LINES = {
"L1": [("Main Square", 3), ("North Station", 4),
("Central Hospital", 6), ("River Park", 0)],
"L2": [("North Station", 5), ("Old Market", 4),
("University", 3), ("River Park", 0)],
"L3": [("Main Square", 7), ("University", 4), ("South Sports Center", 0)],
}
TRANSFER = 5 # minutes for changing lines at the same stop
def build_network():
"""Returns an adjacency dict: {(stop, line): {(stop, line): minutes}}."""
# TODO: edges between consecutive stops of each line (both directions)
# TODO: transfer edges between the lines that share a stop
def best_trip(network, origin, destination):
"""Returns (minutes, [(stop, line), ...]) or None if there is no path."""
# TODO: multi-source Dijkstra (the traveler starts at the stop, on any line)
def floyd_warshall(network):
"""Returns (nodes, matrix) with the all-pairs minimum times."""
# TODOSelf-assessment checklist.
- [ ] A trip without a transfer beats one with a transfer when the minutes justify it (Main Square → University must give 7 min via L3, not 17 via L1+L2).
- [ ] The returned itinerary shows where the line change happens.
- [ ] Dijkstra uses a heap and does not revisit settled nodes (04-05).
- [ ] Floyd-Warshall and Dijkstra give the same times for all pairs (test it with a loop!).
- [ ] The final decision cites concrete complexities, not impressions.
Reference solution
Phase 1 — Modeling. If the node were just the stop, there would be no way to charge for the transfer: the graph wouldn't know which line you "are on". The standard solution is to split: the node is (stop, line), with travel edges within each line and transfer edges (5 min) between the lines that share a stop.
from collections import defaultdict
def build_network():
network = defaultdict(dict)
for line, stops in LINES.items():
for (s1, w), (s2, _) in zip(stops, stops[1:]):
network[(s1, line)][(s2, line)] = w # outbound
network[(s2, line)][(s1, line)] = w # return
by_stop = defaultdict(list)
for node in list(network):
by_stop[node[0]].append(node)
for nodes in by_stop.values(): # transfers
for a in nodes:
for b in nodes:
if a != b:
network[a][b] = TRANSFER
return dict(network)We choose an adjacency dict and not a matrix because the network is sparse: each node has 2–4 neighbors, and as we saw in 05-02, the matrix only pays off in dense graphs.
Phase 2 — Dijkstra with reconstruction. An important detail: the traveler starts "at the stop", with no line assigned. Instead of inventing a virtual node, we seed the heap with every node (origin, line) at distance 0 (multi-source Dijkstra: same algorithm, several seeds):
def best_trip(network, origin, destination):
starts = [n for n in network if n[0] == origin]
dist = {n: 0 for n in starts}
previous = {n: None for n in starts}
heap = [(0, n) for n in starts]
heapq.heapify(heap)
settled = set()
while heap:
d, node = heapq.heappop(heap)
if node in settled:
continue
settled.add(node)
if node[0] == destination: # first time we settle
path = [] # the destination: it is optimal
while node is not None: # (weights >= 0, 04-05)
path.append(node)
node = previous[node]
return d, list(reversed(path))
for neighbor, w in network[node].items():
nd = d + w
if neighbor not in dist or nd < dist[neighbor]:
dist[neighbor] = nd
previous[neighbor] = node
heapq.heappush(heap, (nd, neighbor))
return None
network = build_network()
print(best_trip(network, "Main Square", "University"))
# (7, [('Main Square', 'L3'), ('University', 'L3')])
print(best_trip(network, "Central Hospital", "University"))
# (14, [('Central Hospital', 'L1'), ('River Park', 'L1'),
# ('River Park', 'L2'), ('University', 'L2')])Look at the second example: the itinerary makes the transfer visible (River Park L1 → River Park L2, +5 min), and Dijkstra chose to transfer at River Park (6+5+3 = 14) and not at North Station (4+5+5+4 = 18). Being able to stop as soon as the destination is settled is the property from 04-05: with non-negative weights, a settled node already has its definitive distance.
Phase 3 — Floyd-Warshall. Over the same nodes, the version from 04-06:
def floyd_warshall(network):
nodes = list(network)
idx = {n: i for i, n in enumerate(nodes)}
INF = float("inf")
n = len(nodes)
D = [[INF] * n for _ in range(n)]
for i in range(n):
D[i][i] = 0
for a, neighbors in network.items():
for b, w in neighbors.items():
D[idx[a]][idx[b]] = w
for k in range(n):
for i in range(n):
for j in range(n):
if D[i][k] + D[k][j] < D[i][j]:
D[i][j] = D[i][k] + D[k][j]
return nodes, DPhase 4 — Decision. Our network has V = 11 nodes: Floyd-Warshall does 11³ ≈ 1,300 operations and its matrix takes up 121 cells — all trivial. But the app aspires to real urban networks; let's scale with M2's analysis to V ≈ 5,000 nodes (2,000 stops, several lines):
| Approach | Cost | Memory | Query |
|---|---|---|---|
| Precomputed Floyd-Warshall | Θ(V³) ≈ 1.25·10¹¹ ops (minutes or hours) | Θ(V²) ≈ 200 MB | O(1) |
| Dijkstra on demand | — | Θ(V + E) (the graph) | O((V+E) log V) ≈ milliseconds |
Recommendation: Dijkstra on demand. A query in milliseconds is amply fast for a mobile app, the memory is minimal, and — decisively — the network changes (closures, reinforcements): recomputing the whole Θ(V³) for every incident is unviable, whereas Dijkstra always works on the current graph. Floyd-Warshall remains for small, static networks or for offline analysis (e.g. detecting the worst-connected stop pairs in the whole network, where you want the complete table anyway). And if one day queries dominate, the middle road is caching the frequent pairs — measuring first (05-01) will tell whether it is needed.
Project 2: Fleet dashboard
Difficulty: medium-high · Integrates: Module 2 (costs) + Module 4 (merge, top-k) + Module 5 (memory).
Context. At the end of the day, each bus dumps a CSV file of tap records, sorted by time: time;stop;line;amount (e.g. 07:41:03;North Station;L2;1.20). With hundreds of buses and millions of lines per day, operations wants a daily dashboard that currently blows up the server's memory.
Functional requirements.
- Read the files without loading them whole into memory.
- Compute in a single pass: tap records per line, tap records per stop and total revenue.
- Combine the k daily files (each already sorted by time) into a single chronological stream, also without materializing it.
- Get the top-10 stops by number of tap records without sorting all the stops.
- Justify the memory of each piece and the tool you would verify it with.
Phased plan.
| Phase | Task | Applies |
|---|---|---|
| 1 | Ingestion with generators | 05-02 |
| 2 | Streaming aggregates with a dict (O(1) cost per access) | 02-01 |
| 3 | Chronological merge of k sorted streams (merge_k with a heap) | 04-03, 04-05 |
| 4 | Top-k with a heap (and why not quickselect here) | 04-04 |
| 5 | Verification: tracemalloc and timeit |
05-01, 05-02 |
Starter skeleton.
import heapq
def read_tap_records(path):
"""Generator that yields tuples (time, stop, line, amount)."""
# TODO: do not use readlines()
def summary(tap_records):
"""One single pass: (by_line, by_stop, revenue)."""
# TODO
def merge_days(routes, route_out):
"""Merges k files sorted by time into one globally sorted file."""
# TODO: O(k) memory, not O(n)
def top_stops(by_stop, k=10):
"""Top-k stops by tap records, without sorting them all."""
# TODOSelf-assessment checklist.
- [ ]
read_tap_recordscan process a 10 GB file on an 8 GB machine (reason it out; you don't need the file). - [ ]
summarymakes one pass and no access inside the loop is O(n) (review 06-01, exercise 2). - [ ]
merge_dayskeeps at most one record per open file in memory. - [ ]
top_stopsis Θ(p log k), not Θ(p log p). - [ ] You can state the theoretical memory peak of each function and how to confirm it.
Reference solution
Phases 1 and 2 — Ingestion and streaming aggregates.
def read_tap_records(path):
with open(path, encoding="utf-8") as f:
for record in f: # the file is already an iterator
time, stop, line, amount = record.rstrip("\n").split(";")
yield time, stop, line, float(amount)
def summary(tap_records):
by_line, by_stop, revenue = {}, {}, 0.0
for time, stop, line, amount in tap_records:
by_line[line] = by_line.get(line, 0) + 1
by_stop[stop] = by_stop.get(stop, 0) + 1
revenue += amount
return by_line, by_stop, revenueMemory: the generator retains one record at a time (O(1) with respect to the file, 05-02); the accumulators grow with the number of distinct lines and stops (dozens), not with the millions of tap records. Each dict access is O(1) — with lists and in it would be the quadratic disaster of exercise 2 in 06-01. A 10 GB file passes through an 8 GB machine without flinching, because it is never in memory all at once.
Phase 3 — Chronological merge. It is the k-sorted-lists merge from 04-03 (merge_k), with the heap holding the minimum of the k heads. The standard library ships it ready-made, and it accepts lazy iterables:
def merge_days(routes, route_out):
flows = [read_tap_records(r) for r in routes]
with open(route_out, "w", encoding="utf-8") as out:
for time, stop, line, amount in heapq.merge(*flows):
out.write(f"{time};{stop};{line};{amount:.2f}\n")Only k records live in memory (one per stream) plus the heap of size k: O(k), with k = number of buses, no matter if each file measures gigabytes. Time: Θ(n log k) for n total records. This is, literally, the merge phase of the external sorting we sketched in 04-03. (Fixed-width HH:MM:SS times compare fine as strings; if the format were variable, they would have to be converted to a comparable key.) And if an individual file arrived almost sorted but with a straggler? sorted() would repair it in near-linear time thanks to Timsort (04-02/04-03)… at the price of materializing it; for files that fit in memory it is the simple option, for those that don't, external sorting by chunks.
Phase 4 — Top-k.
Θ(p log k) with p stops: for p = 2,000 and k = 10, about 2,000 comparisons against a heap of 10, versus the Θ(p log p) of sorting everything. And quickselect (04-04, k_earliest)? It is Θ(p) on average, asymptotically better… but it demands the complete list in memory and reorderable, it does not return the top sorted, and its worst case is Θ(p²). With small p and lazy streams, the heap is the natural tool; quickselect shines when p is huge, already in memory, and k is large.
Phase 5 — Verification. Theoretical memory peak: read_tap_records O(1), summary O(lines + distinct stops), merge_days O(k), top_stops O(k). Confirmation: tracemalloc around each phase with a synthetic file (05-02) and timeit for the times (05-01). If the real peak does not match the theoretical one, there is almost always a treacherous list(...) or sorted(...) materializing a generator — the number-one silent mistake in this style of code.
Project 3: Shift and reinforcement planner
Difficulty: high · Integrates: all of Module 3 (backtracking, greedy with justification, DP with reconstruction).
Context. Operations plans Saturday: cover the driver shifts, serve the saturation slots with the only reinforcement bus available, and decide which infrastructure upgrades to spend the annual budget on.
Functional requirements.
- Shifts: assign a driver to each of the 6 shifts (L1/L2/L3 × morning/night). Availability: Anna (morning and night), Bruno (morning only), Carla (night only), Diego (morning and night). A maximum of 2 shifts per driver and, due to mandatory rest, nobody may do morning and night on the same day. Backtracking with at least one pruning.
- Reinforcements: given the forecast saturation slots
[(9, 11), (10, 12), (11, 13), (14, 15), (15, 17), (16, 18)](hours), choose the maximum number of slots the reinforcement bus can cover without overlapping, justifying that the chosen criterion is optimal. - Budget: with €10k, choose among a new bus shelter (€3k, benefit 4), information screens (€4k, benefit 5), wifi at stops (€2k, benefit 3) and a reserved lane (€7k, benefit 9), maximizing benefit. DP with a table and reconstruction of which upgrades to buy. Check whether the greedy by benefit/cost ratio would have gotten it right.
Phased plan.
| Phase | Task | Applies |
|---|---|---|
| 1 | Shifts: choose → recurse → undo, with capacity pruning | 03-04 |
| 2 | Reinforcements: greedy criterion + exchange argument | 03-02 |
| 3 | Budget: 0/1 knapsack with table and reconstruction | 03-03 |
Starter skeleton.
SHIFTS = [("L1", "Morning"), ("L1", "Night"), ("L2", "Morning"),
("L2", "Night"), ("L3", "Morning"), ("L3", "Night")]
AVAILABILITY = {"Anna": {"Morning", "Night"}, "Bruno": {"Morning"},
"Carla": {"Night"}, "Diego": {"Morning", "Night"}}
def assign_shifts():
"""Dict shift -> driver, or None if there is no valid assignment."""
# TODO: backtracking with pruning
def cover_slots(slots):
"""Maximum set of non-overlapping slots for the reinforcement bus."""
# TODO: justified greedy
def upgrade_plan(upgrades, budget):
"""(max_benefit, list_of_chosen_upgrades)."""
# TODO: DP with reconstructionSelf-assessment checklist.
- [ ]
assign_shiftsalways undoes its decisions when backtracking (test: call it twice; it must give the same result). - [ ] There is a pruning that cuts before descending a level, not a final check.
- [ ] The greedy justification is an exchange argument, not "I tried it and it works".
- [ ]
upgrade_planreturns what to buy, not just how much benefit. - [ ] You have compared DP against the greedy by ratio and know which one wins and why.
Reference solution
Phase 1 — Shifts with backtracking.
def assign_shifts():
assignment, shifts_of = {}, {d: [] for d in AVAILABILITY}
def can_take(driver, slot):
if slot not in AVAILABILITY[driver]:
return False
if len(shifts_of[driver]) >= 2:
return False
previous_slots = {s for _, s in shifts_of[driver]}
return not (previous_slots and slot not in previous_slots) # rest rule
def solve(i):
if i == len(SHIFTS):
return True
line, slot = SHIFTS[i]
# PRUNING: is there enough capacity left for this slot?
pending = sum(1 for l, s in SHIFTS[i:] if s == slot)
capacity = sum(2 - len(shifts_of[d]) for d in AVAILABILITY
if can_take(d, slot))
if capacity < pending:
return False
for d in AVAILABILITY:
if can_take(d, slot):
assignment[(line, slot)] = d # choose
shifts_of[d].append((line, slot))
if solve(i + 1):
return True
shifts_of[d].pop() # undo
del assignment[(line, slot)]
return False
return dict(assignment) if solve(0) else None
print(assign_shifts())
# {('L1','Morning'): 'Anna', ('L1','Night'): 'Carla', ('L2','Morning'): 'Anna',
# ('L2','Night'): 'Carla', ('L3','Morning'): 'Bruno', ('L3','Night'): 'Diego'}The pattern is that of assign_shifts from 03-04: choose, recurse, undo. The rest rule is implemented as an incremental constraint (the driver's previous slots must match the new one), and the capacity pruning cuts the branch when the pending shifts of a slot exceed the remaining capacity of the drivers who can still take it — the impossibility is detected levels before stumbling into it. Look at the solution: Anna and Carla absorb the "double" mornings and nights and nobody mixes slots.
Phase 2 — Reinforcements with justified greedy. It is structurally the activity selection from 03-02: same value per slot, maximize how many fit. Criterion: always cover the slot that ends earliest among the compatible ones.
def cover_slots(slots):
chosen, current_end = [], float("-inf")
for start, end in sorted(slots, key=lambda x: x[1]):
if start >= current_end:
chosen.append((start, end))
current_end = end
return chosen
print(cover_slots([(9, 11), (10, 12), (11, 13), (14, 15), (15, 17), (16, 18)]))
# [(9, 11), (11, 13), (14, 15), (15, 17)] -> 4 slotsJustification (exchange): let g be the first slot the greedy chooses (the one with the earliest end) and O any optimal solution. The first slot of O ends at some f ≥ end(g); if we replace that slot with g, no later slot of O overlaps (they all start after f ≥ end(g)), so O remains valid and of the same size. Iterating the argument over the rest, the greedy reaches the optimal size. Cost: Θ(n log n) for the sort. Note that "start with the longest" or "the one that starts earliest" both fail — (9,11),(10,12),(11,13) is a counterexample to the second if (10,12) is chosen.
Phase 3 — Budget with DP and reconstruction. 0/1 knapsack (03-03) with capacity 10:
def upgrade_plan(upgrades, budget):
n = len(upgrades)
dp = [[0] * (budget + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
name, cost, benefit = upgrades[i - 1]
for c in range(budget + 1):
dp[i][c] = dp[i - 1][c] # don't buy
if cost <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - cost] + benefit)
chosen, c = [], budget # reconstruction
for i in range(n, 0, -1):
if dp[i][c] != dp[i - 1][c]: # upgrade i was bought
name, cost, _ = upgrades[i - 1]
chosen.append(name)
c -= cost
return dp[n][budget], list(reversed(chosen))
UPGRADES = [("bus shelter", 3, 4), ("screens", 4, 5),
("wifi", 2, 3), ("reserved lane", 7, 9)]
print(upgrade_plan(UPGRADES, 10))
# (13, ['bus shelter', 'reserved lane'])Optimum: bus shelter + reserved lane = €10k and benefit 13. The greedy by benefit/cost ratio (wifi 1.5 → bus shelter 1.33 → lane 1.29 → screens 1.25) would buy wifi + bus shelter (€5k) and then screens (€9k in total), benefit 12, and can no longer afford the lane: it falls one short of the optimum. The failure is the usual one (03-02): the local criterion fills the budget with "efficient" pieces that block the good combination — exactly what motivated upgrade_knapsack in 03-03. The reconstruction (comparing dp[i][c] with dp[i-1][c] backwards) is the part real projects do not forgive: the purchasing department is not satisfied with "the maximum benefit is 13"; it needs the list.
Course Conclusion
The syllabus is done. It is worth looking back and seeing the whole building:
- In Module 1 you laid the foundations: what an algorithm is, how to express it (pseudocode, diagrams, Python), the difference between iterative and recursive, between exact and heuristic, and the language that runs through it all: asymptotic notation and its hierarchy, from O(1) to O(2ⁿ).
- In Module 2 you learned to analyze: deriving time complexity line by line (Python's hidden costs included), measuring auxiliary and total space, and refining with best case, worst case, average and amortized cost.
- In Module 3 you learned to design: divide and conquer, greedy (and its obligation to prove or refute), dynamic programming and backtracking with pruning — and, above all, to diagnose which one each problem calls for.
- In Module 4 you took on the classics — binary search, insertion sort, merge sort, quicksort, Dijkstra, Floyd-Warshall — not as recipes, but as pieces whose workings and limits you understand and know how to adapt.
- In Module 5 you learned to optimize with method: measure first, attack in order (algorithm → code → memory → parallelize) and know when to stop.
- And in this Module 6 you trained it all together, right up to building complete pieces of RutaBus: a trip planner, a dashboard that processes gigabytes without breaking a sweat, and a planner for shifts, reinforcements and budget.
What you can do now, said plainly: look at code and see its cost; look at a problem and recognize its strategy; look at a slow system and know where to start. That triad — analyze, design, optimize — cuts across any language and any domain: today it was Python and a bus app; tomorrow it will be another stack and another business, and the reasoning will be the same.
Suggestions for growing from here:
- Advanced data structures: balanced trees, tries, hash tables from the inside, union-find, graphs with A* — they are the natural complement to this course, because many "better algorithms" are really "better structures".
- Deliberate practice: problem platforms (LeetCode, Codeforces, Advent of Code) keep the diagnosis skill from exercise 5 of 06-02 in shape; a few per week are enough.
- Your own projects: the next time you write a loop over real data, run the 06-01 analysis on it before hitting run. That habit, sustained for a few months, is what turns the content of this course into instinct.
- Reading: when you want formal depth, the usual reference texts (Cormen et al., Introduction to Algorithms; Skiena, The Algorithm Design Manual) rigorously expand everything presented here with a practical focus.
The fluency we promised at the start of this module never fully arrives — there is always a problem that resists — but it no longer starts from zero: it starts from a method. Thank you for coming this far, and enjoy the ride. At RutaBus they would say: end of the line; we hope it has been a good trip.