Lesson 16: Simulations & Code-Tracing Mastery

Warm-Up

Before a new bridge design gets built, engineers "drive" thousands of simulated trucks over a simulated span in software. Wind gusts, resonance, metal fatigue — modeled, varied, re-run overnight, at the cost of electricity.

Notice three things. The simulation is not the bridge — it's a simplified model. It's useful precisely because it's simplified: real crash-testing a real bridge is ruinously expensive and slightly illegal. And it's only as good as its assumptions — if the wind model ignores vortex effects, the simulation cheerfully approves a bridge that the real wind will destroy (look up the Tacoma Narrows footage sometime).

Simulation = model + assumptions + experiments you couldn't otherwise run. That's the whole conceptual topic. Then we go train your trace muscles on full-size programs.

Core Concept

Simulations: models you can experiment on

A simulation is a program that models a real-world process or phenomenon. The CED's claims, each of which becomes exam questions:

1. Simulations are abstractions. They simplify: they include the aspects of reality that matter for the question and omit the rest. A traffic simulation might model car counts and light timings while omitting weather, driver mood, and mechanical failures.
2. Simplification is a feature and a limitation. Omitting detail makes the model buildable, fast, and focused — and makes its results approximate. The right response to "the simulation ignores X" is not "so it's useless" but "so its results are unreliable where X matters."
3. Assumptions can bias results. Every simulation encodes choices — what to include, what distributions to use (Lesson 15's randomness models real variation), what starting conditions. Biased or wrong assumptions → systematically wrong outputs, delivered with computational confidence. (Echo of Lesson 5: garbage assumptions, confident garbage.)
4. Simulations enable otherwise-impossible experiments. Too dangerous (epidemic spread, reactor failures), too expensive (bridge tests), too slow (climate decades), or too destructive (crash tests) to run in reality — a simulation runs them repeatedly, cheaply, safely, with variables you can adjust one at a time.

Exam pattern: a described simulation, then "which is a limitation / an advantage / an omitted factor that matters?" The advantage answers = safe/cheap/fast/repeatable experimentation. The limitation answers = simplification means results may not match reality, especially where omitted factors matter. Answers claiming a simulation "proves" real-world outcomes overreach — simulations suggest and estimate.

A concrete micro-simulation

Estimate the probability that two dice sum to at least 10:

wins ← 0
REPEAT 1000 TIMES
{
    roll ← RANDOM(1, 6) + RANDOM(1, 6)
    IF (roll ≥ 10)
    {
        wins ← wins + 1
    }
}
DISPLAY (wins / 1000)

Run many random trials; count qualifying ones; the fraction estimates the probability (true value: 6/36 ≈ 0.167 — the simulation will land close, and closer with more trials). This trial-count-estimate skeleton is computational simulation in miniature; recognize it on sight.

Full-program tracing: the method under load

Exam capstone questions look like this — everything at once:

PROCEDURE process(vals, cut)
{
    keep ← 0
    FOR EACH v IN vals
    {
        IF (v ≥ cut)
        {
            keep ← keep + 1
        }
    }
    RETURN (keep)
}

data ← [12, 5, 20, 8, 15]
t ← process(data, 10)
DISPLAY (t)

Method — the same one, scaled up:

1. Read the main program first (bottom block). It calls process(data, 10).
2. Bind arguments to parameters in the margin: vals = [12, 5, 20, 8, 15], cut = 10.
3. Trace-table the body: 12 ✓, 5 ✗, 20 ✓, 8 ✗, 15 ✓ → keep = 3.
4. Carry the return back: t = 3. Display 3.

For multi-procedure programs, resolve inner calls first (Lesson 14), keep one margin note per call. For randomness, the question will either ask about possible outputs (enumerate ranges — Lesson 15) or fix the random values for you ("suppose RANDOM returns 4"). Nothing new is ever needed — just Lessons 7–15 executed without panic on a longer runway.

Time discipline: capstone traces cost 2–3 minutes. That's fine (pace budget ≈ 100 sec/question is an average — definitional questions take 20 seconds and subsidize these). What's not fine is 2 minutes of staring followed by a guess. Start the table immediately; the table always finishes.

Worked Examples

Example 1 (easy): Simulation advantages

Problem: A city considers a new bus route. Instead of running trial buses for a month, planners simulate ridership. Which is the main advantage?

Solution: The simulation lets planners test the route (and variations — different frequencies, stops) quickly and cheaply, without the cost and disruption of a real trial. Multiple scenarios can be compared before committing resources.

Interpretation: Advantage answers = experiment without real-world cost/risk/time; test many variations. Simple as it looks, exams phrase this exact idea repeatedly.

Example 2 (medium): Find the biasing assumption

Problem: A simulation predicts cafeteria wait times. It assumes every student takes exactly 45 seconds to be served and arrivals spread evenly across the lunch period. Real service times vary, and real students arrive in waves when classes release. What effect do the assumptions have?

Solution: Both assumptions smooth away congestion — the exact phenomenon that creates long waits. Evenly-spread arrivals eliminate rush spikes; uniform service time eliminates slow-order pileups. The simulation will systematically underestimate wait times, worst at peak moments — the moments the cafeteria actually cares about.

Interpretation: The graded skill: connect the specific simplification to the direction of the error. Practice the sentence "because the model omits/assumes , its results will over/under-estimate ."

Example 3 (medium): Trace the micro-simulation

Problem: In the dice simulation from section (b), suppose the loop ran only 4 times instead of 1000, and the pairs rolled were (6,5), (2,3), (4,6), (6,6). What is displayed (with the divisor changed to 4)?

Solution: Sums: 11 ✓ (≥10), 5 ✗, 10 ✓ (inclusive ≥), 12 ✓ → wins = 3. Displays 3/4 = 0.75.

Interpretation: With trials fixed, a simulation question becomes a plain loop trace — table it. Note the boundary: 10 qualifies because the comparison is ≥. And note 0.75 vs. the true ≈ 0.167: tiny samples mislead — a fact the exam also likes ("how could the estimate be improved?" → more trials).

Example 4 (AP-style): Full-load trace

Problem: What is displayed?

PROCEDURE mix(list)
{
    out ← 0
    FOR EACH x IN list
    {
        IF (x MOD 2 = 0)
        {
            out ← out + x
        }
        ELSE
        {
            out ← out − 1
        }
    }
    RETURN (out)
}

nums ← [4, 7, 10, 3]
DISPLAY (mix(nums) + LENGTH(nums))

Solution: Bind: list = [4, 7, 10, 3]. Table:

mix returns 12; LENGTH(nums) = 4; displays 16.

Interpretation: Four skills in one item (procedure binding, FOR EACH, MOD parity, post-call arithmetic) and not one of them new. The exam's "hard" questions are long, not deep. The table is the equalizer.

Common Mistakes

1. Treating simulation output as proof. Simulations estimate under assumptions. "The simulation proves the design is safe" overclaims; "suggests/estimates" is the graded phrasing.
2. "It's simplified" as an automatic flaw. Simplification is the point. The valid criticism names a specific omitted factor and why it matters for this question.
3. Missing the assumption→bias direction. Don't stop at "the assumption is unrealistic" — say which way it skews the result (Example 2).
4. Losing the thread in long traces. No mental stacking: margin-bind every call, table every loop, cross out untaken branches. Length is the difficulty.
5. Forgetting the post-call step. After the procedure returns, the main program usually does one more thing (+ LENGTH, × 2, compare). The distractor "12" in Example 4 is the return value without the final addition.

Practice Problems

count ← 0
REPEAT 3 TIMES
{
    count ← count + 2
}
DISPLAY (count)

total ← 0
REPEAT 2 TIMES
{
    total ← total + RANDOM(1, 6)
}
DISPLAY (total)

PROCEDURE f(list, limit)
{
    r ← 0
    FOR EACH v IN list
    {
        IF (v < limit)
        {
            r ← r + 1
        }
    }
    RETURN (r)
}

PROCEDURE change(x)
{
    RETURN (x * 2)
}
n ← 6
change(n)
DISPLAY (n)

PROCEDURE grade(s)
{
    IF (s ≥ 80)
    {
        RETURN ("high")
    }
    RETURN ("low")
}

results ← ""
FOR EACH s IN [85, 60, 92]
{
    results ← results + grade(s)
}
DISPLAY (results)

12 (short response). A simulation models a coffee shop where every customer orders in exactly 30 seconds and a new customer arrives exactly every 60 seconds. (i) Explain why this simulation will report that no line ever forms. (ii) Name one change that would make lines possible in the model.

Create PT Connection

You've now completed every programming concept the Create PT requires — this lesson's full-program traces are bigger than anything your PT needs. Two takeaways for the task:

• Your PT can BE a simulation. Dice games, probability estimators, queue models — all satisfy the rubric naturally (list of trial results, procedure with selection + iteration, meaningful randomness). If you go this route, Written Response 1's "purpose" is a gift: to estimate/model X.
• Trace your own program before recording. Run your procedure on paper with one small input, exactly like Example 4. If the paper trace and the real run disagree, you've found a bug before the video — which is precisely the "testing" story WR 2(b) wants.

Checkpoint: by now you should have — from Lessons 6, 8, 11, 14 — a PT idea, its list, its procedure, and a written paragraph on each. If any piece is missing, spend 20 minutes tonight; Phase 4 (networks) and Phase 5 (impact) won't circle back to programming.