Implementing Selection and Iteration Algorithms - AP Computer Science A

SECTION 1

Historical Context & Motivation

Before high-level programming languages existed, early computer scientists had to wire hardware or punch machine-code instructions to make a computer branch or loop. The fundamental insight that programs could be composed entirely from sequence, selection, and iteration transformed software engineering from ad-hoc craft into a disciplined practice. These three control structures remain the backbone of every algorithm you will encounter on the AP Computer Science A exam and in professional development.

1843 • Ada Lovelace's Notes

Ada Lovelace described the first algorithm for Charles Babbage's Analytical Engine, which included a loop to compute Bernoulli numbers — the earliest documented use of iteration in a program.

1946 • Von Neumann Architecture

John von Neumann's stored-program concept introduced conditional branching at the hardware level, enabling selection logic through jump instructions based on register values.

1966 • Structured Programming Theorem

Böhm and Jacopini proved that any computable function can be expressed using only sequence, selection (if-then-else), and iteration (while loops), eliminating the need for unstructured goto statements.

1995 • Java Released

Sun Microsystems released Java with if, else, for, while, and do-while constructs baked into the language specification — the same constructs tested on the AP CS A exam today.

The core question that selection and iteration answer is simple yet profound: how does a program respond differently to different data and repeat work until a condition is met? Without these capabilities, every program would execute the same fixed sequence of statements regardless of input — useful for almost nothing.

SECTION 2

Core Principles & Definitions

Selection and iteration are built on a small vocabulary of Java keywords and Boolean expressions. Understanding the precise semantics of each construct — when the condition is evaluated, which block executes, and how flow resumes — is essential for writing correct algorithms and tracing code on the AP exam.

Selection (if / else if / else)

Evaluates a Boolean expression and executes one of several code blocks. Only the first true branch in an if / else-if chain runs; the rest are skipped.

Iteration (for / while)

Repeats a block of code as long as a Boolean condition remains true. A for loop packages initialization, condition, and update in one header; a while loop tests only a condition.

Boolean Expressions

The guards that drive both selection and iteration. Composed of relational operators (<, >, <=, >=, ==, !=) and logical operators (&&, ||, !). Short-circuit evaluation applies.

Nested Structures

Selection and iteration can be nested to arbitrary depth. A loop may contain an if statement (filtering), and an if statement may contain a loop (conditional repetition).

Standard Algorithms

The AP CS A curriculum expects fluency with common patterns: finding a min/max, computing a sum/average, searching for a value, and determining if all or some elements satisfy a condition.

SECTION 3

Visual Explanation — Control Flow

On the left, selection evaluates a condition once and branches; control merges afterward. On the right, iteration evaluates a condition repeatedly, executing the loop body each time it is true and looping back to re-check the condition.

The diagram above captures the fundamental difference between selection and iteration. In selection, the diamond (decision node) is visited exactly once: flow splits, one branch executes, and both paths merge into a single continuation. In iteration, the decision node is visited repeatedly — every time the loop body completes, an arrow feeds back to the condition. The loop terminates only when the condition evaluates to false. Recognizing this feedback arrow is critical: if the loop body never changes a variable used in the condition, you get an infinite loop.

SECTION 4

How It Works — Syntax & Semantics

Selection Constructs

Java provides three levels of selection. A standalone if executes its body when the condition is true and does nothing otherwise. Adding else creates two mutually exclusive paths. Chaining else if clauses allows multi-way branching where only the first true condition's block runs. A common exam pitfall is using separate if statements instead of else if when the conditions are mutually exclusive — this causes multiple blocks to execute when only one was intended.

IF / ELSE IF / ELSE TEMPLATE

if (condA) { blockA } else if (condB) { blockB } else { blockC }

condA and condB are Boolean expressions. If condA is true, only blockA runs. If condA is false and condB is true, only blockB runs. If neither is true, blockC runs.

Iteration Constructs

The while loop checks its condition before each iteration; if the condition is initially false, the body never executes. The for loop compresses initialization, condition, and update into a single header, making it ideal for counted iteration. On the AP exam, do-while is not tested, but understanding that it checks the condition after the body runs helps solidify the concept. Every for loop can be rewritten as a while loop and vice versa — the choice is one of clarity, not capability.

FOR LOOP TEMPLATE

