Algorithms with Selection and Repetition - AP Computer Science A

SECTION 1

Historical Context & Motivation

Every program of practical significance must make decisions and repeat actions. Before electronic computers existed, mathematicians formalized the notion of an algorithm — a finite sequence of well-defined steps that transforms inputs into outputs. The two indispensable building blocks identified in that formalization were selection (choosing among alternatives) and repetition (executing steps multiple times). Without these constructs, programs could only perform a fixed, linear series of instructions, making them essentially useless for real-world problems.

1843 • Ada Lovelace's Algorithm

Ada Lovelace published the first recognized algorithm for Charles Babbage's Analytical Engine, employing both conditional branching and iterative loops to compute Bernoulli numbers.

1936 • Turing Machines

Alan Turing introduced the Turing machine model, which relies on state transitions (selection) and the ability to repeat operations indefinitely — proving that these two mechanisms are computationally universal.

1966 • Structured Programming Theorem

Böhm and Jacopini proved that any computable function can be expressed with just three control structures: sequence, selection, and iteration — eliminating the need for goto statements.

1995 • Java Released

Sun Microsystems released Java, providing if/else for selection and for/while for iteration. These constructs became the foundation of AP Computer Science A curricula worldwide.

The central question this lesson addresses is: how do we combine selection and iteration in Java to write algorithms that solve non-trivial problems — searching for values, accumulating results, filtering data, and processing strings? Understanding these patterns is essential because the AP Computer Science A exam tests your ability to trace, write, and analyze code that weaves together conditionals and loops.

SECTION 2

Core Principles & Definitions

Selection and iteration are the two non-sequential control structures in Java. Selection lets a program branch its execution path based on a Boolean condition, while iteration lets a program repeat a block of code until a condition changes. When combined, they enable algorithms of arbitrary complexity. The following foundational concepts underpin every algorithm you will encounter on the AP exam.

Selection (if / else if / else)

Evaluates a Boolean expression and executes one of several branches. Java's if, else if, and else keywords implement single-selection, double-selection, and multi-way selection.

Iteration (for / while)

Repeats a body of code. A for loop is ideal when the number of iterations is known; a while loop is preferred when termination depends on a runtime condition.

Boolean Expressions

The glue connecting selection and iteration. Compound conditions use && (AND), || (OR), and ! (NOT) with short-circuit evaluation.

Algorithmic Patterns

Common patterns include accumulation (summing/counting), searching (linear search), finding min/max, and filtering. Each pattern combines a loop with an internal conditional.

Tracing & Correctness

Hand-tracing through iterations — tracking variable values in a table — is the primary technique for verifying correctness and predicting output, a skill tested on every AP exam.

SECTION 3

Visual Explanation — Control Flow

The outer diamond (i < n) is the loop condition. Each iteration enters the inner diamond (arr[i] > max), which is a selection inside the loop — the classic find-maximum pattern.

The diagram illustrates the most common algorithmic pattern on the AP exam: a selection nested inside iteration. The outer loop iterates through array indices, and on each pass the inner conditional determines whether the current element should update the tracked maximum. Notice that the false branch of the inner diamond simply skips the update and proceeds to i++. This structure generalizes: replace the inner condition with any predicate and replace the update with any action, and you have searching, counting, filtering, or accumulating.

SECTION 4

How Selection & Iteration Work in Java

Selection Constructs

Java provides three selection patterns. A single if statement executes its body only when the condition is true. An if-else guarantees exactly one of two blocks runs. A chained if / else if / else sequence tests conditions top-to-bottom and executes the first matching branch; subsequent conditions are skipped entirely. A subtle but exam-critical point is that Java uses short-circuit evaluation: in A && B, B is never evaluated if A is false, and in A || B, B is never evaluated if A is true.

Iteration Constructs

The for loop bundles initialization, condition, and update into one line: for (init; condition; update). The condition is checked before each iteration, so the body may execute zero times. The while loop expresses the same logic but separates the three components, making it the better choice when the number of iterations cannot be predetermined. Java's enhanced for-each loop (for (Type x : collection)) simplifies traversal but does not expose the index. All three loop forms appear on the AP exam.

Nesting Selection Inside Iteration

Algorithms become powerful when an if statement sits inside a loop body. On each iteration, the conditional selects whether to perform an action on the current element. This composite structure is the backbone of four fundamental patterns the AP exam tests: accumulate (sum or count matching elements), search (find an element satisfying a condition), min/max (track the extreme value), and filter/transform (build a new result based on a predicate).

ℹ

Common Pitfall: Off-by-One Errors

