Advanced dry runs and off-by-one errors

Prerequisites and outcomes

Know variables, conditions, loops, arrays, and basic functions. By the end, you can trace a loop with a table, distinguish inclusive from exclusive bounds, and explain the invariant that makes a loop correct.

Dry run means simulate exact state

A dry run is a manual execution of a program. Do not jump from the first line to the final answer. Record the values that control the next step.

Trace a loop

int total = 0;
for (int i = 1; i <= 4; ++i) {
    total += i;
}

Check at loop start	i	total before body	total after body
true	1	0	1
true	2	1	3
true	3	3	6
true	4	6	10
false	5	10	body skipped

The body executes four times. Notice that the increment happens after the body, then the condition is checked again.

Inclusive and exclusive bounds

for (int i = 0; i < n; ++i)  // indexes 0 through n - 1
for (int i = 1; i <= n; ++i) // values 1 through n

For a sequence of length n, valid vector indexes are from 0 to n - 1. The half-open range [begin, end) includes the first position and excludes the end position. This convention makes an empty range possible when begin equals end.

Loop invariant: a correctness tool

A loop invariant is a statement that is true before the first iteration and remains true after every iteration. For the summation loop, after processing values 1 through i, total equals their sum. At termination, all values 1 through 4 have been processed, so the result is 10.

Common off-by-one patterns

• Using i <= values.size() and then reading values[i]; the last valid index is size minus one.
• Starting a count at 1 but using a zero-based index without converting the meaning.
• Incrementing an index twice or skipping the first/last element.
• Using i + 1 when i is already the final index.

Prerequisites: counted loops, arrays and vectors, nested loops, and basic complexity reasoning. Review Loops, Arrays, Nested loops, and Vectors first.

Worked boundary check

std::vector<int> values{4, 8, 12};
for (std::size_t i = 0; i < values.size(); ++i)
    std::cout << values[i] << '\n';

The loop visits indexes 0, 1, and 2. When i becomes 3, i < values.size() is false and the body is skipped. The number of iterations is n, and the loop uses O(1) extra space.

Practice

1. How many times does for (int i=0; i<7; ++i) execute?
2. What is wrong with accessing values[values.size()]?
3. What does the half-open range [2, 5) contain?

Show reasoned answers

1. Seven times: i takes values 0 through 6.
2. It is one past the final valid index and is not an element of the vector.
3. Positions 2, 3, and 4; the endpoint 5 is excluded.

Summary and next step

Trace every state change, write down the exact loop condition, and test empty, one-element, and final-index cases. Use invariants to explain correctness rather than relying only on a successful sample run. Next, apply careful validation in a small calculator project.

References

• cppreference: iterator ranges
• C++ Core Guidelines