for (int i = start; i < end; i++) { body }

Executes body exactly (end − start) times when start < end. The variable i takes values start, start + 1, …, end − 1.

EQUIVALENT WHILE LOOP

int i = start; while (i < end) { body; i++; }

Identical behavior: initialization before the loop, condition checked each iteration, update at the end of the body.

ℹ

Off-By-One Errors

SECTION 5

Standard Algorithms — The Exam Essentials

The College Board specifies a set of standard algorithms that combine selection and iteration in predictable patterns. Mastering these patterns lets you recognize them quickly in MCQs and produce them reliably in FRQs. The table below catalogs each algorithm, its typical structure, and a key implementation detail.

Algorithm	Pattern	Key Detail
Find Minimum / Maximum	Initialize to first element; iterate and compare with `if`	Initialize to arr[0], not Integer.MAX_VALUE, to handle negative arrays safely.
Compute Sum / Average	Accumulator variable updated inside a loop	Use `double` for average to avoid integer division.
Linear Search	Loop with an `if` that returns index on match	Return −1 after the loop to signal "not found".
Check All / Check Any	Boolean flag + loop; for "all", start true and set false on failure	For "any", start false and set true on success. Return early when possible.
Count Occurrences	Counter variable incremented inside a conditional	Use `.equals()` for Strings, `==` for primitives.

Standard selection-and-iteration algorithms tested on AP CS A

The trace table shows each iteration of the find-maximum algorithm. The variable max is initialized to arr[0] = 3, then updated each time a larger element is found. The amber-highlighted element (9) is the final maximum.

SECTION 6

Worked Example — Counting Even Numbers

Write a method countEvens that accepts an array of integers and returns the number of even values. This combines iteration (traversing the array) with selection (testing each element).

Worked example

1
Step 1 — Declare the method and accumulator

We need a method that takes an int[] parameter and returns an int. Declare a counter variable initialized to 0.

public static int countEvens(int[] arr) { int count = 0;
2
Step 2 — Iterate through the array

Use a for loop from index 0 to arr.length - 1. This guarantees every element is visited exactly once.

for (int i = 0; i < arr.length; i++)
3
Step 3 — Apply the selection condition

Inside the loop, check whether arr[i] % 2 == 0. The modulus operator returns the remainder of division by 2. If the remainder is 0, the number is even. Increment count when the condition is true.

if (arr[i] % 2 == 0) { count++; }
4
Step 4 — Return the result

After the loop completes, count holds the total number of even elements. Return it.

return count; }
5
Step 5 — Trace with sample input

For arr = {3, 8, 5, 12, 7}: i=0 → 3%2≠0, i=1 → 8%2==0 (count=1), i=2 → 5%2≠0, i=3 → 12%2==0 (count=2), i=4 → 7%2≠0. The method returns 2.

countEvens({3, 8, 5, 12, 7}) → 2

SECTION 7

for vs. while — When to Use Which

Since for and while loops are interchangeable in power, the choice is about readability and intent. The table below summarizes the conventional guidelines.

Criterion	for loop	while loop
Number of iterations	Known in advance (e.g., array length)	Unknown; depends on runtime condition
Loop variable scope	Declared in header; scoped to the loop	Declared before loop; persists after
Typical use case	Array traversal, counting	Sentinel-controlled input, searching until found
Risk of infinite loop	Lower — update is in the header	Higher — developer must remember to update
AP Exam frequency	Very common in array/String traversal MCQs	Common in FRQs involving user input or search

★

Key takeaway

CHOOSE WISELY

SECTION 8

Connection to Advanced Topics

Selection and iteration are the building blocks for nearly every advanced algorithm in computer science. The techniques you learn here scale directly into topics such as nested loops for 2D arrays, recursion (which replaces explicit iteration with self-referential method calls), and sorting algorithms that combine both selection and iteration in sophisticated ways.

This Lesson	Advanced Extension
Single for loop traversing an array	Nested for loops traversing a 2D array (row-major order)
Linear search with early return	Binary search requiring a sorted array and logarithmic time
Find max using a single pass	Selection sort: repeatedly find min of unsorted subarray
while loop with a condition variable	Recursion: the "condition" becomes the base case, the "loop back" becomes the recursive call

