Unit 2 Algorithms and Analysis: Building, Using, and Reasoning About Code

Implementing Selection and Iteration Algorithms

An algorithm is a step-by-step procedure for solving a problem. In AP Computer Science A, you spend a lot of time taking an idea (“count how many scores are passing”) and turning it into precise Java code that always works—even for edge cases. Unit 2 focuses on the two core tools that make algorithms powerful:

  • Selection: choosing between paths (using if, if-else, and else if).
  • Iteration: repeating a process (using while and for).

These are the building blocks for nearly every non-trivial program you’ll write.

Selection: making decisions with if / else

Selection means your program executes different code depending on a condition. The condition must be a boolean expression—something that evaluates to true or false.

Why it matters: Without selection, programs are “straight lines.” Real problems involve rules: apply a discount only if a customer qualifies, stop when you hit invalid input, update a max only when you find something larger.

How it works:

  • Java evaluates the condition in parentheses.
  • If it’s true, the block executes.
  • Otherwise, Java skips that block (and may execute an else block).

Key idea: selection often appears inside loops to filter or update running results.

int score = 82;
if (score >= 90) {
    System.out.println("A");
} else if (score >= 80) {
    System.out.println("B");
} else {
    System.out.println("C or below");
}

What can go wrong:

  • Using == to compare objects like String (use .equals instead—covered later).
  • Overlapping or misordered conditions (e.g., checking score >= 80 before score >= 90 would make the >= 90 branch unreachable).

Iteration: repeating work with loops

Iteration repeats a block of code while a condition remains true (or for a fixed number of times). Loops matter because most algorithms aren’t “do once”—they process many items: characters in a String, numbers in a range, attempts until valid input, etc.

There are two main loop forms in AP CSA:

LoopBest forWhat controls repetition?
whileUnknown number of repetitionsA boolean condition checked before each iteration
forKnown number of repetitions (counting)Initialization, condition, update (usually counter-based)
while loops: repeat until something changes

A while loop is ideal when you don’t know in advance how many times you’ll loop—often because the loop ends when you hit a “sentinel” condition.

How it works step by step:

  1. Check the loop condition.
  2. If it’s true, run the body once.
  3. Go back to step 1.

This means if the condition is initially false, the body runs zero times.

Example: find the first position of a target character in a String.

public static int indexOfChar(String s, char target) {
    int i = 0;
    while (i < s.length() && s.charAt(i) != target) {
        i++;
    }

    if (i < s.length()) {
        return i;
    }
    return -1;
}

Why this pattern is common:

  • The loop has two stopping reasons: you ran out of characters (i < length fails), or you found the target (charAt(i) != target fails).

What can go wrong:

  • Forgetting i++ (infinite loop).
  • Checking s.charAt(i) before confirming i < s.length() (causes StringIndexOutOfBoundsException). Java evaluates && left to right and stops early, so putting the bounds check first is crucial.
for loops: count-controlled repetition

A for loop is best when you know you want to iterate over a numeric range or every index in a string.

Structure:

  • Initialize a counter.
  • Continue while condition is true.
  • Update the counter after each iteration.

Example: sum numbers from 1 to n.

public static int sumToN(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

What can go wrong:

  • Off-by-one errors (i < n vs i <= n). The difference is whether n itself is included.
  • Accidentally modifying the loop counter inside the body in a way that breaks the intended progression.

Common loop algorithm patterns

Most AP CSA loop questions are variations on a few patterns. Learning to recognize them helps you design correct algorithms quickly.

1) Counting occurrences

You keep a counter and increment when a condition is met.

public static int countEvens(int start, int end) {
    int count = 0;
    for (int x = start; x <= end; x++) {
        if (x % 2 == 0) {
            count++;
        }
    }
    return count;
}

Why it matters: counting is the foundation of frequency tables, validations (“at least 2 digits”), and many string problems.

Common mistake: incrementing the counter in the wrong place (e.g., outside the if) so you count everything.

2) Accumulation (sum/product/building a result)

You maintain a running total (or other combined result).

public static int sumMultiplesOf3(int n) {
    int sum = 0;
    for (int x = 1; x <= n; x++) {
        if (x % 3 == 0) {
            sum += x;
        }
    }
    return sum;
}

Key idea: initialize correctly (0 for sum, 1 for product, "" for string building in simple cases).

3) Finding a maximum/minimum

You track the “best so far” and update it conditionally.

