Fig. 1
Drag to turn · shift-drag to pan · click to break it down
Scroll to turn the page
Computer Science A · AP Computer Science A
if, while and for
A program runs its statements one after another, in order. Two things change that order: selection chooses which statements run, and iteration runs statements again.
The program in the figure starts with n = 5. While n is not 1, it halves n if it is even, or triples it and adds 1 if it is odd, and counts a step. The diamond at the top is the loop’s question; the diamond below it is the if’s. The red token is the point of execution, and the code beside it lights the line running.
int n = 5; int steps = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; } else { n = 3 * n + 1; } steps++; } System.out.println(steps); n goes 5, 16, 8, 4, 2, 1. The loop’s condition is checked 6 times: true 5 times, then false once, and the program prints 5.
This chapter is AP Computer Science A Unit 2, 25–35% of the multiple-choice score: Boolean expressions and if statements (2.1–2.6), while and for loops (2.7–2.8), the standard algorithms built from them (2.9–2.10), loops inside loops (2.11), and counting how often a statement runs (2.12).
the three building blocks
Every algorithm is built from three things: sequencing (steps in order), selection (a decision) and repetition (a loop).
Selection happens when the way an algorithm goes on depends on a true or false decision. Repetition is a process repeating until a desired outcome is reached. Both appear in everyday instructions: “if it is raining, take an umbrella” is selection; “stir until the sugar dissolves” is repetition.
Algorithms can be written in words or drawn as a flowchart: a box for each step, a diamond for each true-or-false decision, and an arrow running back up for repetition. The figure now writes the same algorithm in words: “is n even?”, “halve it”, “count a step”. The code says exactly the same thing in Java.
The order of the steps changes the outcome. These two segments hold the same statements:
int x = 3; x = x * 2; x = x + 1;
int x = 3; x = x + 1; x = x * 2;
The first leaves x at 7; the second, at 8. In the figure, counting a step after the loop instead of inside it would print 1, however long the loop ran.
relational operators
A Boolean expression evaluates to one of two values, true or false. The simplest compare two values with a relational operator.
== and != test whether two values are the same or different. <, >, <= and >= compare numbers. With primitive types such as int, double and boolean, == compares the actual values. With reference types it compares the references: whether two variables refer to the same object (2.6).
In the figure a holds 7 and b takes the values 4, 7, 9. Each comparison produces a block, red for true:
| b = 4 | b = 7 | b = 9 | |
|---|---|---|---|
a == b | false | true | false |
a != b | true | false | true |
a < b | false | false | true |
a > b | true | false | false |
a <= b | false | true | true |
a >= b | true | true | false |
= assigns; == compares. A Boolean result can be stored like any other value: boolean same = a == b;
one-way and two-way selection
Selection statements change the sequential execution of statements. An if statement runs different segments of code depending on the value of a Boolean expression.
A one-way selection (an if) has one segment, run only when the condition is true:
if (temp >= 30) { System.out.println("hot"); } System.out.println("done"); With temp at 34 it prints hot then done; at 22, only done. The last line is after the if, so it always runs.
A two-way selection (an if-else) has two segments: the body of the if when the condition is true, the body of the else when it is false. Exactly one of them runs.
if (temp >= 30) { System.out.println("hot"); } else { System.out.println("mild"); } System.out.println("done"); The figure sends two temperatures down it. At 34 the token takes the true lane and prints hot; at 22 the false lane, mild. Both then print done.
if, else if, else
A multiway selection (if-else-if) tests a series of conditions in order. The first one that is true runs its segment, and no more than one segment runs.
if (score >= 90) { grade = "A"; } else if (score >= 80) { grade = "B"; } else if (score >= 70) { grade = "C"; } else { grade = "F"; } The figure drops three scores down the chain. 83 fails score >= 90, passes score >= 80, and is caught: grade "B". The conditions below are never checked. 95 is caught by the first gate, "A". 64 fails all three, so the trailing else runs: "F". Without a trailing else, a value that fails every condition runs no segment at all.
Because the first true condition wins, order matters. Test score >= 70 first and 95 gets "C": every score of 70 or more stops at the first gate. Put the most demanding test first.
an if inside an if
Nested if statements are if, if-else or if-else-if statements inside another if, if-else or if-else-if statement.
if (age >= 16) { if (hasPermit) { System.out.println("may drive"); } else { System.out.println("needs a permit"); } } System.out.println("done"); The inner condition is evaluated only if the outer one is true. The figure runs three people through. Age 17 with a permit passes both and prints may drive. Age 17 without one passes the outer test and fails the inner: needs a permit. Age 14 fails the outer test, so the token goes round the whole box: hasPermit is never even looked at, and only done is printed.
The braces decide which if an else belongs to. Here the else is inside the outer braces, so it pairs with if (hasPermit): someone under 16 gets no message about a permit at all.
!, && and ||
The logical operators ! (not), && (and) and || (or) combine Boolean expressions into one that is itself true or false.
!a is true when a is false, and false otherwise. a && b is true only when both are true. a || b is true when a is true, b is true, or both. The figure works through every combination, one row at a time:
| a | b | a && b | a || b | !a |
|---|---|---|---|---|
| true | true | true | true | false |
| true | false | false | true | false |
| false | true | false | true | true |
| false | false | false | false | true |
The order of precedence is ! first, then &&, then ||. So with a = false, b = true, c = false, the expression !a || b && c means (!a) || (b && c): true. Grouping it as (!a || b) && c instead gives false. Parentheses make the order plain.
Relational operators come before logical ones, so x > 0 && x < 10 compares first and combines after: it is true for every x strictly between 0 and 10.
the right side may never run
When the left operand of && or || already decides the result, Java does not evaluate the right one. This is short-circuit evaluation.
false && anything is false, and true || anything is true, whatever the right side would say. So the right side is skipped. The figure evaluates two expressions, first with x = 4, then with x = 0:
x != 0 && 10 / x > 2 x == 0 || 10 / x > 2
With x = 4 both sides of both run. 10 / 4 is 2 (integer division), not more than 2, so the first is false and so is the second.
With x = 0, x != 0 is false, so the first is false at once; and x == 0 is true, so the second is true at once. In neither does 10 / x run, which is just as well: dividing an int by zero throws an ArithmeticException.
That makes the left operand a guard. Written the other way round, 10 / x > 2 && x != 0 divides first and crashes when x is 0.
truth tables and De Morgan’s laws
Two Boolean expressions are equivalent if they evaluate to the same value in all cases. A truth table, with a row for every combination of inputs, can prove it.
De Morgan’s laws give two equivalences:
!(a && b) is equivalent to !a || !b !(a || b) is equivalent to !a && !b
To push a ! inside parentheses, negate each part and swap && for ||, or || for &&. In the figure each column of the second expression slides onto the first: the colors match in every row.
| a | b | !(a && b) | !a || !b | !(a || b) | !a && !b |
|---|---|---|---|---|---|
| true | true | false | false | false | false |
| true | false | true | true | false | false |
| false | true | true | true | false | false |
| false | false | true | true | true | true |
Forgetting to swap the operator breaks it: !(a && b) and !a && !b differ in 2 of the 4 rows. A negated comparison flips the operator: !(x > 5) is x <= 5. So !(x >= 1 && x <= 10) is equivalent to x < 1 || x > 10.
== against equals
Two different variables can hold references to the same object. == and != on references ask whether they refer to the same object, not whether two objects hold the same contents.
String s1 = new String("atlas"); String s2 = s1; String s3 = new String("atlas"); String s4 = null; s2 = s1 copies the reference, so s1 and s2 point at one object: s1 == s2 is true. s3 refers to a second object with the same letters: s1 == s3 is false.
Classes often define an equals method that says when two objects count as equal, usually by comparing their attributes. String’s compares the characters, so s1.equals(s3) is true. Compare strings with equals, never ==.
A reference can be compared with null using == or !=, to find whether it refers to an object at all: s4 == null is true. (Overriding the equals method is outside the scope of the course.)
check, run, check again
Iteration is a form of repetition: an iteration statement repeats a segment of code zero or more times, as long as its Boolean expression is true.
In a while loop the Boolean expression is evaluated before each pass through the body, including the first. While it is true the body runs; when it is false the loop ends and the program goes on after it.
int sum = 0; int k = 1; while (k <= 4) { sum += k; k++; } System.out.println(sum); A trace table records the variables each time the condition is checked. The figure fills it row by row:
| k | sum | k <= 4 |
|---|---|---|
| 1 | 0 | true |
| 2 | 1 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 10 | false |
The condition is checked 5 times and the body runs 4 times: the last check is the one that is false. The loop ends with k = 5, and 10 is printed.
never, forever, one short
Most loop bugs are one of three: the loop never runs, never stops, or runs one time too many or too few.
If the Boolean expression is false the first time, the body never executes. while (k < 5) with k at 10 checks once and moves on (top row).
An infinite loop happens when the Boolean expression always evaluates to true. In the middle row k goes 1, 3, 5, 7, 9, … and is never 6, so while (k != 6) never becomes false. A loop whose body never changes the variables in its condition does the same.
An off-by-one error is a loop that runs one time too many or one time too few. Meant to print 1 to 5, the bottom loop prints 1234: while (k < 5) stops before 5. k <= 5 fixes it.
int k = 1; while (k < 5) { System.out.print(k); k++; } Check a loop at its edges: the first pass, the last pass, and the check that ends it.
initialization, Boolean expression, update
A for loop puts the three parts of a counting loop in its header: the initialization, the Boolean expression and the update.
for (int i = 0; i < 3; i++) { System.out.println(i); } The initialization runs once, before the first check. The variable it sets is the loop control variable. The Boolean expression is evaluated right after the initialization, and then again after each update, until it is false. In each pass the update runs after the whole body and before the next check.
The figure’s token goes initialization → check → body → update → check …. The counts under each station: initialization 1, check 4, body 3, update 3. It prints 0, 1, 2, each on its own line.
A for loop can be rewritten as an equivalent while loop, and the other way round:
int i = 0; while (i < 3) { System.out.println(i); i++; } One difference: i declared in the for header exists only inside the loop; declared before a while loop, it is still there afterwards.
% 10, / 10 and % k
Two standard algorithms use the remainder operator: taking an integer apart digit by digit, and testing whether one integer is evenly divisible by another.
For a positive int n, n % 10 is its last digit and n / 10 (integer division) is n with that digit removed. Repeat until n is 0:
| n | n % 10 | n / 10 |
|---|---|---|
| 3725 | 5 | 372 |
| 372 | 2 | 37 |
| 37 | 7 | 3 |
| 3 | 3 | 0 |
int n = 3725; int sum = 0; int max = 0; int odd = 0; while (n > 0) { int d = n % 10; sum += d; if (d > max) { max = d; } if (d % 2 == 1) { odd++; } n /= 10; } The figure peels the digits of 3725 off from the right, 5, 2, 7, 3, and each one passes through d.
a % b == 0 is true exactly when a is evenly divisible by b. 3725 % 5 is 0, so 3725 is divisible by 5; 3725 % 3 is 2, so it is not divisible by 3. The same test with 2 sorts even from odd, as d % 2 == 1 does in the loop.
accumulating as the loop runs
Three more standard algorithms keep a running value in a variable declared before the loop and updated inside it: a sum, a minimum or maximum, and a count.
A sum starts at 0 and adds each value: sum += d. For 3725, sum ends at 17.
An average is the sum divided by how many values there were. Watch the integer division:
double avg = (double) sum / 4; int avgInt = sum / 4;
avg is 4.25; avgInt is 4, the fraction thrown away. Cast before dividing, not after.
A maximum keeps the largest value so far and replaces it whenever a bigger one comes: if (d > max). Here max ends at 7. Start it at the first value, or at a value no real one can be below: 0 works only because digits are never negative; in general use Integer.MIN_VALUE. A minimum is the mirror image, starting at Integer.MAX_VALUE and testing <; the smallest digit is 2.
A count of how often a criterion is met starts at 0 and adds 1 inside an if: if (d % 2 == 1) counts the odd digits, 3 of them.
reverse, and count substrings
String algorithms walk an index along a string and take a substring at each position: to build a new string, or to test or count substrings with some property.
To reverse a string, put each character in front of what has been built so far. substring(i, i + 1) is the single character at index i:
String word = "drawer"; String rev = ""; for (int i = 0; i < word.length(); i++) { rev = word.substring(i, i + 1) + rev; } rev grows "d", "rd", "ard", "ward", "eward", "reward". (rev = rev + word.substring(i, i + 1) would copy the word unchanged.)
To count substrings that meet a criterion, slide a window along and test each one:
String s = "banana"; int count = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.substring(i, i + 2).equals("an")) { count++; } } The window substring(i, i + 2) looks at "ba", "an", "na", "an", "na": 2 match, so count is 2. The last window starts at index 4, so i must stop below s.length() - 1; one step further, substring(5, 7) runs past the end and throws a StringIndexOutOfBoundsException.
Compare substrings with equals. To find whether any substring has the property, the same loop can stop at the first one found, or indexOf returns where a given substring first appears, −1 if nowhere.
a loop inside a loop
Nested iteration is a loop in the body of another loop. The inner loop runs all its iterations before the outer loop goes on to its next one.
for (int r = 0; r < 3; r++) { for (int c = 0; c < 4; c++) { System.out.print(r * c + " "); } System.out.println(); } For r = 0 the inner loop runs c from 0 to 3; then println ends the line, and only then does r become 1. The figure lights the grid cell by cell, row after row: the inner body runs 3 × 4 = 12 times and prints
0 0 0 0 0 1 2 3 0 2 4 6
The inner loop’s bounds can depend on the outer variable. Here the inner loop runs r + 1 times, so the passes are 1, 2, 3, 4:
int count = 0; for (int r = 0; r < 4; r++) { for (int c = 0; c <= r; c++) { count++; } } count ends at 10, a triangle instead of a rectangle.
counting how often a statement runs
A statement execution count is the number of times a statement runs. It is usually found informally, by tracing a few passes and reasoning about the loops.
for (int i = 0; i < n; i++) { count++; } With i from 0 to n − 1, count++ runs n times. The check i < n runs n + 1 times: once more, to end the loop.
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; } } Nested, each of the n outer passes runs the inner loop n times: count++ runs n × n times. For n = 6 that is 6 against 36; for n = 8, 8 against 64. The figure grows both as n climbs: doubling n doubles one and quadruples the other.
Count from the loop bounds. for (int i = 1; i <= n; i++) also runs n times; i < n starting at 1 runs n − 1; a triangle like the one on the last page runs 1 + 2 + … + n times. Comparing such counts is how to say one loop is faster than another without a stopwatch.