Selection and iteration

1. THE TWO PIECES OF PAPER: THE TRACE TABLE AND THE LOOP TABLE

Every question in this unit is answered on one of two tables, and the first move is to draw it.

The trace table — for straight-line code with decisions in it. One column per variable, one row per statement executed, and when a condition is reached, a row that records its value:

The condition column is the whole point: a branch is taken because a comparison came out true for these values, and writing the comparison down is what stops you from taking the branch the code’s shape suggests.

The loop table — for anything that repeats. One row per pass: the condition’s value before the pass, what the body did, and every variable’s value after. The first row is the test before the first pass (a loop can run zero times); the last row is the test that came out false. Count the rows and you have the number of passes, which is the number the exam asks for and the number fingers get wrong.

The verbs. Determine the output — the table, then the exact text, spacing and line breaks included. Describe the behavior — what the segment does for any input, in one sentence with the variables named. Explain why it does not work and fix it — what it does instead, then the corrected line. Write the method — the header first, the return last, the loop and its bounds in between.

2. SEQUENCING, SELECTION, REPETITION — THE THREE BLOCKS EVERY ALGORITHM IS BUILT FROM

An algorithm is a step-by-step process, and the CED names its three building blocks. Sequencing runs statements one after another (Unit 1). Selection chooses between paths on a true-or-false decision. Repetition runs a segment again and again until a condition changes. The order in which they are combined is the algorithm; the same three blocks in a different order do something different.

The exam’s habit is to hand you a description in words — “a game that reacts to the player,” “a filter that keeps only the records that match” — and ask which block it needs. Reacts to and only if are selection; for each, until, keep going are repetition; first this, then that is sequencing.

3. BOOLEAN EXPRESSIONS: RELATIONAL OPERATORS, AND WHAT ==ACTUALLY COMPARES

A relational operator compares two values and produces a boolean: == and != ask whether values are the same; <, >, <=, >= compare numbers. The result is a value like any other — it can be stored in a boolean variable, printed, or returned — and a method whose whole body is return x > 0; is complete.

What == compares depends on the type. On primitives (int, double, boolean) it compares the values: 7 == 7 is true. On reference types it compares the references — whether two variables point at the same object — and two objects with identical contents built separately are not the same object. For a String’s contents the question is .equals:

Two idioms. if (s != null && s.length() > 0) checks for an object before asking it anything, in that order (card 5 says why the order matters). And if (flag == true) is if (flag); the comparison adds nothing and is a place to write = by accident.

4. IF, IF-ELSE, NESTED, MULTIWAY — AND THE RULE THAT THE FIRST TRUE WINS

A one-way if runs its body when the condition is true and skips it otherwise. A two-way if-else runs exactly one of two bodies. A nested if sits inside another’s body, and its condition is tested only if the outer condition was true. A multiway if-else-if is a chain: the conditions are tested in order, the first true one’s body runs, and no other body runs — a trailing else catches the case where none was true.

Because the chain stops, the second condition is really “t < 90 && t >= 70” — the earlier conditions’ failures are implied. That is why the order matters: the same four tests as separate ifs, from the largest threshold down, each overwrite the last, and t = 95 comes out "mild". Problem 1 traces both.

Three traps in the syntax. An if without braces controls exactly the next statement; indent all you like, the second line runs unconditionally. An else pairs with the nearest unmatched if above it, whatever the indentation says — braces are how you say otherwise. And a semicolon after the condition, if (x > 0);, ends the if with an empty body, so the next line runs every time.

Reading a nested if as a multiway. if (a) { if (b) X else Y } else Z is the same as “a && b: X; a && !b: Y; !a: Z” — and the exam asks you to rewrite in both directions. Problem 2 does.

5. COMPOUND EXPRESSIONS: !, &&, ||, AND SHORT-CIRCUIT EVALUATION

The logical operators combine booleans: !a flips; a && b is true only when both are; a || b is true when either is, or both. Precedence runs !, then &&, then ||, so !a && b || c means ((!a) && b) || c. Write the parentheses the precedence implies before evaluating, every time.

Short-circuit evaluation. Java evaluates a compound left to right and stops as soon as the answer is known: in a && b, if a is false the whole thing is false and b is never evaluated; in a || b, if a is true, b is never evaluated. This is not an optimization you can ignore — it is the reason

is safe when x is 0 (the division never happens) while y / x > 2 && x != 0 throws an ArithmeticException first. The same guard protects a null: s != null && s.length() > 3. Put the guard on the left.

Reading a compound in words. “Between 10 and 20” is x >= 10 && x <= 20; “outside” is x < 10 || x > 20. “Not between” is the negation of the first, which card 6 turns into the second. A student who writes 10 <= x <= 20 has written something that does not compile; Java compares two values at a time.

6. EQUIVALENT EXPRESSIONS, DE MORGAN’S LAW, AND COMPARING REFERENCES

Two Boolean expressions are equivalent when they evaluate the same in every case, and a truth table — every combination of the variables, both expressions evaluated — is the proof. For two variables that is four rows; for three, eight. The exam asks “which of the following is equivalent to …” and the honest method is the table; the fast method is the law below, checked against one row.

De Morgan’s law moves a ! through a compound by flipping the operator and negating each part:

Combined with negating a comparison — !(x < 5) is x >= 5, !(x == y) is x != y — it rewrites any negated condition into one with no ! at all:

