Problem Decomposition

Pseudocode & Algorithmic Problem-Solving

Chapter 4 · Problem Decomposition

A real problem statement rarely arrives in a form small enough to write pseudocode for directly. Top-down design is the discipline of splitting a large, ambiguous problem into smaller subproblems — and splitting those, if needed — until each remaining piece is simple enough that Chapter 2's own three building blocks can express it directly.

Input / Processing / Output: A Starting Discipline

Before decomposing anything, frame the problem in three parts — what goes in, what has to happen to it, and what comes out. This alone often reveals the natural first split.

IPO	For this chapter's problem: "compute a shopping cart's final total"
Input	A list of cart items, each with a quantity and unit price
Processing	Subtotal → discount tier → shipping → tax → sum — genuinely several distinct steps, not one
Output	A single final total the customer pays

The "Processing" row is doing too much to write pseudocode for directly — that's the signal to decompose it further.

Top-Down Decomposition, One Level

Splitting "Processing" into its natural major steps produces five subproblems, each independently understandable without needing to know how the others are implemented internally:

Why stop at exactly five, and not fewer or more

Each of these five boxes is now small enough to write pseudocode for directly — Chapter 5's own translation discipline can turn any one of them into real code without needing to think about the other four at the same time. That's the actual stopping rule for top-down decomposition: not a fixed number of levels, but "can I now write straightforward pseudocode for this piece, using only sequence, selection, and iteration?"

Pseudocode for Each Subproblem — and a Full, Verified Composition

Each of the five boxes above becomes its own short block of pseudocode, using a concrete cart to ground the numbers: 3 Widgets at $12.50, 1 Gadget at $45.00, 2 Gizmos at $8.25. Discount tiers: 10% off at $100+, 5% off at $50+. Free shipping at $75+ (discounted), otherwise a flat $8. Tax: 8%.

// Subproblem 1
ALGORITHM CalculateSubtotal(items)
    subtotal ← 0
    FOR EACH (name, qty, price) IN items
        subtotal ← subtotal + (qty × price)
    ENDFOR
    RETURN subtotal

// Subproblem 2
ALGORITHM ApplyDiscountTier(subtotal)
    IF subtotal ≥ 100 THEN rate ← 0.10
    ELSE IF subtotal ≥ 50 THEN rate ← 0.05
    ELSE rate ← 0.00
    ENDIF
    RETURN subtotal × (1 - rate)

// Subproblem 3
ALGORITHM CalculateShipping(discounted_subtotal)
    IF discounted_subtotal ≥ 75 THEN RETURN 0
    ELSE RETURN 8
    ENDIF

// Subproblem 4
ALGORITHM CalculateTax(discounted_subtotal)
    RETURN discounted_subtotal × 0.08

// Subproblem 5
ALGORITHM ComputeCartTotal(items)
    subtotal ← CalculateSubtotal(items)
    discounted ← ApplyDiscountTier(subtotal)
    shipping ← CalculateShipping(discounted)
    tax ← CalculateTax(discounted)
    RETURN discounted + shipping + tax
    

Verified directly — running the composed subproblems end to end

Translated into real code and run on the worked cart: CalculateSubtotal returns 99.00 (3×12.50 + 1×45.00 + 2×8.25). ApplyDiscountTier selects the 5% tier (since 50 ≤ 99 < 100), giving 94.05. CalculateShipping returns 0 (free — 94.05 ≥ 75). CalculateTax returns 7.52 (94.05 × 0.08, rounded). ComputeCartTotal sums these to a final total of 101.57 — matching a hand-computed reference calculation exactly.

Decomposition changes structure, never the answer

The four sub-algorithms compute exactly what one large, undivided block of code would compute for the same cart — decomposition didn't add or remove any logic, it only organized it into pieces that can each be written, tested, and verified independently. If CalculateShipping alone had a bug, only that one subproblem's own pseudocode needs re-checking, not the entire calculation.

Where This Connects

This chapter's finding	What it sets up
IPO framing revealing where a problem needs further splitting	The default first move Chapter 10's own capstone applies to a genuinely ambiguous problem statement
Five independently verifiable subproblems, composed and confirmed end to end	Chapter 5's translation discipline works subproblem by subproblem — exactly this chapter's own decomposition, not the whole algorithm at once
"Small enough to write pseudocode for directly" as the real stopping rule	Chapters 6-8's design strategies (brute force, greedy, divide and conquer) all operate on problems already broken down to roughly this size

Hands-On Exercises

Exercise 1

Using this chapter's own five sub-algorithms, compute the final total for a cart containing just 1 item: a single $120.00 item, quantity 1. Show the result of each of the five subproblems in order, the same way this chapter's own worked example did.

📄 View solution

Exercise 2

A new requirement arrives: orders over $200 (after discount) get a $5 shipping discount even if shipping wasn't already free. Using this chapter's own decomposition, identify which single subproblem needs to change, and explain why the other four don't need to be touched at all.

📄 View solution

Exercise 3

Using this chapter's own IPO framing and stopping rule, apply the same discipline to a new problem: "given a list of student test scores, compute each student's letter grade and the class average." Write the Input/Processing/Output table, and list what you'd expect the first-level decomposition's major subproblems to be.

📄 View solution

Chapter 4 Quick Reference

Input/Processing/Output (IPO) framing is the starting discipline — an overloaded "Processing" row is the signal a problem needs decomposing
Top-down design: split a problem into major subproblems, and split further only until each piece is small enough for direct pseudocode — not a fixed number of levels
Verified directly: five independently-defined subproblems (subtotal, discount tier, shipping, tax, sum), composed and run end to end, produced 101.57 for a worked cart — matching a hand-computed reference exactly
Decomposition reorganizes logic, it never changes the answer — and it lets any one subproblem be checked or fixed without touching the others
Next chapter: Translating pseudocode into real code — taking exactly this kind of decomposed design and mapping it onto a specific language and paradigm