Advanced Control Structures: Selection, Iteration, and Analysis

Implementing Selection and Iteration Algorithms

In AP Computer Science A, the ability to combine Selection (making decisions) and Iteration (repeating tasks) is fundamental to solving complex problems. An algorithm is a precise sequence of instructions implemented using programming languages (like Java) to solve a specific task.

Standard Algorithm Patterns

There are several standard algorithms you must memorize and understand conceptually. These often appear in Free Response Questions (FRQs) involving methods.

1. Divisibility and Modulo

To determine if a number is even, odd, or a multiple of another number, use the modulus operator (%). It returns the remainder of division.

• Even Check: if (num % 2 == 0)
• Odd Check: if (num % 2 != 0)
• Multiple Check: if (num % k == 0) (Is $num$ a multiple of $k$?)

2. Determining Min/Max Values

To find the minimum or maximum value in a sequence of inputs (or elements), you need initialized variables and a loop structure.

• Initialization: Never initialize to 0 if the data might be negative (for max) or large (for min).
  • Initialize max to Integer.MIN_VALUE or the first value in the set.
  • Initialize min to Integer.MAX_VALUE or the first value in the set.

int currentMax = Integer.MIN_VALUE;
// Assume 'input' is a value received inside a loop
if (input > currentMax) {
    currentMax = input;
}

3. Digit Extraction

A classic algorithm involves analyzing integers digit-by-digit. This requires a while loop that continues as long as the number is greater than 0.

• Get the last digit: int digit = number % 10;
• Remove the last digit: number = number / 10;

Accumulation Logic

Algorithms frequently require running totals (sums) or counts.

• Counter: A variable incremented by 1 (e.g., count++) when a condition is met.
• Accumulator: A variable increased by a value from the dataset (e.g., total += currentValue).

Example: Sum of Even Digits

public int sumEvenDigits(int num) {
    int sum = 0;
    while (num > 0) {
        int digit = num % 10;
        if (digit % 2 == 0) {
            sum += digit;
        }
        num /= 10;
    }
    return sum;
}

Developing Algorithms Using Strings

Strings in Java are objects. Developing algorithms for strings usually involves iterating through the characters to analyze or construct new strings. Since strings are immutable, you cannot change them in place; you must build a new string using concatenation.

String Traversal

You iterate through a string using its index, which ranges from $0$ to $length() - 1$.

The Standard for Loop Structure

String str = "Computer";
for (int i = 0; i < str.length(); i++) {
    String letter = str.substring(i, i + 1);
    // Process 'letter'
}

Accessing Characters

While charAt(int index) exists, the AP exam frequently tests utilizing substring for single-character analysis.

• Syntax: str.substring(index, index + 1) returns the single character at index as a String.
• Boundary: Be careful! Accessing str.substring(n, n+1) where n is str.length() leads to a StringIndexOutOfBoundsException.

Common String Algorithms

1. Counting Occurrences: finding how many times loop logic detects a specific character (e.g., vowels).
2. Reversing a String: iterating backwards or prepending characters.
3. Finding Nested Substrings: checking if a smaller string exists inside a larger one.

Example: Reversing a String

public String reverseString(String original) {
    String reversed = ""; // Initialize empty string
    for (int i = 0; i < original.length(); i++) {
        String singleChar = original.substring(i, i + 1);
        reversed = singleChar + reversed; // Prepend character
    }
    return reversed;
}

Informal Code Analysis

Informal code analysis (or "hand tracing") is the process of manually stepping through code to determine the output or the state of variables. This is a critical skill for attempting Multiple Choice Questions (MCQs).

Trace Tables

A Trace Table is a grid used to track the changing values of variables during iteration.

How to construct a Trace Table:

1. Create columns for every variable (including the loop counter $i$).
2. Create a column for the logical condition (True/False).
3. Create a column for Output.
4. Add a new row for every iteration of the loop.

Analyzing Nested Loops

When analyzing nested loops, remember that the inner loop completes a full cycle for every single iteration of the outer loop.

• If the outer loop runs $N$ times and the inner loop runs $M$ times, the body execution count is $N \times M$.
• Triangle Loops: Watch for inner loops dependent on the outer loop variable (e.g., for(int k=0; k < i; k++)). These usually print triangle patterns or process lower/upper portions of 2D data (covered later in arrays).

Predicting Output

When asked "What is printed?":

• Does the printing happen inside or outside the loop?
• Is it System.out.print (same line) or System.out.println (new line)?
• Watch for loop boundaries—does the loop stop at < n or <= n? This determines if the last value is processed (a common "off-by-one" error source).

Common Mistakes & Pitfalls

• String Comparison Error: Never use == to compare strings. == checks if two references point to the same memory object. Always use str1.equals(str2) to check if the text content is the same.
• Off-By-One Errors: Misinterpreting loop boundaries. Using <= length on a specific index (like accessing an array or string) causes an Index Out of Bounds exception. The last valid index is always $length - 1$.
• Integer Division: Remember that int / int results in an int (truncation). 5 / 2 equals 2, not 2.5. This often breaks average calculations if you don't cast to double.
• Infinite Loops: In while loops, failing to update the control variable inside the loop body results in an infinite loop which crashes the program.
• Substring Blindness: For substring(start, end), remember the start index is inclusive strings, but the end index is exclusive (the character at end is NOT included).