The error the exam plants is flipping the operator without negating the parts (!a && !b for !(a && b)), or negating the parts without flipping the operator. Both fail on a row of the table; check one.

Comparing references. Two variables can hold references to the same object; == and != ask exactly that. A reference compared with null says whether there is an object at all. Classes define their own equals to say what “equivalent” means for their objects — usually that the attributes match — and that is the method to call when contents are the question. For Strings this is the difference between a == b (same object?) and a.equals(b) (same characters?), and the exam writes both.

7. WHILE LOOPS: ZERO OR MORE TIMES, AND THE TWO WAYS THEY GO WRONG

A while loop tests its condition before every pass, including the first; when the condition is true the body runs and the test happens again; when it is false the loop ends. So a loop whose condition is false at the start runs zero times, and a loop whose condition never becomes false is an infinite loop — usually because the body never changes the variable the condition tests, or changes it the wrong way.

The loop table is the method, and here it is for the digit-sum of n = 4729 with while (n > 0):

Four passes, five tests. The row that says F is the one students forget to write, and it is the row that decides the count.

Off by one. The CED names it: “the iteration statement loops one time too many or one time too few.” while (n > 9) on the table above stops with n = 4 unsummed — one pass too few; i <= s.length() on a String is one pass too many and throws. The cure is the first and last rows of the table.

Leaving early. A loop that should stop when something is found needs a conditional inside the body that changes what the condition tests — a boolean found flag set to true, with while (i < n && !found) — or a compound condition that tests the thing directly. The CED’s warning is about order: update the flag at the line where the discovery is made, and the test sees it on the next pass, not this one.

8. FOR LOOPS: THREE PARTS, ONE EXACT ORDER

A for header has three parts, and the CED spells out when each runs:

The variable declared in the header is the loop control variable, and it exists only inside the loop. When the loop ends, i has the first value that failed the test — for the header above, 5, not 4.

The four headers the exam uses, with their values written out — write them out yourself until this is reflex:

for and while are the same loop. Any for rewrites as: the initialization before a while whose condition is the test, with the update as the last line of the body — and the reverse. Use for when the number of passes is known from the start, while when the loop runs until something happens; the exam asks you to convert in both directions.

9. THE STANDARD ALGORITHMS — AND THE INITIALIZATION THAT DECIDES EACH ONE

The CED lists five, and each is three lines once you know the line that comes before the loop:

The max initialized to zero is the unit’s quietest bug: it is right for positive data and silently wrong the day the values are all negative — max stays 0, a value that was never in the data. Initialize from the first element, or from Integer.MIN_VALUE when there is no first element to read.

The average is Unit 1’s division. sum / count with two ints is an int; (double) sum / count is the average. Cast before dividing, not after.

Digits come off the right. 4729 % 10 is 9, 4729 / 10 is 472; repeating gives 2, 7, 4, and the loop ends when the quotient reaches 0. To get the digits in left-to-right order, count them first or build a String.

10. STRING ALGORITHMS: THE TRAVERSAL, THE WINDOW, AND THE BOUNDARY

A String is walked one character at a time with substring(i, i + 1) — Unit 1’s one-character substring — for i from 0 to length() - 1. Three things are built on that walk, and the CED names them:

• does a substring with a property exist — walk, test each window, set a flag or return early;
• count the substrings meeting a criterion — walk, count++ on each hit;
• reverse the characters — walk, and build rev = ch + rev so each new character lands in front.

The window’s boundary. A window of k characters starting at i is substring(i, i + k), and it exists only while i + k <= length(), that is, i <= length() - k. For k = 2 the loop is for (int i = 0; i < s.length() - 1; i++). Off by one here is not a wrong count; it is a StringIndexOutOfBoundsException.

The other traversal: indexOf. To walk words, find the next space and cut: int sp = s.indexOf(" "); String w = s.substring(0, sp); s = s.substring(sp + 1); — and the last word has no space after it, so indexOf returns -1 and the whole remainder is the word. The CED’s own sample activity is the $n$th word; Problem 7 writes it.

Strings are immutable, so every “change” is a new String assigned back: s = s.substring(1) shortens s; s.substring(1) on its own does nothing you can see.

11. NESTED ITERATION: THE INNER LOOP FINISHES FIRST

When a loop is inside another loop, the inner loop runs all of its passes every time the outer loop takes one step. The picture is a grid: the outer variable picks the row, the inner variable walks across it.

Two shapes the exam draws. Independent bounds — a rectangle, $m\times n$ executions. An inner bound that depends on the outer variable, j <= i or j = i, — a triangle, $1+2+\cdots +n=n(n+1)∕2$ executions. Output patterns of stars, digit tables and pairwise comparisons are all one of the two.

Reading the output. A print inside the inner loop and a println() after it, inside the outer loop, makes one line per outer pass. Trace one full outer pass by hand, then trust the pattern.

12. INFORMAL RUN-TIME ANALYSIS: COUNTING STATEMENT EXECUTIONS

A statement execution count is how many times a statement runs, found by tracing the loops around it. For a single loop it is the number of passes; for nested loops, the sum over the outer passes of the inner passes. The exam asks it two ways: “how many times is the statement executed,” and “which segment executes the statement more times.”

Three counts worth knowing cold:

For anything else, the loop table is the method: write the passes and count the rows. “Informal” means a number for this $n$, not a formula for all of them — the exam gives $n=10$ and wants $55$.