Selection and Iteration

Algorithms are built from three ideas: sequencing (steps in order), selection (choosing a path based on a true-or-false question) and repetition (repeating steps until a goal is reached). Changing the order of these pieces can change the result, which you can see by writing the steps out or drawing a flowchart.

Relational operators (==, !=, <, >, <=, >=) compare two values and produce a boolean. With primitives, == compares the actual values; with objects, it checks whether two references point to the same object.

An if statement runs its body only when its condition is true (one-way selection). Adding an else gives two-way selection: exactly one of the two blocks runs, depending on the condition.

A nested if sits inside another if, so its condition is checked only when the outer condition is true. An if-else-if chain is multiway selection: Java checks the conditions in order, runs only the first block whose condition is true, and runs the final else (if there is one) when none are.

The logical operators ! (not), && (and) and || (or) combine Boolean expressions, and they're applied in that order: ! first, then &&, then ||. Java uses short-circuit evaluation, so if the left side of && is false or the left side of || is true, the right side is never checked.

Two Boolean expressions are equivalent when no combination of values makes them disagree, and a truth table lets you check every case. De Morgan's laws say !(a && b) equals !a || !b and !(a || b) equals !a && !b. With objects, == and != check whether two variables are aliases of the same object (or null), while a class's equals method compares their contents.

A while loop checks its condition before every pass and keeps running its body as long as the condition is true. If the condition starts out false the body never runs, and if it can never become false you get an infinite loop. Looping one time too many or too few is called an off-by-one error.

A for loop header has three parts: the initialization runs once, the condition is checked before each pass, and the update runs after each pass of the body. The variable it sets up is the loop control variable, and any for loop can be rewritten as an equivalent while loop (and the other way around).

Some loop algorithms come up again and again: checking whether one number divides evenly into another (n % d == 0), pulling out the digits of an integer with % 10 and / 10, counting how often something happens, finding a minimum or maximum, and computing a sum or average. Learn these patterns so you can adapt them quickly on free-response questions.

String algorithms loop through a string's indexes and use substring to look at pieces of it. Standard examples are checking whether substrings have some property, counting the substrings that meet a condition, and building a reversed copy of a string.

Nested iteration means a loop inside another loop. For each single pass of the outer loop, the inner loop runs all of its passes before the outer loop moves on, which is why nested loops are used for patterns, grids and comparing every pair of items.

A statement execution count is how many times a statement runs, and you find it by tracing the loops. For example, a statement inside two nested loops that each run n times executes n * n times. Comparing these counts is an informal way to say which code segment does more work.