SECTION 5

Algorithmic Pattern Catalog

The AP Computer Science A exam repeatedly tests a small set of canonical algorithmic patterns. Each pattern combines iteration with selection in a specific way. Recognizing these patterns quickly is the key to both MCQ speed and FRQ accuracy. The diagram below categorizes the four main patterns and shows the essential code skeleton for each.

Each panel shows a minimal code skeleton and its purpose. The green-highlighted line in each pattern is the action performed when the selection condition is true.

A few important notes apply across all four patterns. First, every pattern has O(n) time complexity because each element is visited exactly once. Second, the min/max pattern must initialize the tracking variable to an actual element (typically arr[0]), not to zero or Integer.MAX_VALUE — the AP exam frequently exploits this misunderstanding. Third, for the search pattern, returning inside the loop provides an early exit, which is more efficient than searching the entire array when a match exists.

SECTION 6

Worked Example — Counting Even Digits

Consider the following method that counts how many even digits appear in a non-negative integer. This example demonstrates a while loop (since the number of digits is not known at compile time) with an if selection inside.

ℹ

Code

Worked example

1
Step 1 — Initialization

Set n = 3842 and count = 0. The while condition 3842 > 0 is true, so we enter the loop.
2
Step 2 — Iteration 1 (digit = 2)

digit = 3842 % 10 = 2. Since 2 % 2 == 0 is true, count increments to 1. Then n = 3842 / 10 = 384.

count = 1, n = 384
3
Step 3 — Iteration 2 (digit = 4)

digit = 384 % 10 = 4. Since 4 % 2 == 0 is true, count increments to 2. Then n = 384 / 10 = 38.

count = 2, n = 38
4
Step 4 — Iteration 3 (digit = 8)

digit = 38 % 10 = 8. Since 8 % 2 == 0 is true, count increments to 3. Then n = 38 / 10 = 3.

count = 3, n = 3
5
Step 5 — Iteration 4 (digit = 3)

digit = 3 % 10 = 3. Since 3 % 2 == 0 is false, count stays at 3. Then n = 3 / 10 = 0.

count = 3, n = 0
6
Step 6 — Loop terminates

The condition 0 > 0 is false, so the loop exits. The method returns 3. Indeed, the integer 3842 contains three even digits (2, 4, 8).

return 3 ✓

★

Key takeaway

TRACING TIP

SECTION 7

Comparing Loop Constructs

Java offers three loop constructs that are appropriate for the AP subset. Each has strengths and constraints, and choosing the right one can make your code both cleaner and less error-prone. The table below summarizes when to prefer each form.

Feature	for loop	while loop	for-each loop
Best when	Number of iterations is known or index-driven	Termination depends on a dynamic condition	Every element must be visited; no index needed
Access to index?	Yes	Yes (if you manage it)	No
Off-by-one risk	Moderate — < vs. <=	Higher — manual updates	None — automatic
Can modify collection?	Yes (with index)	Yes (with index)	No — ConcurrentModificationException
AP exam frequency	Very high	High	Moderate

Comparison of Java loop constructs relevant to the AP exam

SECTION 8

Connection to Advanced Topics

The selection-inside-iteration pattern studied in this lesson is the foundation on which more advanced algorithms are built. Once you are comfortable nesting a single conditional inside a single loop, you are ready for nested loops (iteration within iteration) and recursive decomposition (where the loop is replaced by a method calling itself). The table below maps the patterns from this lesson to their more advanced counterparts.

This Lesson	Advanced Extension	Where Tested
Linear search (single loop)	Binary search (selection with halving)	AP CSA Unit 7 / FRQ
Find max (single loop + if)	Selection sort (nested loop + swap)	AP CSA Unit 7
Accumulate pattern	Merge sort merge step	AP CSA Unit 7
String traversal with charAt()	Recursive string processing	AP CSA Unit 10 / FRQ
Filter (single array)	2D array traversal (nested for loops)	AP CSA Unit 8 / FRQ

From basic patterns to advanced algorithms

