53 flashcard terms for AP Computer Science A Unit 4, written to match the course framework. Read them here, drill them as flashcards, or take the 44-question quiz. Free, no account needed.
A property that holds before and after every iteration, such as 'sum equals the total of elements 0..i-1'. Reasoning with invariants lets you predict a loop's final result without tracing every step.
Off-by-one Errors
Using <= where < was needed (or vice versa) runs the loop one extra or one fewer time. Check the first and last iteration values explicitly.
Sentinel-controlled Loop
A while loop that continues until a special value (like -1 or an empty string) appears. The number of iterations is unknown in advance.
Counting Loop Iterations
for (int i = a; i <= b; i++) runs b - a + 1 times; with i < b it runs b - a times. Step size k gives roughly (b - a) / k iterations.
Nested Loop Iteration Count
An inner loop that runs m times inside an outer loop of n iterations executes its body n × m times. Triangular patterns (inner bound depends on outer variable) give 1+2+...+n = n(n+1)/2.
Loop Variable Scope
A variable declared in the for header exists only inside the loop. Reading it after the loop is a compile error; declare it before the loop if you need the final value.
Infinite Loop Causes
Forgetting to update the loop variable, updating in the wrong direction, or a condition that can never become false. while (x != 10) with x incrementing by 3 from 0 never terminates.
A while or for loop whose condition is false initially never runs its body. Contrast with do-while (not in the AP subset), which always runs once.
Accumulator Pattern
Initialize a total (0 for sums, 1 for products, "" for strings) before the loop and update it each iteration. Initializing inside the loop resets it every pass.
Finding Max/Min in a Loop
Initialize to the first element or to Integer.MIN_VALUE for max; update when a better value appears. Initializing max to 0 fails when all values are negative.
Digit Loop
while (n > 0) { digit = n % 10; ... n /= 10; } visits digits from right to left. To preserve n, copy it to a temporary variable first.
String Traversal
for (int i = 0; i < s.length(); i++) with s.substring(i, i + 1) or s.charAt(i) visits each character. Using <= s.length() throws an exception at the last index.
Searching a String for a Substring
for (int i = 0; i <= s.length() - sub.length(); i++) if (s.substring(i, i + sub.length()).equals(sub)) counts occurrences, including overlapping ones.
Building a Reversed String
String rev = ""; for each char c from left to right rev = c + rev; prepending each character reverses the order.
Loop with Multiple Exit Conditions
while (i < n && !found) stops when either the data runs out or the target appears. Check which condition ended the loop after it exits.
Nested Loop Output Patterns
Outer loop controls rows, inner loop controls columns; use System.out.print in the inner loop and System.out.println() after it to end each row.
Algorithm Efficiency (Statement Count)
The AP exam asks how many times a statement executes, not big-O. Count iterations of each enclosing loop and multiply for nested loops.
Loop Condition Evaluated Every Pass
The condition of a while or for loop is re-evaluated before each iteration, including method calls like s.length(); changing s inside the loop changes the bound.
Converting while to for
for (init; cond; update) body; is equivalent to init; while (cond) { body; update; } except for scope of the loop variable.
Prime Test Loop
for (int d = 2; d * d <= n; d++) if (n % d == 0) return false; return n > 1; checks divisors up to the square root, halting early on the first divisor found.
Loop Invariant Reasoning
An invariant is a statement true before the loop, preserved by every iteration, and therefore true at exit — it is how correctness is proved rather than guessed.
Counting Iterations of a for Loop
for (int i = a; i < b; i++) runs b - a times when b >= a, and zero times otherwise; changing < to <= adds exactly one iteration.
Step Size Changes the Count
for (int i = 0; i < n; i += k) executes ceil(n / k) times, so a step of 3 over 10 values gives 4 iterations.
Nested Loop Multiplication
Independent nested loops of m and n iterations execute the inner body m * n times, which is why nesting drives quadratic growth.
Triangular Nested Loops
When the inner bound depends on the outer index, as in for (j = i; j < n; j++), the body runs n(n + 1) / 2 times rather than n^2.
Doubling n roughly doubles the work of a single loop but quadruples the work of a doubly nested loop, which is the AP way of comparing efficiency.
Halving Loops Are Logarithmic
while (n > 0) { n /= 2; } runs about log2(n) + 1 times, the same pattern that makes binary search fast.
Condition Re-evaluated Every Pass
A loop bound that calls a method or reads a changing variable is recomputed each iteration, so mutating the collection inside the body changes the bound.
Sentinel Loop Structure
Read a value, then loop while it is not the sentinel, reading again at the end of the body; the sentinel itself must not be processed.
Priming Read
A sentinel-controlled while loop needs one read before the loop so the condition has something to test on the first evaluation.
do-while Beyond the Subset
A do-while always executes its body at least once. It is outside the AP subset, so equivalent logic must be written with a while loop and a flag.
break and continue Are Not Tested
The AP Java subset avoids break and continue in loops, so early exit is expressed with a boolean flag in the loop condition.
Two-pointer Traversal
Advancing an index from each end toward the middle checks a palindrome or reverses in place in about n / 2 iterations.
Accumulating Two Quantities
Tracking a sum and a count in the same pass lets the average be computed after the loop with one double division.
Running Maximum with Index
Store both the best value and where it occurred so the loop can report the position, initializing from element 0 rather than from zero.
Loop Fusion
Two loops over the same range can often be merged into one pass, halving the traversal cost without changing the result.
String Building in a Loop
Repeated concatenation creates a new String each pass, so an n-character build performs work proportional to n^2 in total.
Traversing Every Other Element
Starting at index 1 with i += 2 visits the odd positions, a pattern used for alternating-sign sums and checksum digits.
Detecting the First Occurrence
Use a flag or a stored index initialized to -1 so the loop can report that nothing was found without a special exception path.
Nested Loop Output Shapes
Printing i stars on row i produces a triangle; printing n stars on every row produces a rectangle. The inner bound controls the shape.
Infinite Loop Diagnosis
A loop never terminates when the control variable is not updated, is updated in the wrong direction, or the condition can never become false.
Converting between while and for
Any for loop can be rewritten as an initialization, a while with the same condition, and an update at the end of the body — noting that scope of the counter changes.