public static int maxInRange(int start, int end) {
    int max = start; // careful: initialize to a real value in the range
    for (int x = start; x <= end; x++) {
        if (x > max) {
            max = x;
        }
    }
    return max;
}

Why initialization matters: setting max = 0 would be wrong if your range could be negative.

4) Early termination

Sometimes you can stop as soon as you know the answer.

Example: check whether a number has a factor (not prime). This uses early exit to avoid extra work.

public static boolean hasFactor(int n) {
    if (n < 2) return false;

    for (int d = 2; d < n; d++) {
        if (n % d == 0) {
            return true;
        }
    }
    return false;
}

Even if you’re not doing formal efficiency proofs, AP CSA expects you to notice that returning early changes how many loop iterations happen.

5) Nested loops

A nested loop is a loop inside another loop. This often represents “for each item, do a full scan of something else.”

Example: generate all ordered pairs (i, j).

public static void printPairs(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            System.out.println(i + "," + j);
        }
    }
}

Why it matters: nested loops are common in pattern printing, comparing all pairs, and 2D grid reasoning. They also dramatically increase how many total iterations happen.

What can go wrong:

  • Mixing up which counter changes where.
  • Misunderstanding total iteration count: the inner loop runs fully for each outer-loop iteration.
Exam Focus
  • Typical question patterns:
    • “Write a method that uses a loop to count/accumulate/filter values meeting a condition.”
    • “Determine the output of a loop with if statements and updates to variables.”
    • “Identify the number of times a loop executes given its bounds and updates.”
  • Common mistakes:
    • Off-by-one bounds (especially with < vs <= and starting at 0 vs 1).
    • Infinite loops from missing/incorrect updates (counter doesn’t move toward termination).
    • Placing bounds checks after indexing (e.g., charAt(i) before confirming i < length).

Developing Algorithms Using Strings

A String in Java represents a sequence of characters. Many “Algorithms and Analysis” tasks in Unit 2 involve iterating through strings to analyze or transform them, because strings are a clean way to practice loops, indexing, and conditional logic.

Why strings are tricky: a string feels like a single value (“Hello”), but algorithmically it’s a collection of characters with positions (indices). Most errors come from misunderstanding indices, length, or equality.

Essential String tools (and what they really do)

You’ll repeatedly use a small set of methods.

  • length() returns the number of characters.
  • charAt(int index) returns the character at a given index.
  • substring(int start, int end) returns a new string from start (inclusive) to end (exclusive).
  • substring(int start) returns from start to the end.
  • equals(String other) compares string contents for equality.
  • compareTo(String other) compares lexicographically (dictionary order), returning a negative/zero/positive integer.

Important index facts:

  • The first character is at index 0.
  • The last character is at index length() - 1.
  • Valid indices are 0 through length() - 1. Anything else causes StringIndexOutOfBoundsException.

Iterating through a string by index

The standard pattern is a for loop from 0 to length() - 1.

public static void printChars(String s) {
    for (int i = 0; i < s.length(); i++) {
        System.out.println(i + ": " + s.charAt(i));
    }
}

Why this pattern matters: It gives you direct control over positions, which you need for tasks like counting, searching, comparing neighbors, or extracting substrings.

What can go wrong:

  • Using i <= s.length() instead of i < s.length()—that tries to access charAt(length()), which is out of bounds.

Algorithm idea: counting features in a string

A very common task is: “Count how many characters match a rule.” The rule might be “is a vowel,” “is uppercase,” “is a digit,” or “equals some target character.”

Example: count vowels (case-insensitive). Notice how selection (if) is embedded inside iteration.

public static int countVowels(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = Character.toLowerCase(s.charAt(i));
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            count++;
        }
    }
    return count;
}

Why this is a strong model solution:

  • It cleanly separates “get the character” from “test the character.”
  • It avoids duplicated logic by normalizing case once.

Common mistakes:

  • Trying to compare a char to a String (use single quotes for char, double quotes for String).
  • Forgetting that || combines conditions; using && by mistake would make the condition impossible.

Algorithm idea: searching in a string

Searching means finding whether something exists, or where it occurs.

Find the first occurrence of a character

You’ve seen a version earlier with a while loop. A for loop version is also common.

public static int firstIndexOf(String s, char target) {
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == target) {
            return i; // early termination
        }
    }
    return -1;
}

Why returning early matters: The moment you find the answer, continuing the loop would only waste work and complicate reasoning.

Count occurrences of a substring (non-overlapping vs overlapping)

Substring counting is trickier because you must decide whether overlaps count.