A critical skill as you advance is recognizing that nested loops change the time complexity from O(n) to O(n²). Binary search, in contrast, achieves O(log n) by leveraging selection to halve the search space on every iteration — a dramatic improvement that stems from the same if-else construct you already know. The transition from Unit 4 (this lesson's material) to Units 7–10 is essentially the transition from flat composition (one loop, one if) to deep composition (nested loops, recursive calls), all using the same building blocks.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Consider the following code segment.

int x = 5;
while (x > 0) {
  if (x % 2 == 1)
    System.out.print(x + " ");
  x--;
}

What is printed as a result of executing this code? A. 5 3 1 B. 5 4 3 2 1 C. 4 2 D. 1 3 5

A. 5 3 1
B. 5 4 3 2 1
C. 4 2
D. 1 3 5

Show answer (A)

Correct answer: A. The loop runs with x = 5, 4, 3, 2, 1. The if-condition x % 2 == 1 is true when x is odd (5, 3, 1), so those values are printed in descending order: 5 3 1. Option B would print all values (no selection). Option C prints even values instead of odd ones — that would require x % 2 == 0. Option D has the correct values but in ascending order; since x starts at 5 and decrements, the output is descending.

Question 2: BASIC CALCULATION

Consider the following code segment.

int[] arr = {3, 7, 2, 8, 5};
int sum = 0;
for (int i = 0; i < arr.length; i++) {
  if (arr[i] > 4)
    sum += arr[i];
}
System.out.println(sum);

What is printed? A. 25 B. 20 C. 15 D. 5

A. 25
B. 20
C. 15
D. 5

Show answer (B)

Correct answer: B. The loop iterates over all five elements. The condition arr[i] > 4 is true for 7, 8, and 5 (three elements). Their sum is 7 + 8 + 5 = 20. Option A (25) is the sum of all elements, ignoring the conditional. Option C (15) might result from incorrectly using >= 5 and miscounting. Option D (5) is just the last qualifying element, as if only the final match were kept.

Question 3: INTERMEDIATE

Consider the following code segment.

String s = "aAbBcC";
String result = "";
for (int i = 0; i < s.length(); i++) {
  if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
    result += s.charAt(i);
  else
    result += "*";
}
System.out.println(result);

What is printed? A. a*b*c* B. abc C. *A*B*C D. a*B*c*

A. a*b*c*
B. abc
C. *A*B*C
D. a*B*c*

Show answer (A)

Correct answer: A. The loop processes each character: 'a' is lowercase → appended; 'A' is uppercase → replaced with '*'; 'b' → appended; 'B' → '*'; 'c' → appended; 'C' → '*'. Result: a*b*c*. Option B keeps only lowercase letters but ignores the else branch. Option C reverses the condition logic. Option D incorrectly treats 'B' as lowercase.

Question 4: APPLIED

Write a method public static int longestRun(int[] arr) that returns the length of the longest consecutive run of equal values in arr. For example, if arr = {1, 1, 2, 2, 2, 3, 3}, the method returns 3 (the run of 2s). You may assume arr.length >= 1.

Show answer

Sample solution:

public static int longestRun(int[] arr) {
  int maxRun = 1;        // 1 pt
  int currentRun = 1;    // 1 pt
  for (int i = 1; i < arr.length; i++) {  // 1 pt
    if (arr[i] == arr[i - 1]) {           // 1 pt
      currentRun++;
    } else {
      currentRun = 1;
    }
    if (currentRun > maxRun) {            // 1 pt
      maxRun = currentRun;
    }
  }
  return maxRun;                          // 1 pt
}

Rubric: • (1 pt) Initializes maxRun and currentRun appropriately (both to 1). • (1 pt) Correctly iterates starting from index 1 to arr.length − 1. • (1 pt) Compares adjacent elements using arr[i] == arr[i − 1]. • (1 pt) Increments currentRun when equal, resets to 1 when not. • (1 pt) Updates maxRun when currentRun exceeds it. • (1 pt) Returns the correct value. No array out-of-bounds errors.

Question 5: CRITICAL THINKING

Write a method public static boolean isPalindrome(String s) that returns true if s reads the same forwards and backwards (case-sensitive). Your solution must use a loop with selection. Explain why your loop only needs to iterate through half the string.

Show answer

Sample solution:

public static boolean isPalindrome(String s) {
  for (int i = 0; i < s.length() / 2; i++) {
    if (s.charAt(i) != s.charAt(s.length() - 1 - i))
      return false;
  }
  return true;
}

Rubric: • (1 pt) Loop iterates from 0 to s.length() / 2 (exclusive) — correctly covers half the string. • (1 pt) Compares s.charAt(i) with s.charAt(s.length() − 1 − i) to mirror-check characters. • (1 pt) Returns false immediately upon finding a mismatch (early exit). • (1 pt) Returns true after the loop completes without finding a mismatch. Explanation: Checking half the string suffices because each comparison checks two characters symmetrically (position i and position length − 1 − i). By the time i reaches the midpoint, every character pair has been compared. This halving reduces comparisons by 50%, and the early return provides further efficiency when a mismatch exists near the beginning.