Capstone — Designing an Algorithm from a Real-World Problem Statement

Pseudocode & Algorithmic Problem-Solving

Chapter 10 · Capstone — Designing an Algorithm from a Real-World Problem Statement

One continuous project: a conference organizer hands over a genuinely ambiguous request, and every chapter of this course gets applied, in order, to turn it into a working, verified algorithm — resolving the ambiguity, decomposing the problem, choosing the right strategy for each piece, and translating the result into real code.

Step	Task	Chapter(s) used
1	Resolve the ambiguous problem statement	Ch.1
2	Frame it with IPO and decompose it	Ch.2, Ch.4
3	Sort the talks — reusing merge sort directly	Ch.8
4	Assign rooms with a greedy strategy, verified optimal	Ch.7
5	Check a small manual override with brute force	Ch.6, Ch.9
6	Translate the final algorithm into real code	Ch.5

Step 1 — The Problem Statement, and Its Hidden Ambiguity

Ch.1

The organizer's request: "Build something that schedules our conference talks into rooms so nothing overlaps, using as few rooms as possible."

Flagged, per Chapter 1's own discipline

"Nothing overlaps" doesn't say whether a talk ending at 10:00 and another starting at 10:00 in the same room counts as a conflict. "As few rooms as possible" doesn't say whether that means minimizing the room count or the room rental cost — different rooms could cost differently. Resolved explicitly, exactly as Chapter 1 recommended: talks may share a room if one ends exactly when the other starts (touching, not overlapping); "as few as possible" means minimizing the total number of distinct rooms used.

Step 2 — IPO Framing and Decomposition

Ch.2, Ch.4

Input: a list of talks, each with a start and end time. Processing: genuinely three separate jobs. Output: a room assignment for every talk, using the fewest distinct rooms.

Step 3 — Sorting: Reusing Merge Sort Directly

Ch.8

Six talks: A(9-10), B(9-11), C(10-12), D(11-13), E(12-13), F(9-12). Subproblem 1 needs them ordered by start time before assignment can begin — exactly Chapter 8's own MergeSort, unchanged, applied to a new kind of data.

Verified directly

Sorted by start time: A(9), B(9), F(9), C(10), D(11), E(12) — three talks tie at 9:00, and MergeSort's own stable comparison (left[0] ≤ right[0], from Chapter 8) preserves their original relative order rather than shuffling them arbitrarily.

Step 4 — Greedy Room Assignment, Verified Optimal

Ch.7

For each sorted talk: reuse a room whose current occupant has already finished, if one exists; otherwise open a new room. This is the same greedy shape Chapter 7 used — one locally-best choice per step, never revisited.

Verified directly — greedy result, cross-checked against an independent computation

The greedy assignment uses 3 rooms: Room 0 → A, C, E; Room 1 → B, D; Room 2 → F. Cross-checked independently — not by re-running the greedy algorithm, but by directly sweeping the timeline for the maximum number of talks ever happening simultaneously (which, at 10:00-11:00, is exactly 3: B, C, F all in progress) — the greedy result matches this independent minimum exactly.

Why greedy is trustworthy here — unlike Chapter 7's own {1,3,4} counterexample

Room scheduling has a real, provable property Chapter 7's coin-change counterexample lacked: the minimum number of rooms needed is always exactly equal to the maximum number of talks overlapping at any single instant, and the "reuse the earliest-freeing room, else open a new one" strategy always achieves that exact minimum. This isn't assumed — it's exactly what the independent max-overlap cross-check above just confirmed for this specific case.

Step 5 — A Small Brute-Force Check for an Organizer's Override

Ch.6, Ch.9

The organizer asks: "Could talks A, C, D, and E fit into just 2 rooms, if we moved something?" — a genuinely small question (only 2⁴=16 possible 2-room assignments), exactly the kind of search Chapter 6 called honestly brute-forceable.

Verified directly — brute force with an early exit, exactly Chapter 9's own prune-as-you-go spirit