For example, in "aaaa", the substring "aa" occurs:

  • Overlapping: positions 0-1, 1-2, 2-3 (3 occurrences)
  • Non-overlapping: positions 0-1, 2-3 (2 occurrences)

AP-style questions often specify behavior; if not, your code should clearly implement one approach.

Overlapping count:

public static int countSubstringOverlapping(String s, String sub) {
    if (sub.length() == 0) return 0; // avoid infinite counting idea

    int count = 0;
    for (int i = 0; i <= s.length() - sub.length(); i++) {
        if (s.substring(i, i + sub.length()).equals(sub)) {
            count++;
        }
    }
    return count;
}

Key reasoning:

  • The last starting index you can use is s.length() - sub.length().
  • That’s why the loop condition is i <= ....

Common mistakes:

  • Looping to i < s.length() and then using substring(i, i + sub.length())—this will go out of bounds near the end.
  • Using == to compare the substring with sub instead of .equals.

Algorithm idea: building a new string (transformation)

Sometimes you need to produce a modified version of a string: remove spaces, replace characters, reverse it, etc.

Important concept: Strings are immutable in Java, meaning you cannot change a character “in place.” Any transformation creates a new string.

A simple approach is to build a result string by concatenation.

public static String removeSpaces(String s) {
    String result = "";
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c != ' ') {
            result += c;
        }
    }
    return result;
}

This is fine for AP CSA-style problems. In professional Java, repeated concatenation in a loop is often replaced by StringBuilder for performance, but AP CSA frequently keeps things at the level of String operations unless otherwise stated.

Common mistakes:

  • Forgetting to assign back (result + c; does nothing; you need result += c;).
  • Confusing character and string literals.

Worked algorithm: palindrome check

A palindrome reads the same forward and backward (e.g., "racecar"). This problem is a great illustration of careful indexing and stopping conditions.

How it works:

  • Compare the first and last characters.
  • Then the second and second-to-last, etc.
  • Stop when you’ve compared the whole string (you only need to go halfway).
public static boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Why left < right is the right condition:

  • When left == right, you’re at the middle character of an odd-length string—no need to compare it with itself.

What can go wrong:

  • Using left <= right still works here, but it does an unnecessary comparison when they meet.
  • Forgetting to move both pointers leads to an infinite loop.

String comparisons: equals vs ==, and compareTo

This is one of the highest-impact correctness issues.

  • Use equals to compare the contents of strings.
  • == checks whether two variables refer to the same object in memory, which is not what you usually mean.
String a = new String("hi");
String b = new String("hi");
System.out.println(a == b);      // likely false
System.out.println(a.equals(b)); // true

compareTo is used for ordering:

  • s1.compareTo(s2) < 0 means s1 comes before s2 lexicographically.
  • == 0 means equal strings.
  • > 0 means after.

This is useful for tasks like “find the alphabetically smallest word” using a running minimum pattern.

Exam Focus
  • Typical question patterns:
    • “Write a method that traverses a string to count characters matching a rule.”
    • “Find/return the index of the first/last occurrence of a character or substring.”
    • “Construct and return a transformed string (remove/replace/reverse).”
  • Common mistakes:
    • Off-by-one substring bounds (forgetting the end index is exclusive, or looping too far).
    • Using == instead of .equals for string equality.
    • Out-of-bounds indexing by using i <= s.length() or failing to guard charAt/substring near the end.

Informal Code Analysis

Informal code analysis means reasoning about what code does without necessarily running it. On AP CSA, this usually looks like:

  • Tracing variable values through loops and conditionals.
  • Determining printed output or returned values.
  • Counting how many times a statement executes.
  • Comparing which of two approaches does “more work” in a general sense.

Why it matters: Writing code is only half the job. You also need to predict behavior, debug logic errors, and justify that an algorithm is correct. Informal analysis builds the habit of thinking like the computer—very literally, step by step.

Tracing: executing code in your head (systematically)

When tracing, your goal is to track how variables change over time. The most reliable method is to create a small table with:

  • loop counter(s)
  • key variables (sum, count, min/max, current character, etc.)
  • the condition outcome (whether the loop continues)
Example 1: trace a counting/accumulation loop

Consider:

public static int mystery(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            total += i;
        } else {
            total -= i;
        }
    }
    return total;
}

How to analyze it:

  • The loop runs from i = 1 to i = n.
  • Odd i are subtracted, even i are added.

If n = 5, the sequence of updates is:

  • i=1 odd: total = 0 - 1 = -1
  • i=2 even: total = -1 + 2 = 1
  • i=3 odd: total = 1 - 3 = -2
  • i=4 even: total = -2 + 4 = 2
  • i=5 odd: total = 2 - 5 = -3

