Implementing Selection and Iteration Algorithms - AP Computer Science A Study Guide

Getting Started

Complex programming tasks are rarely solved with a single command. Instead, they are solved by creating an algorithm, a step-by-step process for achieving a goal. In Java, we build these algorithms by combining fundamental control structures: selection (making choices) and iteration (repeating actions). This topic focuses on how to strategically combine loops and conditional statements to process data and solve common programming problems.

What You Should Be Able to Do

• Implement algorithms that use if and if-else statements to control the flow of execution.

• Implement algorithms that use for and while loops for repetition.

• Combine iteration and selection to create algorithms that process all elements of a data set, such as the characters in a String.

• Develop algorithms that use methods from the Math class for numerical computations.

• Trace the execution of an algorithm to understand its behavior and predict its output.

Key Concepts & Java Implementation

The Core Idea

An algorithm is a finite sequence of well-defined, computer-implementable instructions to solve a class of problems or to perform a computation. In programming, we don't just write code; we design algorithms. The two most essential tools for building algorithms are:

1. Selection: This refers to a program's ability to make a choice and execute different blocks of code based on a condition. In Java, this is primarily done using if, else if, and else statements. This allows your program to react differently to different inputs or states.

2. Iteration: This refers to repeating a block of code. Repetition is crucial for processing collections of data, such as every character in a String or checking multiple possible values in a mathematical problem. In Java, we use for and while loops for iteration.

By combining these two structures, we can create powerful algorithms. A common pattern is to use a loop to iterate over a set of data and an if statement inside the loop to make a decision about each individual piece of data.

Syntax & Implementation

Let's examine how to combine these structures to solve two common problems: processing text and analyzing numbers.

Annotated Java Example 1: Processing a String

A frequent task is to iterate through a String and analyze its characters. The following algorithm counts the number of times a specific character appears in a given string.

public class StringProcessor {

    /**

     * Counts the occurrences of a target character within a source string.

     * @param source The string to search through.

     * @param target The character to count.

     * @return The total number of times the target character appears.

     */

    public int countOccurrences(String source, char target) {

        int count = 0; // 1. Initialize a counter to zero.


        // 2. Create a 'for' loop to visit every character in the string.

        //    The loop runs from the first index (0) up to (but not including) the string's length.

        for (int i = 0; i < source.length(); i++) {

            

            // 3. Get the character at the current index 'i'.

            char currentChar = source.charAt(i);


            // 4. Use an 'if' statement (selection) to check if the current character

            //    matches our target character.

            if (currentChar == target) {

                // 5. If it matches, increment the counter.

                count++;

            }

        }

        // 6. After the loop finishes, return the final count.

        return count;

    }

}

Annotated Java Example 2: A Numeric Algorithm

Algorithms are also essential for mathematical problems. The following method determines if a number is "prime" by iterating through potential divisors and using a selection statement to check for divisibility.

public class MathAlgorithms {

    /**

     * Determines if a given integer is a prime number.

     * A prime number is a number greater than 1 that has no positive divisors

     * other than 1 and itself.

     * @param n The integer to check.

     * @return true if n is prime, false otherwise.

     */

    public boolean isPrime(int n) {

        // 1. By definition, numbers less than or equal to 1 are not prime.

        //    This 'if' is a selection that handles edge cases.

        if (n <= 1) {

            return false;

        }


        // 2. Iterate from 2 up to the square root of n. We only need to check

        //    this far because if n has a factor larger than its square root,

        //    it must also have a factor smaller than it.

        //    Here we use a method from the 'Math' class.

        for (int i = 2; i <= Math.sqrt(n); i++) {

            

            // 3. The modulo operator (%) gives the remainder of a division.

            //    If the remainder is 0, 'n' is evenly divisible by 'i'.

            if (n % i == 0) {

                // 4. If we find a divisor, we know it's not prime, so we can

                //    immediately return false and exit the method.

                return false;

            }

        }


        // 5. If the loop completes without finding any divisors, the number is prime.

        return true;

    }

}

