Unit 02
Selection and Iteration
Decisions and repetition, the two things that turn a list of instructions into a program that responds to the world.
Every check for understanding filed under this unit, and where each one stands with your classes. The whole console →
- Counting the trips checking
- Why the null check comes first checking
- Sequencing, selection, repetition checking
- At least, more than, under checking
- The branch that never runs checking
- Same object, or same contents checking
- Remainders, digits, and a maximum checking
- How much work is that checking
Unit 1 was about saying things to the machine. This unit is about the machine saying something back — asking a question and taking one road instead of another, doing the same work a thousand times without you typing it a thousand times.
Two ideas cover all twelve topics. Selection is choosing. Iteration is repeating. Everything else here is detail about how Java spells them, and the detail matters, because the difference between a loop that runs four times and one that runs five is usually a single character.
2.1 · Algorithms with selection and repetition
Before any Java: an algorithm is built from exactly three things.
- Sequencing — do this, then that. Order matters.
- Selection — decide, based on something being true or false, which of two paths to take.
- Repetition — do something again until you have what you wanted.
You already use all three without naming them. A fire drill is sequencing. “If the alarm is a continuous tone, use the east stairs” is selection. “Keep walking until you reach the field” is repetition. The reason to name them is that once you can spot them in English you can spot them in code, and the reverse: describing what a loop does in a sentence is how you find out whether you understood it.
The order you combine the three in is part of the algorithm, not a detail of presentation. Add the eggs, then check whether the mix is too thick and check whether the mix is too thick, then add the eggs are different procedures that disagree about what is being tested. Java will not notice; only you will.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
A recipe says: "Heat the pan. If the butter browns, lower the heat. Stir until the sauce thickens." Which building blocks are in it?
Every algorithm you will write this year is made of three things: sequencing (do this, then that), selection (decide which way to go), and repetition (do it again until something is true). You can find all three in a recipe, a fire drill, or a bus timetable — which is the point of starting here rather than in Java.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
Two versions of the same instructions. A: "Add the eggs. If the mix is too thick, add milk." B: "If the mix is too thick, add milk. Add the eggs." Do they do the same thing?
The order in which sequencing, selection, and repetition are combined is part of the algorithm, not a formatting choice. Moving a test above the step that changes what it tests is one of the most common logic errors there is, and it survives translation into Java untouched — the compiler has no opinion about it.
2.2 · Boolean expressions
A Boolean expression is any expression whose value is true or false.
That is all a condition is: an expression that happens to have a boolean type.
Six relational operators produce them:
| Operator | Asks |
|---|---|
== |
are these the same? |
!= |
are these different? |
< > |
is this smaller / larger? |
<= >= |
smaller-or-equal / larger-or-equal? |
int score = 85;
boolean passed = score >= 60; // true
System.out.println(score != 85); // falseTwo things students trip over immediately. First, == is not =. One equals
sign assigns; two compare. In Java, writing if (lives = 0) does not
silently destroy your variable the way it would in C — it fails to compile,
because an int turned up where a boolean was required. That is Java
protecting you from a bug other languages ship.
Second, == and != mean something different for reference types than for
primitives, and that difference gets its own topic at 2.6. For now: on int,
double and boolean, == compares the values, and that is exactly what you
would expect.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What does this print?
int score = 85;
System.out.println(score != 85);!= is one operator, not a negated assignment. It asks a question and answers true or false — nothing else. Say the condition out loud in English before you decide; it catches this every time.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What does this print?
int a = 4;
int b = 9;
boolean smaller = a < b;
System.out.println(smaller);A relational operator is an expression, and its value is a boolean — so it can be stored, passed to a method, or negated, exactly like any other value. Once you see that, if (smaller) stops looking like a special form of if and starts looking like what it is: a boolean being read.
The other half of getting a condition right is the boundary. At least 48 inches, more than 48 inches and under 48 inches are three different rules, and the only way to be sure you picked the right operator is to put the boundary value itself in and check the answer you get.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
A ride requires you to be at least 48 inches tall. Which condition lets in exactly the right people?
int height = 48;Nearly every off-by-one bug is a boundary read too fast. Translate the English first — at least, more than, up to, under — and only then pick the operator. Then test the boundary itself: put the exact value in and check that the answer is the one you meant.
2.3 · if statements
An if statement is one test with two ways down, and you take exactly one of
them.
if (temperature > 80) {
System.out.println("hot");
}
System.out.println("done");That is a one-way selection: run the body, or skip it. Note what is not
conditional — the line after the closing brace runs either way. If you want
something to happen in the false case you have to say so, with else:
if (temperature > 80) {
System.out.println("hot");
} else {
System.out.println("not hot");
}That is a two-way selection, and exactly one of the two bodies runs. Never both, never neither.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What does this print when temp is 70?
int temp = 70;
if (temp > 80) {
System.out.println("hot");
}
System.out.println("done");A one-way selection has exactly one conditional path: run the body, or do not. There is no hidden "otherwise". If you want something to happen in the false case you have to write an else — and noticing that you have not is the difference between code that is silent when it should speak and code that is right.
The semicolon that ends the sentence early
A single ; is a legal statement in Java that does nothing. That fact plus a
typo produces the most confusing bug in this unit, because the code compiles and
runs and is wrong.
Find the error · java
One line is wrong
This always prints. Which line is responsible?
The ; at the end of line 2 is the entire body of the if — a statement that does nothing. The braces below are then just a block, and a block on its own always runs. Read a semicolon as a full stop and this becomes visible: the sentence finished before the braces arrived.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
This compiles and always prints. Why?
int x = 1;
if (x > 3);
{
System.out.println("big");
}A lone ; is a legal statement in Java — it does nothing — so if (x > 3); is a complete if whose body is that nothing. The braces underneath are then just a block, and a block on its own always executes. This is the reason it is worth reading a semicolon as a full stop: one at the end of an if line finishes the sentence early.
2.4 · Nested if statements
Put an if inside an if and the inner condition is only ever asked when the
outer one was true. That is what nesting means, and it is why nesting is not
quite the same thing as && even when the result is identical — a nested if
lets you do work in between the two tests.
if (age >= 18) {
System.out.println("adult");
if (hasTicket) {
System.out.println("enjoy the film");
}
}Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
How many lines print?
int age = 12;
boolean hasTicket = true;
if (age >= 18) {
System.out.println("adult");
if (hasTicket) {
System.out.println("enjoy the film");
}
}The inner condition is only asked when the outer one is true. That is what nesting means, and it is why nesting is not the same as && in your head even when it is the same in result — a nested if lets you do work between the two tests, which a single compound condition cannot.
else if, and why order is the whole game
A multiway selection is a ladder of conditions tested top to bottom. The first true one runs, and the rest are never even asked.
if (score >= 90) {
System.out.println("excellent");
} else if (score >= 60) {
System.out.println("pass");
} else {
System.out.println("fail");
}Swap those first two branches and the code still compiles, still runs, and is
permanently wrong: every score at or above 90 is also at or above 60, so the
excellent branch becomes unreachable for every possible input. Nothing warns
you. The rule that prevents it is simple — order your conditions from
narrowest to widest — and it is the same mistake as checking for “animal”
before “dog”.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What is printed?
int score = 95;
if (score >= 60) {
System.out.println("pass");
} else if (score >= 90) {
System.out.println("excellent");
} else {
System.out.println("fail");
}A multiway selection is tested top to bottom and stops at the first true condition. 95 >= 60 is true, so pass prints and excellent is unreachable for every possible score. The fix is ordering: put the most specific test first. This is one of the few bugs that a careful read catches faster than a debugger.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
Which line can never run, no matter what n is?
if (n > 0) {
System.out.println("positive");
} else if (n > 100) {
System.out.println("very large");
} else {
System.out.println("zero or negative");
}Every value that satisfies n > 100 also satisfies n > 0, and the first true branch wins — so the second branch is dead code that the compiler will not warn you about. Order your conditions from narrowest to widest and this class of bug disappears. It is the same mistake as checking for "animal" before "dog".
2.5 · Compound Boolean expressions
Three logical operators combine conditions.
a && b— and. True only when both are.a || b— or. True when either is, or both.!a— not. Flips it.
Precedence runs !, then &&, then ||. So !a && b means (!a) && b, not
!(a && b) — the two are genuinely different expressions and the parentheses
are not decoration. Once a condition has three parts, write the parentheses even
where you would not need them. The next person reading it is you, in April.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What does this print?
boolean a = false;
boolean b = false;
System.out.println(!a && b);! binds tighter than &&, which binds tighter than ||. So !a && b means (!a) && b — true and false, which is false. If you meant !(a && b) you have to write the parentheses. When a condition has more than two parts, write the parentheses even where precedence would have got it right: the next reader is you.
Short-circuit evaluation
&& and || stop as soon as the answer is settled. If the left side of an
&& is false, the whole thing is false whatever the right side says, so Java
does not evaluate the right side at all.
That is not a performance trick, it is a tool. It is what makes this the standard way to look inside something that might not be there:
if (name != null && name.length() > 0) {
System.out.println("has a name");
}Swap the two halves and it throws immediately. The order of the operands is doing real work.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
Does this throw?
String name = null;
if (name != null && name.length() > 0) {
System.out.println("has a name");
}&& evaluates left to right and stops the moment the answer is settled. name != null is false, so the whole expression is false and the right side is never touched. Swap the two halves and it throws immediately — the order is doing real work.
2.6 · Comparing Boolean expressions
Two expressions are equivalent when they produce the same value for every possible input — not for the input you happened to try. The only way to be sure is to check every row.
De Morgan’s laws say you can push a ! inward if you flip the operator as
you go. !(a && b) becomes !a || !b. Predict before you look:
Truth table
Predict first
Do these two always agree?
!(a && b) !a || !b | a | b | !(a && b) | !a || !b | Same? |
|---|---|---|---|---|
| true | true | · | · | |
| true | false | · | · | |
| false | true | · | · | |
| false | false | · | · |
Every row matches, so the two expressions are interchangeable. That is what De Morgan's law buys you: a way to rewrite a negated condition without changing what it means.
Now the mistake almost everybody makes the first time — negating both operands but leaving the operator alone:
Truth table
Predict first
And these — do they always agree?
!(a && b) !a && !b | a | b | !(a && b) | !a && !b | Same? |
|---|---|---|---|---|
| true | true | · | · | |
| true | false | · | · | |
| false | true | · | · | |
| false | false | · | · |
They come apart on exactly the two rows where one is true and the other is false. !a && !b demands that both be false; !(a && b) only demands that they not both be true. Negating the operands is half the job — the operator has to flip too, or you have written a much stricter condition than you meant.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
Which of these is equivalent to !(raining || cold)?
De Morgan's law: !(a || b) is !a && !b, and !(a && b) is !a || !b. The operator flips as the ! moves inward — negating the operands and leaving || alone produces a much weaker condition. Read the correct answer in English and it is obvious: not (raining or cold) is not raining and not cold.
Comparing objects, not values
On primitives, == compares values. On reference types it compares
references — is this the same object? — which is almost never the question you
meant to ask.
String x = new String("hello");
String y = new String("hello");
System.out.println(x == y); // false — two objects
System.out.println(x.equals(y)); // true — same charactersequals is a method a class defines to say what counts as the same for that
class. For String it means the same characters in the same order. Comparing
Strings with == is the most common single bug in this course, and it is
particularly cruel because small literals often work by accident.
== and != do have one honest job on references: comparing against null, to
find out whether a variable refers to an object at all.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What does this print?
String x = new String("hello");
String y = new String("hello");
System.out.println(x == y);
System.out.println(x.equals(y));On primitives, == compares values. On reference types it compares references — is this the same object? — and new guarantees two different ones. equals is the method a class defines to answer "are these two the same for our purposes", which for String means the same characters in the same order. Comparing Strings with == is the single most common bug in this course.
2.7 · while loops
Iteration is repetition with a condition on it. A while loop tests, then runs
the body, then tests again — zero or more times, which is worth saying
carefully: if the condition is false at the start, the body never runs at all.
int i = 1;
while (i <= 5) {
System.out.println(i);
i++;
}Every loop needs three things, and a while loop makes you put them in three
different places: a starting value above the loop, a condition in the
header, and a change inside the body that moves toward failing the
condition. Leave out the third and you have written an infinite loop.
Predict the number of passes before you run it. Type your answer in:
Loop trace
Predict first
How many times does the loop body run?
int i = 1;
while (i <= 5) {
System.out.println(i);
i++;
}| Pass | i | Printed |
|---|---|---|
| 1 | · | · |
| 2 | · | · |
| 3 | · | · |
| 4 | · | · |
| 5 | · | · |
| — | · | · |
Five passes, then the check fails at i = 6. The last row of the table is not a sixth pass — it is the test that ended the loop, and it is the row people forget to count when they are working out where a loop stopped.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
How many times does the body of this loop execute?
int count = 0;
int i = 5;
while (i > 0) {
count = count + 1;
i = i - 2;
}
System.out.println(count);Trace it rather than eyeball it: i = 5 (run, count 1), i = 3 (run, count 2), i = 1 (run, count 3), i = −1 (test fails). Three passes. A loop that decreases by more than one is the standard trap here. The answer is not 5.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
How many times does the body run?
int n = 10;
while (n < 5) {
System.out.println(n);
n++;
}A while loop evaluates its condition before each pass, including the first — so "zero or more times" is the honest description of what it does. Assuming a loop runs at least once is a good way to write a sum that is right in testing and wrong on the empty case.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
This loop never ends. What is missing?
int i = 0;
while (i < 5) {
System.out.println(i);
}Three things every loop needs: a starting value, a condition, and a change that moves toward failing the condition. This one has two of the three. A for loop puts all three on one line, which is exactly why it exists.
2.8 · for loops
A for loop is a while loop with its three moving parts collected onto one
line, in the order you need them:
for (int i = 1; i <= 5; i++) {
System.out.println(i);
}The header holds the initialization (once, before anything else), the
Boolean expression (tested before every pass, including the first), and the
update (after the body, before the next test). Nothing is more powerful here
than a while loop — it is just much harder to leave half-written, which is why
it is the right choice whenever you are counting.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What is printed?
for (int i = 0; i < 3; i++) {
System.out.print(i);
}The order for each pass is: test, then body, then update. The initialization happens once, before any of it. Getting this order right is what makes the difference between 012 and 123, and it is exactly what a trace table is for — one column per variable, one row per pass.
Here is the same trace as the one at 2.7, produced by a for loop instead of a
while:
Loop trace
Predict first
How many times does the loop body run?
int i = 1;
while (i <= 5) {
System.out.println(i);
i++;
}| Pass | i | Printed |
|---|---|---|
| 1 | · | · |
| 2 | · | · |
| 3 | · | · |
| 4 | · | · |
| 5 | · | · |
| — | · | · |
Same frames as the while loop at 2.7 — because it is the same loop.
This is 2.8.A.3 demonstrated rather than asserted: a for loop can be rewritten as an equivalent while loop and vice versa. Not similar — the same passes, the same values, the same stopping point. Choosing between them is a question of what is easiest to read, never of what is possible.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
Which while loop does exactly what "for (int i = 0; i < 3; i++)" does?
A for loop is a while loop with its three moving parts collected onto one line. Neither is more powerful; the for is just harder to leave half-written, which is why it is the right choice whenever you are counting. Being able to convert one into the other is the point of 2.8.A.3.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What is printed?
int sum = 0;
for (int i = 1; i <= 4; i++) {
sum += i;
}
System.out.println(sum);Write the values of i in a row before you add anything: 1, 2, 3, 4. Then add. The whole difficulty in loop questions is knowing which values the counter actually takes, and < versus <= is the one detail that decides it.
< or <=
This one character decides how many times the loop runs, and it is worth more exam points than any other detail in the unit.
Loop trace
Predict first
How many times does this loop body run?
int sum = 0;
for (int i = 0; i <= 3; i++) {
sum += i;
}| Pass | i | sum |
|---|---|---|
| 1 | · | · |
| 2 | · | · |
| 3 | · | · |
| 4 | · | · |
| — | · | · |
Four passes, because i <= 3 lets i take the values 0, 1, 2 and 3. Write the values the counter actually takes in a row before you do anything else — that habit is what turns an off-by-one from a coin flip into a calculation.
2.9 · Implementing selection and iteration algorithms
A handful of small algorithms come up again and again, in this course and on the exam. Learn the shapes, not the examples.
Divisibility and digits both come from %, which gives the remainder:
if (n % 3 == 0) { /* n divides evenly by 3 */ }
int lastDigit = n % 10;
int rest = n / 10; // integer division throws the digit awayQuick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
Which condition is true exactly when n is evenly divisible by 3?
% gives the remainder, and "divides evenly" means "leaves no remainder". This one line is the whole of the divisibility algorithm the CED names — and it is also how you test for even (n % 2 == 0), pull off the last digit (n % 10), and wrap a counter round a fixed range.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What is printed?
int n = 407;
while (n > 0) {
System.out.print(n % 10);
n = n / 10;
}The pair n % 10 and n / 10 is the standard digit-extraction algorithm: the remainder is the last digit, integer division throws that digit away. It comes out backwards, which is a feature as often as it is a nuisance — it is how you reverse a number, and it is why palindrome questions are easier than they look.
Accumulating — a sum, a count, an average — is always the same four moves: declare a total before the loop, add to it inside, do nothing to it in the header, use it after.
Loop trace
Predict first
How many times does the loop body run?
int sum = 0;
for (int i = 1; i <= 6; i++) {
sum += i;
}| Pass | i | sum |
|---|---|---|
| 1 | · | · |
| 2 | · | · |
| 3 | · | · |
| 4 | · | · |
| 5 | · | · |
| 6 | · | · |
| — | · | · |
Watch the sum column rather than the i column. The counter is scaffolding; the accumulator is the answer, and it is the only variable that still matters after the loop ends.
Finding a maximum looks like accumulating but has a trap in it: what you
start from. Seed the running maximum with a convenient constant like 0 and
your method will confidently report a value that was never in the data.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
This is meant to find the largest of the three values it sees. Why can it fail?
int max = 0;
int[] readings = {-5, -12, -3};
for (int i = 0; i < 3; i++) {
if (readings[i] > max) {
max = readings[i];
}
}
System.out.println(max);Seeding an accumulator with a convenient-looking constant is the classic maximum bug, and it hides completely in test data that happens to be positive. Start from the first element (int max = readings[0];) and loop from index 1 — then the answer is always a value that was really there.
Now write one yourself. Sum the whole numbers from 1 to n:
Write it · java
Checked on submit · retry as often as you like
Write a loop that adds every whole number from 1 up to n into a variable called total. Assume n is already declared and total starts at 0.
The closed form n(n+1)/2 is the right answer in mathematics and the wrong answer to this question — the point is the accumulator pattern, which generalises to sums, counts, averages and maxima, none of which have a closed form.
2.10 · Implementing String algorithms
Strings are where selection and iteration meet the methods from Unit 1. The
loop is always the same: walk every index from 0 to length() - 1 and look
at one character’s worth of String at a time.
for (int i = 0; i < s.length(); i++) {
String ch = s.substring(i, i + 1);
// ...
}i < s.length() and not i <= s.length(). A String of length 4 has indices
0 through 3, so <= walks one step past the end and throws at run time — the
compiler cannot see it coming, because it does not know how long the String is.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
How many times does this loop run, and does it throw?
String word = "code";
for (int i = 0; i <= word.length(); i++) {
System.out.print(word.substring(i, i + 1));
}A String of length 4 has indices 0 through 3. i <= word.length() lets i reach 4, and the exception comes from the machine at run time — the compiler had no way to see it coming. Use < and the loop is right.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
What is printed?
String s = "banana";
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.substring(i, i + 1).equals("a")) {
count++;
}
}
System.out.println(count);This is the standard counting algorithm and the shape is always the same: a counter starting at zero, a loop over every position, a condition, and one increment inside it. Note equals rather than == — substring hands back a new String each time, so == would compare two different objects and count nothing.
Predict the output of this one before you open it:
Trace the code · java
Checked on submit · retry as often as you like
What does this print?
1String s = "stop";
2String out = "";
3for (int i = 0; i < s.length(); i++) {
4 out = s.substring(i, i + 1) + out;
5}
6System.out.println(out);
Each character is glued to the front of what has been built so far, so the String comes out backwards. Swap the two operands — out + s.substring(...) — and you have rebuilt the original. That one difference is the whole reversal algorithm.
A chatbot is selection over strings
The Magpie lab, which anchors the second half of this unit, is nothing but an
if-else ladder over String searches. Here is the finished thing, running.
Say something to it and watch which branch answers.
Magpie
Nothing here is recorded
MagpieHello, let's talk.
-
statement.length() == 0→ Say something, please. -
findKeyword("no") >= 0→ Why so negative? -
findKeyword("mother") >= 0 || ...→ Tell me more about your family. -
else — getRandomResponse()
The rules are Laurie White's, from the Magpie starter. Note that saying I know does not trigger the no rule — finding a keyword is harder than finding a substring, and that gap is the lab.
2.11 · Nested iteration
A loop inside a loop. The inner one runs all the way through for every single pass of the outer one.
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 4; col++) {
System.out.print("*");
}
System.out.println();
}Three outer passes, four inner passes each: twelve stars. When both bounds are fixed like that, nested loops multiply.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
How many times does the inner statement execute?
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 4; c++) {
System.out.print("*");
}
}Nested loops multiply: 3 outer passes × 4 inner passes = 12. This is also the first place you meet run-time cost — double both numbers and the work quadruples, which is what Unit 2.12 is warning you about.
When the inner bound mentions the outer variable, they stop multiplying and start accumulating — the rows are different lengths, and the total is their sum:
Loop trace
Predict first
How many times does the inner print statement run?
for (int row = 1; row <= 4; row++) {
for (int col = 1; col <= row; col++) {
System.out.print("*");
}
System.out.println();
}| Pass | row | col | line | Printed |
|---|---|---|---|---|
| 1 | · | · | · | · |
| 2 | · | · | · | · |
| 3 | · | · | · | · |
| 4 | · | · | · | · |
| 5 | · | · | · | · |
| 6 | · | · | · | · |
| 7 | · | · | · | · |
| 8 | · | · | · | · |
| 9 | · | · | · | · |
| 10 | · | · | · | · |
| — | · | · | · | · |
Rows of 1, 2, 3 and 4 stars: ten passes in total, not sixteen. Watch the col column reset every time row advances — that reset is the inner loop starting over, which it does once per outer pass. This shape returns in Unit 4 as selection sort.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
How many stars are printed in total?
for (int row = 1; row <= 4; row++) {
for (int col = 1; col <= row; col++) {
System.out.print("*");
}
System.out.println();
}When the inner condition mentions the outer variable, the loops stop multiplying and start accumulating: the row lengths are 1, 2, 3, 4 and the total is their sum. This is the shape behind every triangle pattern, and behind selection sort in Unit 4 — which is why n(n+1)/2 is worth recognising when you see it.
2.12 · Informal run-time analysis
The last topic in the unit asks one question: how many times does this statement actually run? That is a statement execution count, and you get it by tracing, not by guessing.
One loop over n items does n passes. Two nested loops over n items do
n × n. So doubling the input doubles the work in the first case and
quadruples it in the second — which is why a method that is fine on ten
records can be unusable on ten thousand.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
How many times does the marked statement execute?
int total = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
total++; // <-- this one
}
}A statement execution count is exactly what it sounds like: how many times does this line actually run. You get it by tracing, not by guessing — and for two nested counting loops it is the product of their two counts. This is the whole of the informal run-time analysis the CED asks for; nothing here needs big-O notation.
Quick check · not graded, try as many times as you like
Add this question to
Loading your meetings…
A method has two nested loops, both running n times. It does 100 operations when n is 10. Roughly how many when n is 20?
Two nested loops over the same n do n × n passes, so doubling n multiplies the work by four, and tripling it multiplies by nine. You do not need any notation to see it — just count the passes for two different values of n and compare. Knowing which shape you have written is what stops a method that is fine on ten records from being unusable on ten thousand.
The project · Magpie
A chatbot that answers a person by looking at what they typed. It is the first lab of the AP CSA course for a reason: it is nothing but selection over strings, and it produces something you actually want to show someone.
The starter is Laurie White’s Magpie lab (April 2012), part of the AP CSA lab series. Ours lives at dadiletta/MagpieProject. Her code and her canned responses are hers; what you add is yours.
What you are given, and what you write
| Provided | Yours |
|---|---|
Magpie.java with getGreeting(), a starter getResponse(String), and getRandomResponse() |
Every new rule in getResponse |
findKeyword(statement, goal) and its three-argument overload |
Deciding which keywords are worth searching for |
MagpieRunner.java — a Scanner loop that runs until you type Bye |
Nothing. Read it, though: it is a real sentinel loop |
Read MagpieRunner before you touch anything else. It is eleven lines and it
contains two things from this unit — while (!statement.equals("Bye")) is a
sentinel-controlled loop, and it uses .equals rather than == for exactly the
reason 2.6 gave.
The milestones
Work in this order and test after each one. Each milestone is a working chatbot, which is what makes this lab pleasant instead of frightening.
- A canned response. Change what
getGreetingreturns, and add one branch togetResponsethat answers a single keyword. One rule, working, before you add a second. - Search with
indexOf. The plain version:statement.indexOf("mother") >= 0. Note the>= 0and not> 0— index 0 is a real position, andindexOfsignals not found by returning-1. Get this backwards and a keyword at the very start of a sentence is silently ignored. - Why
"mother"matches"grandmother". BecauseindexOffinds substrings, andgrandmothercontainsmother. Run into it deliberately, then read the providedfindKeywordand see how it fixes the problem: it checks the character on each side of the hit and only accepts the match when neither is a letter. That is why"I know"does not trigger the"no"rule. - Multiple keywords, case-insensitively. One branch answering several
related words with
||, and.toLowerCase()so thatMotherandmotherare the same word.findKeywordalready lowercases both sides — read it before you write your own.
Where it goes wrong
==on Strings. It compiles, and it compares references. Use.equals.indexOfreturning-1. Test with>= 0, not> 0and not!= 0.- No fallback. If every rule is an
ifwith no trailingelse, some inputs get an empty reply. There must be a branch that always matches. - Branch order. A broad rule above a narrow one makes the narrow one unreachable — the 2.4 problem, arriving in real code.
How it is graded
| Weight | |
|---|---|
| At least six distinct keyword rules, each responding sensibly | 40% |
Whole-word matching, so "mother" does not fire on "grandmother" |
20% |
| Case-insensitive, and a fallback branch that always answers | 20% |
| Readable: meaningful method names, no branch unreachable, commented where it is not obvious | 20% |
If you finish early: make it remember. A field that holds the last thing the user said lets you answer “you mentioned your brother earlier”, and that is one line of state away from everything Unit 3 is about.
Where this goes next
Unit 3 turns the Magpie class from something you edit into something you
design — fields, constructors, and the difference between what an object knows
and what it can do. Unit 4 gives your loops something worth looping over.
The framework, in full
Every topic College Board lists for this unit, with the learning objectives and essential knowledge in their words rather than mine. If something below isn't covered above yet, that gap is real. Open it, read the objective, then come find me.
-
2.1 Algorithms with Selection and Repetition 1 objective
2.1.A Represent patterns and algorithms that involve selection and repetition found in everyday life using written language or diagrams.
- 2.1.A.1The building blocks of algorithms include sequencing, selection, and repetition.
- 2.1.A.2Algorithms can contain selection, through decision making, and repetition, via looping.
- 2.1.A.3Selection occurs when a choice of how the execution of an algorithm will proceed is based on a true or false decision.
- 2.1.A.4Repetition is when a process repeats itself until a desired outcome is reached.
- 2.1.A.5The order in which sequencing, selection, and repetition are used contributes to the outcome of the algorithm.
-
2.2 Boolean Expressions 1 objective
2.2.A Develop code to create Boolean expressions with relational operators and determine the result of these expressions.
- 2.2.A.1Values can be compared using the relational operators == and != to determine whether the values are the same. With primitive types, this compares the actual primitive values. With reference types, this compares the object
- 2.2.A.2Numeric values can be compared using the relational operators <, >, <=, and >= to determine the relationship between the values.
- 2.2.A.3An expression involving relational operators evaluates to a Boolean value.
-
2.3 if Statements 1 objective
2.3.A Develop code to represent branching logical processes by using selection statements and determine the result of these processes.
- 2.3.A.1Selection statements change the sequential execution of statements.
- 2.3.A.2An if statement is a type of selection statement that affects the flow of control by executing different segments of code based on the value of a Boolean expression.
- 2.3.A.3A one-way selection (if statement) is used when there is a segment of code to execute under a certain condition. In this case, the body is executed only when the Boolean expression is true.
- 2.3.A.4A two-way selection (if-else statement) is used when there are two segments of code—one to be executed when the Boolean expression is true and another segment for when the Boolean expression is false. In this case, the body of the if is executed when the Boolean expression is true, and the body of the else is executed when the Boolean expression is false.
-
2.4 Nested if Statements 1 objective
2.4.A Develop code to represent nested branching logical processes and determine the result of these processes.
- 2.4.A.1Nested if statements consist of if, if-else, or if-else-if statements within if, if-else, or if-else-if statements.
- 2.4.A.2The Boolean expression of the inner nested if statement is evaluated only if the Boolean expression of the outer if statement evaluates to true.
- 2.4.A.3A multiway selection (if-else-if) is used when there are a series of expressions with different segments of code for each condition. Multiway selection is performed such that no more than one segment of code is executed based on the first expression that evaluates to true. If no expression evaluates to true and there is a trailing else statement, then the body of the else is executed.
-
2.5 Compound Boolean Expressions 1 objective
2.5.A Develop code to represent compound Boolean expressions and determine the result of these expressions.
- 2.5.A.1Logical operators ! (not), && (and), and || (or) are used with Boolean expressions. The expression !a evaluates to true if a is false and evaluates to false otherwise. The expression a && b evaluates to true if both a and b are true and evaluates to false otherwise. The expression a || b evaluates to true if a is true, b is true, or both, and evaluates to false otherwise. The order of precedence for evaluating logical operators is ! (not), && (and), then || (or). An expression involving logical operators evaluates to a Boolean value.
- 2.5.A.2Short-circuit evaluation occurs when the result of a logical operation using && or || can be determined by evaluating only the first Boolean expression. In this case, the second Boolean expression is not evaluated.
-
2.6 Comparing Boolean Expressions 2 objectives
2.6.A Compare equivalent Boolean expressions.
- 2.6.A.1Two Boolean expressions are equivalent if they evaluate to the same value in all cases. Truth tables can be used to prove Boolean expressions are equivalent.
- 2.6.A.2De Morgan’s law can be applied to Boolean expressions to create equivalent Boolean expressions. Under De Morgan’s law, the Boolean expression !(a && b) is equivalent to !a || !b and the Boolean expression !(a || b) is equivalent to !a && !b.
2.6.B Develop code to compare object references using Boolean expressions and determine the result of these expressions.
- 2.6.B.1Two different variables can hold references to the same object. Object references can be compared using == and !=.
- 2.6.B.2An object reference can be compared with null, using == or !=, to determine if the reference actually references an object.
- 2.6.B.3Classes often define their own equals method, which can be used to specify the criteria for equivalency for two objects of the class. The equivalency of two objects is most often determined using attributes from the two objects.
-
2.7 while Loops 2 objectives
2.7.A Identify when an iterative process is required to achieve a desired result.
- 2.7.A.1Iteration is a form of repetition. Iteration statements change the flow of control by repeating a segment of code zero or more times as long as the Boolean expression controlling the loop evaluates to true.
- 2.7.A.2An infinite loop occurs when the Boolean expression in an iterative statement always evaluates to true.
- 2.7.A.3The loop body of an iterative statement will not execute if the Boolean expression initially evaluates to false.
- 2.7.A.4Off by one errors occur when the iteration statement loops one time too many or one time too few.
2.7.B Develop code to represent iterative processes using while loops and determine the result of these processes.
- 2.7.B.1A while loop is a type of iterative statement. In while loops, the Boolean expression is evaluated before each iteration of the loop body, including the first. When the expression evaluates to true, the loop body is executed. This continues until the Boolean expression evaluates to false, whereupon the iteration terminates.
-
2.8 for Loops 1 objective
2.8.A Develop code to represent iterative processes using for loops and determine the result of these processes.
- 2.8.A.1A for loop is a type of iterative statement. There are three parts in a for loop header: the initialization, the Boolean expression, and the update.
- 2.8.A.2In a for loop, the initialization statement is only executed once before the first Boolean expression evaluation. The variable being initialized is referred to as a loop control variable. The Boolean expression is evaluated immediately after the loop control variable is initialized and then following each execution of the increment statement until it is false. In each iteration, the update is executed after the entire loop body is executed and before the Boolean expression is evaluated again.
- 2.8.A.3A for loop can be rewritten into an equivalent while loop (and vice versa).
-
2.9 Implementing Selection and Iteration Algorithms 1 objective
2.9.A Develop code for standard and original algorithms (without data structures) and determine the result of these algorithms.
- 2.9.A.1There are standard algorithms to: Bullet identify if an integer is or is not evenly divisible by another integer Bullet identify the individual digits in an integer Bullet determine the frequency with which a specific criterion is met Bullet determine a minimum or maximum value Bullet compute a sum or average
-
2.10 Implementing String Algorithms 1 objective
2.10.A Develop code for standard and original algorithms that involve strings and determine the result of these algorithms.
- 2.10.A.1There are standard string algorithms to: Bullet find if one or more substrings have a particular property Bullet determine the number of substrings that meet specific criteria Bullet create a new string with the characters reversed
-
2.11 Nested Iteration 1 objective
2.11.A Develop code to represent nested iterative processes and determine the result of these processes.
- 2.11.A.1Nested iteration statements are iteration statements that appear in the body of another iteration statement. When a loop is nested inside another loop, the inner loop must complete all its iterations before the outer loop can continue to its next iteration.
-
2.12 Informal Run-Time Analysis 1 objective
2.12.A Calculate statement execution counts and informal run-time comparison of iterative statements.
- 2.12.A.1A statement execution count indicates the number of times a statement is executed by the program. Statement execution counts are often calculated informally through tracing and analysis of the iterative statements.
Where you are
Not startedAnswer the checks above whenever you like. They're not graded, and you can retry any of them.
Sources
- College Board — AP Computer Science A Course and Exam Description, Effective Fall 2025
- Laurie White — Magpie Lab (AP Computer Science A lab series)
AP Computer Science A · members' unit
Selection and Iteration is behind a locked door
Units in AP Computer Science A are for people taking the course. Getting in takes a link or a key — signing in on its own doesn't do it.
What's in this unit · 19 min read
- 2.1 · Algorithms with selection and repetition
- 2.2 · Boolean expressions
- 2.3 · if statements
- 2.4 · Nested if statements
- 2.5 · Compound Boolean expressions
- 2.6 · Comparing Boolean expressions
- 2.7 · while loops
- 2.8 · for loops
- 2.9 · Implementing selection and iteration algorithms
- 2.10 · Implementing String algorithms
- 2.11 · Nested iteration
- 2.12 · Informal run-time analysis
- The project · Magpie
- Where this goes next
29 quick checksloop tracerchatbot sandboxtruth tablescode exercisesdebugging drills
1 Sign in
With your school Google account. This is how your work reaches the gradebook — it doesn't open the unit by itself.
A key unlocks this browser and keeps your progress here; signing in keeps it with you across devices. Either way the key itself is only ever checked as a hash. Manage all of this on your account, read what signing in stores, or go back to AP Computer Science A.