Checking every 2-room split of {A, C, D, E}, stopping the instant a valid one is found (the same early-termination discipline as Chapter 9's own backtracking): a valid split exists — Room 0: A, C, E; Room 1: D — found after checking just 5 of the 16 possible splits. Cross-checked against the same max-overlap technique from Step 4 on just this subset: the maximum overlap among these four talks is 2, confirming 2 rooms genuinely suffice.

Step 6 — Translating the Final Algorithm Into Real Code

Ch.5

The chosen strategy — sort, then greedily assign — translates directly into Python, using a min-heap to always find the earliest-freeing room efficiently:

import heapq

def assign_rooms(talks):  # talks: list of (name, start, end)
    sorted_talks = sorted(talks, key=lambda t: t[1])
    heap = []                    # (end_time, room_id)
    assignment = {}
    next_room = 0
    for name, start, end in sorted_talks:
        if heap and heap[0][0] <= start:
            end_time, room_id = heapq.heappop(heap)
            heapq.heappush(heap, (end, room_id))
        else:
            room_id = next_room
            next_room += 1
            heapq.heappush(heap, (end, room_id))
        assignment[name] = room_id
    return next_room, assignment
    

Verified directly — the real code matches the pseudocode-level result exactly

Run on all six talks: next_room = 3, assignment = {'A':0, 'B':1, 'F':2, 'C':0, 'D':1, 'E':0} — identical to Step 4's own hand-verified result.

What This Course Doesn't Cover

As stated honestly back in Chapter 1: formal complexity analysis and formal logic/proof techniques stayed out of scope through all ten chapters. This capstone never asked how fast any of these algorithms are, or proved greedy's optimality from first principles — it verified correctness by cross-checking against an independent computation, exactly the discipline this course built from Chapter 6 onward. Algorithms & Complexity and Discrete Mathematics Fundamentals pick up exactly where this course's own honest boundary was drawn.

Where This Course Connects

Discrete Mathematics Fundamentals' own set and logic material underlies Chapter 2's structured conditionals directly. Algorithms & Complexity would give this capstone's own greedy-optimality claim (Step 4) and brute-force cost (Step 5) precise, provable mathematical treatment. Within the new Software Development subject, Design Patterns picks up directly where this course leaves off — the same decomposed, well-named subproblems this capstone produced (sort, assign, verify) are exactly the shape a real codebase organizes into classes and modules.

Hands-On Exercises

Exercise 1

Using this chapter's own greedy room-assignment algorithm, hand-trace what room a new talk, G(13-14), would be assigned to if added to the original six talks and processed after all of them (in sorted order). Which room does it reuse, and why?

📄 View solution

Exercise 2

Using this chapter's own Step 1 ambiguity resolution, explain what would change about the greedy room-assignment result in Step 4 if "nothing overlaps" had instead been resolved to mean that a talk ending at 10:00 and another starting at 10:00 in the same room DO count as a conflict (no touching endpoints allowed).

📄 View solution

Exercise 3

Using this chapter's own Step 5, explain why checking the organizer's override question with brute force was the honest choice per Chapter 6's own criteria, rather than reusing the same greedy algorithm from Step 4 to answer it directly.

📄 View solution

Chapter 10 Quick Reference

Full worked project: ambiguity resolution (Ch.1) → IPO + decomposition (Ch.2, Ch.4) → merge sort (Ch.8) → greedy room assignment, verified optimal (Ch.7) → a small honest brute-force check (Ch.6, Ch.9) → real-code translation (Ch.5)
Greedy room assignment verified against an independent max-overlap computation — genuinely optimal here, unlike Chapter 7's own {1,3,4} counterexample, because this problem has the right provable structure
A small, genuinely brute-forceable subproblem (16 possibilities) handled honestly with exhaustive checking, with an early exit in the same spirit as Chapter 9's own pruning
The final real-code translation matched the pseudocode-level result exactly, closing the loop from Chapter 1's own opening warning about ambiguity all the way to working, verified code
Course complete — Pseudocode & Algorithmic Problem-Solving, 10 chapters, from a single ambiguous "remove duplicates" spec to a fully designed, verified, and coded scheduling algorithm