Algorithms with Selection and Repetition - AP Computer Science A Study Guide

Getting Started

Nearly every useful computer program needs to do two things: make decisions and repeat actions. To solve a problem, such as finding the largest number in a list, we need a step-by-step plan, or an algorithm. This chapter introduces the fundamental Java control structures that allow us to implement these algorithms by directing the flow of our program's execution through selection (making choices) and repetition (performing loops).

What You Should Be Able to Do

• Write conditional statements using if, else if, and else to execute different code blocks based on a condition.

• Implement for loops to repeat a task a specific number of times.

• Implement while loops to repeat a task as long as a condition remains true.

• Combine selection and repetition structures to solve multi-step problems.

• Trace the execution of code containing loops and conditional statements to predict output.

Key Concepts & Java Implementation

The Core Idea

An algorithm is a finite, step-by-step procedure for solving a problem. To translate an algorithm into code, we need to control the order in which statements are executed. Java provides two primary types of control structures for this purpose: selection and repetition.

Selection structures allow a program to follow different paths based on whether a given condition is true or false. The primary tool for selection in Java is the if-else statement. It evaluates a boolean expression—an expression that results in either true or false—to decide which block of code to run.

Repetition structures (also called loops or iterations) allow a program to execute the same block of code multiple times. This is essential for tasks like processing every item in a dataset or repeating a process until a goal is met. Java's main repetition tools are the for loop, typically used when the number of repetitions is known, and the while loop, used when the repetitions depend on a condition that can change during execution.

Syntax & Implementation

Selection with if, else if, and else

These statements control which code is executed based on one or more boolean conditions.

Syntax Table

Annotated Java Example

This code determines if an integer is positive, negative, or zero.

public class NumberChecker {

    public void checkNumber(int num) {

        // The first condition checked.

        if (num > 0) {

            System.out.println("The number is positive.");

        } 

        // If the first condition (num > 0) was false, this one is checked.

        else if (num < 0) {

            System.out.println("The number is negative.");

        } 

        // If both of the above conditions were false, this block runs.

        else {

            System.out.println("The number is zero.");

        }

    }

}

Repetition with for and while Loops

Loops execute a block of code repeatedly.

The for Loop

A for loop is ideal when you know exactly how many times you want to repeat an action. It combines initialization, a condition, and an update step into one line.

Syntax Table

Annotated Java Example

This for loop prints the numbers from 1 to 5.

public class Counter {

    public void countUp() {

        // 1. Initialize: int i = 1

        // 2. Condition: is i <= 5? (true) -> run loop body

        // 3. Update: i++

        // Repeat step 2 and 3 until the condition is false.

        for (int i = 1; i <= 5; i++) {

            System.out.println(i);

        }

    }

}

The while Loop

A while loop is used when a loop should continue as long as a condition is true, but the number of iterations is not known in advance.

Annotated Java Example

This while loop simulates rolling a die until a 6 is rolled.

public class DiceRoller {

    public void rollUntilSix() {

        int roll = 0; // Initialize roll to a value that allows the loop to start.


        // The loop continues as long as roll is not 6.

        while (roll != 6) {

            // Math.random() returns a double from 0.0 up to (but not including) 1.0

            roll = (int) (Math.random() * 6) + 1; // Simulate a roll from 1-6

            System.out.println("You rolled a: " + roll);

        }


        System.out.println("You got a 6! You win!");

    }

}

Tracing & Analysis

Execution Trace

Let's trace an algorithm that finds the sum of all even numbers from 1 to 8.

Code:

int sum = 0;

for (int i = 1; i <= 8; i++) {

    if (i % 2 == 0) { // Check if i is even

        sum = sum + i;

    }

}

// What is the final value of sum?

Trace Table:

The final value of sum is 20.

Analysis

Choosing the right loop is a key skill.

• Use a for loop when the number of iterations is fixed or can be easily calculated beforehand (e.g., iterating n times, processing every character in a String).

• Use a while loop when the number of iterations is unknown and depends on a runtime condition (e.g., processing user input until they type "quit", waiting for a sensor reading to exceed a threshold).

Java Syntax Quick-Reference

• if (boolean_expression): Executes the following code block if the expression evaluates to true.

• else if (boolean_expression): Provides a secondary condition to test if the preceding if or else if was false.

• else: Executes a code block if all preceding if and else if conditions in the chain were false.

• for (initialization; condition; update): A repetition structure that groups the three parts of a count-controlled loop.

• while (boolean_expression): A repetition structure that executes a code block as long as its condition remains true.

• ==: Equality operator. Returns true if two values are equal.

• !=: Inequality operator. Returns true if two values are not equal.

• >, <, >=, <=: Relational operators used to compare numeric values.

• %: Modulo operator. Returns the remainder of a division (e.g., 10 % 3 is 1).

Core Code Examples & Terminology

• Algorithm: A finite, unambiguous set of instructions used to perform a computation or solve a problem.

• Selection: A control structure that allows a program to choose between different paths of execution based on a boolean condition.

• Repetition: A control structure that allows a program to execute a block of code multiple times. Also known as iteration or looping.

• Boolean Expression: An expression in Java that evaluates to a boolean value, either true or false.

• Core Snippet 1 (If-Else If-Else Structure):

  
  if (grade >= 90) {
  
      letter = "A";
  
  } else if (grade >= 80) {
  
      letter = "B";
  
  } else {
  
      letter = "C";
  
  }
  

  This structure efficiently assigns a value based on a series of mutually exclusive conditions.

• Core Snippet 2 (Standard for Loop):

  
  for (int i = 0; i < 10; i++) {
  
      System.out.println("Count is: " + i);
  
  }
  

  This loop iterates exactly 10 times, with the counter i taking on values from 0 to 9.

• Core Snippet 3 (Condition-Controlled while Loop):

  
  int x = 100;
  
  while (x > 1) {
  
      x = x / 2;
  
  }
  

  This loop continues to execute as long as the value of x is greater than 1.

Core Skill Check

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

• Debugging: Identify the logical error in this Java code intended to print numbers 1 through 10: int i = 1; while (i < 10) { System.out.println(i); }.

• Application: Write a single line of Java code that begins a for loop to print all odd numbers between 1 and 99 (inclusive).

Common Misconceptions & Errors

1. Using = instead of == for Comparison: The single equals sign (=) is for assignment, not comparison. A condition like if (x = 5) will cause a compile-time error because it doesn't produce a boolean value. Always use the double equals sign (==) for checking equality.

2. Off-by-One Errors in Loops: Carefully check your loop's boundary conditions. Using < versus <= can mean the difference between a correct loop and one that runs one too many or one too few times. For example, for (int i = 0; i < 10; i++) runs 10 times (for i = 0 through 9), while for (int i = 0; i <= 10; i++) runs 11 times.

3. Infinite while Loops: A while loop's condition must eventually become false. If you forget to include code inside the loop that changes the variable(s) in the condition, the loop will run forever.

4. Misplaced Semicolons: Placing a semicolon directly after an if condition or a loop declaration, like if (x > 10);, terminates the statement. The following code block {...} will then execute unconditionally, which is almost never the intended behavior.

Summary

Algorithms are the logical recipes for solving computational problems. In Java, we implement these recipes using control structures. Selection statements, primarily if, else if, and else, allow our programs to make decisions and execute different code based on boolean conditions. Repetition statements, or loops, like for and while, allow us to execute code multiple times. The for loop is best suited for a known number of iterations, while the while loop is ideal for situations where the looping depends on a dynamic condition. Combining these structures is the fundamental skill required to build complex and useful software.