Tracing & Analysis

Execution Trace

Let's trace the execution of countOccurrences("banana", 'a').

The loop terminates when i becomes 6. The method then returns the final value of count, which is 3.

Analysis

In the isPrime algorithm, the use of Math.sqrt(n) is a key optimization. A less efficient version might loop all the way to n / 2 or n - 1. While that would still produce the correct result, it would perform many more iterations for large values of n. Choosing the right loop bounds and conditions is a critical part of designing efficient algorithms.

Java Syntax Quick-Reference

The following Java syntax elements are the building blocks for the algorithms in this topic.

Core Code Examples & Terminology

• Algorithm: A finite, step-by-step set of instructions designed to perform a specific task or solve a problem.

• Selection: A control structure, such as an if statement, that directs a program to execute different code blocks based on a boolean condition.

• Iteration: A control structure, such as a for or while loop, that causes a block of code to be executed repeatedly.

• Math class: A standard Java class that contains static methods for performing common mathematical operations.

• Core Snippet 1 (Iterating through a String):

  
  for (int i = 0; i < myString.length(); i++) {
  
      char c = myString.charAt(i);
  
      // Process character c...
  
  }
  

  This for loop is the standard way to access every character in a String by its index.

• Core Snippet 2 (Find First Match with while):

  
  int i = 0;
  
  boolean found = false;
  
  while (i < someArray.length && !found) {
  
      if (someArray[i] == targetValue) {
  
          found = true;
  
      }
  
      i++;
  
  }
  

  This while loop searches for a value and stops as soon as the value is found.

• Core Snippet 3 (Generating a Random Integer in a Range):

  
  // Generates a random integer from min to max (inclusive)
  
  int randomNum = (int)(Math.random() * (max - min + 1)) + min;
  

  This formula uses Math.random() to produce a random integer within a specified range.

Core Skill Check

• Code Tracing: What is the final value of sum after this Java code runs: int sum = 0; for (int k = 1; k <= 5; k++) { if (k % 2 == 0) { sum += k; } }?

  Answer: 6 (2 + 4)

• Debugging: Identify the runtime error in this Java code: String word = "test"; for (int i = 0; i <= word.length(); i++) { System.out.println(word.charAt(i)); }.

  Answer: A StringIndexOutOfBoundsException will occur. The loop condition should be i < word.length() because the last valid index is word.length() - 1.

• Application: Write a single line of Java code that declares a boolean variable isTeenager and initializes it to true if an int variable age is between 13 and 19 (inclusive), and false otherwise.

  Answer: boolean isTeenager = age >= 13 && age <= 19;

Common Misconceptions & Errors

• Off-By-One Errors: A common mistake in loops is using <= instead of < with .length() or an array's length. The valid indices for a string of length L are 0 to L-1, so the condition i < L is almost always correct.

• Incorrect Loop Condition in while loops: Forgetting to update the variable that controls the while loop's condition can lead to an infinite loop, causing the program to hang.

• Improper Use of Math.random(): The Math.random() method returns a double between 0.0 and 1.0 (exclusive of 1.0). You must multiply, cast to int, and add an offset to get a random integer within a specific range.

• Integer Division: When performing division with two integers, the result is an integer (the fractional part is truncated). For example, 7 / 2 evaluates to 3, not 3.5. This can lead to unexpected results in numerical algorithms if not handled carefully.

Summary

This topic covers the practical application of selection and iteration, the core building blocks of algorithms. By nesting if statements inside for or while loops, you can create code that intelligently processes collections of data, such as the characters in a String. These combined structures allow you to search for values, count occurrences, and validate data. Furthermore, the static methods in the Math class provide essential tools for implementing numerical algorithms. Mastering the ability to combine these fundamental control structures is the key to solving a vast range of programming problems.