On the AP exam, FRQ questions frequently ask you to write methods that involve iterating through an ArrayList while conditionally removing or modifying elements. This is a direct application of combining iteration with selection, and it introduces the subtlety that removing an element during forward traversal can skip the next element. Traversing backward or adjusting the index after removal solves this — a detail the exam loves to test.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Consider the following code segment:

int x = 10;
if (x > 5)
  x -= 3;
if (x > 5)
  x -= 3;
System.out.println(x);

What is printed? A) 10 B) 7 C) 4 D) 3

A. 10
B. 7
C. 4
D. 3

Show answer (C)

The correct answer is C) 4. Initially x = 10. The first if checks 10 > 5 (true), so x becomes 7. The second if (not else-if) independently checks 7 > 5 (true), so x becomes 4. This illustrates that two separate if statements both execute when both conditions are true — unlike an if / else-if chain where only the first true branch runs. A is wrong because both conditions are true, so x is modified. B is wrong because it only accounts for the first if. D is wrong because subtracting 3 twice from 10 gives 4, not 3.

Question 2: BASIC CALCULATION

What is the output of the following code?

int sum = 0;
for (int i = 1; i <= 5; i++)
{
  if (i % 2 != 0)
    sum += i;
}
System.out.println(sum);

A) 6 B) 9 C) 15 D) 10

A. 6
B. 9
C. 15
D. 10

Show answer (B)

The correct answer is B) 9. The loop runs for i = 1, 2, 3, 4, 5. The condition i % 2 != 0 selects odd numbers: 1, 3, 5. Their sum is 1 + 3 + 5 = 9. A (6) is wrong — it might result from summing even numbers 2 + 4. C (15) is wrong — that is the sum of all integers 1 through 5 without the filter. D (10) is wrong — it does not correspond to any correct subset sum.

Question 3: INTERMEDIATE

Consider the following method:

public static String mystery(String str)
{
  String result = "";
  for (int i = 0; i < str.length(); i++)
  {
    if (str.substring(i, i + 1).equals("a"))
      result += "@";
    else
      result += str.substring(i, i + 1);
  }
  return result;
}

What does mystery("banana") return? A) "b@n@n@" B) "b@nana" C) "ban@n@" D) "@@@@@@"

A. "b@n@n@"
B. "b@nana"
C. "ban@n@"
D. "@@@@@@"

Show answer (A)

The correct answer is A) "b@n@n@". The method iterates through each character of the string. When the character equals "a", it appends "@"; otherwise, it appends the original character. "banana" has 'a' at indices 1, 3, and 5, which are all replaced with '@'. B is wrong because it only replaces the first 'a'. C is wrong because it skips the 'a' at index 1. D is wrong because non-'a' characters are preserved, not replaced.

Question 4: APPLIED

Write the method public static int indexOfMax(int[] arr) that returns the index of the maximum value in arr. If there are duplicate maximum values, return the index of the first occurrence. You may assume arr has at least one element.

Show answer

Sample solution:

public static int indexOfMax(int[] arr)
{
  int maxIdx = 0;
  for (int i = 1; i < arr.length; i++)
  {
    if (arr[i] > arr[maxIdx])
      maxIdx = i;
  }
  return maxIdx;
}

Rubric: • (1 pt) Initialize maxIdx to 0 (or equivalent valid initialization). • (1 pt) Correct loop bounds starting at 1 through arr.length − 1. • (1 pt) Correct comparison using > (not >=) to return first occurrence. • (1 pt) Return maxIdx after the loop completes.

Question 5: CRITICAL THINKING

Write the method public static boolean isStrictlyIncreasing(int[] arr) that returns true if every element is strictly greater than the one before it, and false otherwise. An array with 0 or 1 elements is considered strictly increasing.

Show answer

Sample solution:

public static boolean isStrictlyIncreasing(int[] arr)
{
  for (int i = 1; i < arr.length; i++)
  {
    if (arr[i] <= arr[i - 1])
      return false;
  }
  return true;
}

Rubric: • (1 pt) Loop starts at index 1 and compares arr[i] with arr[i − 1]. • (1 pt) Uses <= (not just <) to correctly detect equal adjacent elements as non-increasing. • (1 pt) Returns false immediately upon finding a violation (early exit pattern), and returns true after the loop if no violation is found.