Return value: -3.

What students often miss: they treat the if as if both branches somehow matter each time. In reality, exactly one branch runs per iteration.

Loop bounds and “how many times does it run?”

A frequent informal analysis task is to count iterations.

Example 2: simple counting loop
int count = 0;
for (int i = 0; i < 10; i += 2) {
    count++;
}

Analyze it by listing i values: 0, 2, 4, 6, 8. That’s 5 iterations, so count ends as 5.

Common mistake: assuming “less than 10” means 10 iterations automatically. The update step (i += 2) changes everything.

Example 3: nested loop iteration counting
int ops = 0;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
        ops++;
    }
}

Outer loop runs 3 times. Inner loop runs 4 times per outer iteration. Total increments: 3 * 4 = 12.

This kind of reasoning is often enough for AP CSA: you don’t need advanced proofs, but you must correctly multiply nested loop counts.

Reasoning about correctness: invariants (informal but powerful)

An invariant is something that remains true at key points in your program (often at the start or end of each loop iteration). You may not be asked to use the term “loop invariant,” but thinking this way makes analysis and debugging much easier.

Example: for a loop that counts vowels seen so far, an invariant could be:

  • “After processing indices 0 through i-1, count equals the number of vowels in that prefix.”

Why this matters: If you can state what a variable means, you can check whether updates preserve that meaning.

A common student issue is treating variables as “magic numbers” instead of meaningful quantities. When you give the variable a meaning, mistakes like incrementing in the wrong branch become obvious.

Informal efficiency comparisons (doing “more work” vs “less work”)

AP CSA sometimes expects you to compare which code segment is more efficient in a general sense—especially with nested loops and early termination.

Key ideas you can use without heavy math:

  • A single loop over n items does work proportional to n.
  • A nested loop where both loops scale with n does work proportional to “n times n,” meaning it grows much faster.
  • Early termination can reduce work for many inputs (best case), but you should still consider the possibility it runs to completion (worst case).
Example 4: early return vs full scan

Compare:

// Version A
public static boolean containsX(String s) {
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == 'x') return true;
    }
    return false;
}

// Version B
public static boolean containsX2(String s) {
    boolean found = false;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == 'x') found = true;
    }
    return found;
}

Both are correct. Informally:

  • Version A may stop early (if 'x' appears near the front).
  • Version B always scans the entire string.

A subtle but important analysis point: in the worst case (no 'x'), both scan the full string. But Version A can be faster for many typical inputs.

Analyzing common bug patterns via tracing

Informal analysis isn’t only about answering “what prints?” It’s also how you catch mistakes.

Bug pattern 1: off-by-one in loops
for (int i = 0; i <= s.length(); i++) {
    System.out.println(s.charAt(i));
}

A trace immediately shows the failure point: when i == s.length(), charAt(i) crashes. The fix is i < s.length().

Bug pattern 2: wrong boolean logic in conditions
if (c != 'a' || c != 'e') {
    // intended: if not a vowel
}

This condition is always true, because any character is always “not equal to at least one of these.” Informal analysis here means testing with a concrete character:

  • If c is 'a', then c != 'e' is true, so the overall || is true.
  • If c is 'e', then c != 'a' is true.

Correct logic for “not (a or e)” is &&:

if (c != 'a' && c != 'e') {
    // not a and not e
}

Or, more generally for vowels, you often write the positive case (is a vowel) with || and then negate it.

Reading code questions: focus on the order of evaluation

Java evaluation order matters most in:

  • short-circuit boolean expressions (&&, ||)
  • chained if-else if structures

Example with short-circuiting:

if (i < s.length() && s.charAt(i) == 'A') {
    // safe
}

If i is out of bounds, the left side is false, and Java does not evaluate charAt(i). Reversing the condition would be unsafe.

Exam Focus
  • Typical question patterns:
    • “What is the output / return value after this loop runs?” (often with a counter, accumulator, or string traversal)
    • “How many times does this statement execute?” (including nested loops)
    • “Which code segment is more efficient or stops earlier, and why?” (early termination vs full scan)
  • Common mistakes:
    • Losing track of variable updates inside a loop (especially when updates happen conditionally).
    • Miscounting iterations because of nonstandard updates (i += 2, decrementing loops, nested loops).
    • Ignoring evaluation order in &&/|| and if-else if chains, leading to wrong traces or missed exceptions.