# UNIT 2: SELECTION AND ITERATION

# 1. INTRODUCTION

Imagine you are designing the software for a self-driving car. If the car only followed a single, linear set of instructions—"Drive forward for 10 miles, then stop"—it would be useless and dangerous. To navigate the real world, the software needs to make decisions: If a pedestrian is in the crosswalk, then apply the brakes. It also needs to perform repetitive tasks: While the battery level is above 5%, continue monitoring the GPS.

In computer science, these capabilities are known as Selection and Iteration. They are the fundamental structures that transform a simple calculator into a powerful, intelligent system. In Unit 1, we learned about variables and basic operations (Sequencing). In this unit, we introduce the "brain" of the program. We will explore how Boolean logic allows a program to branch into different paths and how loops allow a program to repeat complex calculations millions of times per second. By the end of this chapter, you will move from writing simple scripts to developing robust algorithms capable of solving complex mathematical and data-processing problems.

# 2. KEY CONCEPTS, TERMS, AND FOUNDATIONAL KNOWLEDGE

# Core Concepts

• Sequencing: The execution of statements in the order they appear in the code, one after another.
• Selection: The ability of a program to choose different paths of execution based on a condition (Boolean expression).
• Iteration (Repetition): The repeated execution of a block of code as long as a certain condition remains true.
• Algorithm: A step-by-step procedure or formula for solving a problem, built using sequencing, selection, and iteration.

# Boolean Logic and Operators

• Boolean Value: A data type that can only be either true or false.

• Relational Operators: Used to compare two values.

  Operator	Description	Example ($a=5, b=10$)	Result
  ==	Equal to	$a == b$	false
  !=	Not equal to	$a != b$	true
  <	Less than	$a < b$	true
  <=	Less than or equal to	$a <= b$	true
  >	Greater than	$a > b$	false
  >=	Greater than or equal to	$a >= b$	false

• Logical Operators: Used to combine multiple Boolean expressions.

  • && (AND): True if both operands are true.
  • || (OR): True if at least one operand is true.
  • ! (NOT): Reverses the Boolean value.

# Control Structures

• if Statement: A one-way selection structure.
• if-else Statement: A two-way selection structure.
• if-else-if ladder: A multi-way selection structure.
• while Loop: A condition-controlled loop that checks the condition before the body executes.
• for Loop: A count-controlled loop consisting of initialization, condition, and update.
• Nested Loop: A loop placed inside the body of another loop.

# 3. IN-DEPTH EXPLANATION

# 2.1 – Algorithms with Selection and Repetition

Every computer program, regardless of complexity, is built from three building blocks:

1. Sequencing: Standard linear flow.
2. Selection: Branching logic ($ \text{if-then} $).
3. Repetition: Loops.

The order and combination of these blocks define the algorithm. For example, to find the largest number in a list, you use sequencing to start at the beginning, repetition to look at every number, and selection to compare the current number with the largest one found so far.

# 2.2 – Boolean Expressions

A Boolean expression is any expression that evaluates to true or false.

• Primitive Comparison: When comparing int, double, or char, Java compares the actual values.
• Reference Comparison: When using == or != with Objects (like String), Java compares the memory addresses (references), not the content. Two Strings can both contain "Hello" but exist at different memory locations, making str1 == str2 evaluate to false.

# 2.3 – if Statements

The if statement is the most basic form of selection.

if (boolean_expression) {
    // executes if true
}

The if-else provides an alternative path:

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

Exactly one branch will execute in an if-else structure.

# 2.4 – Nested if Statements

Nesting allows for complex logic. A multi-way selection (else-if) ensures that only the first true condition is executed.
$$ \text{If } C_1 \text{ is true, execute } B_1. \text{ Else if } C_2 \text{ is true, execute } B_2. \dots \text{ Else execute } B_{default}. $$
Once a condition is met, the rest of the ladder is skipped.

# 2.5 – Compound Boolean Expressions

Logic operators follow a strict order of operations (Precedence):

1. Parentheses ()
2. Logical NOT !
3. Arithmetic (*, /, %, then +, -)
4. Relational (<, >, <=, >=)
5. Equality (==, !=)
6. Logical AND &&
7. Logical OR ||

Short-circuit evaluation:

• For A && B: If A is false, the result must be false, so B is never evaluated.
• For A || B: If A is true, the result must be true, so B is never evaluated.
• Application: if (list != null && list.size() > 0) prevents a NullPointerException.

# 2.6 – Comparing Boolean Expressions and De Morgan’s Laws

Two expressions are equivalent if they yield the same result for all possible inputs. We use Truth Tables to prove this.
De Morgan’s Laws:

1. !(A && B) is equivalent to !A || !B
2. !(A || B) is equivalent to !A && !B

To negate a complex expression, negate each individual term and flip the operator ($&& \leftrightarrow ||$, $< \leftrightarrow \ge$, $== \leftrightarrow !=$).

# 2.7 – while Loops

The while loop is used when the number of iterations is not known beforehand.

while (condition) {
    // loop body
}

If the condition is false initially, the body executes zero times. If the condition never becomes false, an infinite loop occurs.

# 2.8 – for Loops

The for loop is specialized for counting.

for (initialization; condition; update) {
    // body
}

1. Initialization: Runs once at the start.
2. Condition: Checked before every iteration (including the first).
3. Update: Runs after the body, before the next condition check.

Any for loop can be written as a while loop:

int i = 0; // Initialization
while (i < n) { // Condition
    // body
    i++; // Update
}

# 2.9 – Standard Algorithms

• Divisibility: n % d == 0 means $n$ is divisible by $d$.
• Digit Extraction:
  • To get the last digit: num % 10
  • To remove the last digit: num / 10
• Min/Max: Initialize max to a very small value or the first element, then update if a larger one is found.

# 2.10 – String Algorithms

Since Strings are immutable, we use substring() and length() to process them.

• Traversing a String:

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

• Counting: Use a counter variable inside the loop.
• Reversing: Build a new string by adding characters in reverse order.

# 2.11 – Nested Iteration

When a loop is inside another, the inner loop completes all its cycles for every one cycle of the outer loop.
Total executions of the inner-most statement = $(\text{Outer Iterations}) \times (\text{Inner Iterations})$.

# 2.12 – Informal Run-Time Analysis

In AP CSA, we count how many times a statement executes.

• A loop from $i=0$ to $i < N$ runs $N$ times.
• Nested loops where both run $N$ times result in $N^2$ executions.
• If a loop runs $N$ times and another runs $M$ times inside it, the count is $N \times M$.

# 4. EXAMPLES

# Example 1: Basic Selection (Level 10)

Determine if a student passed based on a grade.

int grade = 85;
if (grade >= 65) {
    System.out.println("Passed");
}

Logic: Since $85 \ge 65$ is true, "Passed" is printed.

# Example 2: Even or Odd (Level 15)

Using the modulo operator.

int num = 7;
if (num % 2 == 0) {
    System.out.println("Even");
} else {
    System.out.println("Odd");
}

Calculation: $7 \pmod 2 = 1$. $1 == 0$ is false. Output: "Odd".

# Example 3: Nested if (Level 20)

Checking eligibility for a discount.

int age = 70;
boolean isMember = false;
if (age > 65) {
    if (isMember) {
        System.out.println("50% discount");
    } else {
        System.out.println("25% discount");
    }
}

Logic: age > 65 is true. isMember is false. Output: "25% discount".

# Example 4: Compound Boolean logic (Level 25)

$A \text{ and } B$.

int temp = 25;
if (temp > 0 && temp < 100) {
    System.out.println("Liquid");
}

Logic: $25 > 0$ (true) AND $25 < 100$ (true). Result: true.

# Example 5: Short-circuit Evaluation (Level 30)

int x = 0;
if (x != 0 && 10 / x > 1) {
    System.out.println("Success");
}

Logic: x != 0 is false. Because of &&, the second part 10/x is never evaluated, avoiding a DivisionByZeroException.

# Example 6: Short-circuit OR (Level 30)

int y = 10;
if (y > 5 || 10 / 0 == 1) {
    System.out.println("True");
}

Logic: y > 5 is true. Because of ||, the second part (which would crash) is skipped. Output: "True".

# Example 7: De Morgan's Law Transformation (Level 35)

Simplify !(x < 5 && y >= 10).
Step 1: Negate x < 5 $\rightarrow$ x >= 5.
Step 2: Negate y >= 10 $\rightarrow$ y < 10.
Step 3: Flip && to ||.
Result: (x >= 5 || y < 10).

# Example 8: Comparing Strings (Level 40)

String s1 = new String("AP");
String s2 = new String("AP");
System.out.println(s1 == s2);      // false
System.out.println(s1.equals(s2)); // true

Note: == checks if they are the same object in memory. .equals() checks the characters.

# Example 9: basic while loop (Level 45)

Summing integers until 5.

int sum = 0;
int i = 1;
while (i <= 4) {
    sum += i;
    i++;
}

Trace:

1. $i=1, sum=1$
2. $i=2, sum=3$
3. $i=3, sum=6$
4. $i=4, sum=10$
5. $i=5$, loop terminates. Result: $10$.

# Example 10: Infinite Loop Danger (Level 45)

int i = 10;
while (i > 0) {
    System.out.println(i);
    // i++ is missing or written as i++, leading to i always being > 0
}

# Example 11: for loop mechanics (Level 50)

for (int i = 5; i > 0; i--) {
    System.out.print(i + " ");
}

Output: 5 4 3 2 1.

# Example 12: Summing with a for loop (Level 50)

Calculate $\sum_{i=1}^{10} i$.

int sum = 0;
for (int i = 1; i <= 10; i++) {
    sum += i;
}

Calculation: $\frac{n(n+1)}{2} = \frac{10(11)}{2} = 55$.

# Example 13: Extracting digits (Level 55)

Reverse the digits of 123.

int n = 123;
int rev = 0;
while (n > 0) {
    int d = n % 10;
    rev = rev * 10 + d;
    n = n / 10;
}

Trace:

1. d=3, rev=3, n=12
2. d=2, rev=32, n=1
3. d=1, rev=321, n=0

# Example 14: Counting occurrences in a number (Level 55)

How many times does '7' appear in 7172?

int n = 7172;
int count = 0;
while (n > 0) {
    if (n % 10 == 7) count++;
    n /= 10;
}

Result: count = 2.

# Example 15: String Traversal (Level 60)

Count 'a's in "banana".

String s = "banana";
int count = 0;
for (int i = 0; i < s.length(); i++) {
    if (s.substring(i, i + 1).equals("a")) {
        count++;
    }
}

Result: 3.

# Example 16: Finding a Maximum (Level 65)

Given a set of inputs (e.g., from a sensor).

int max = Integer.MIN_VALUE;
// Assume we have a loop reading values
if (currentVal > max) {
    max = currentVal;
}

# Example 17: Finding an Average (Level 65)

int sum = 0;
int count = 0;
for (int i = 1; i <= 5; i++) {
    sum += i;
    count++;
}
double avg = (double) sum / count;

Note: Must cast to double to avoid integer division: $15 / 5 = 3.0$.

# Example 18: String Reversal (Level 70)

String original = "Java";
String reversed = "";
for (int i = 0; i < original.length(); i++) {
    reversed = original.substring(i, i+1) + reversed;
}

Trace:

1. J + "" = "J"
2. a + "J" = "aJ"
3. v + "aJ" = "vaJ"
4. a + "vaJ" = "avaJ"

# Example 19: Nested Loop - Rectangle Pattern (Level 75)

for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++) {
        System.out.print("*");
    }
    System.out.println();
}

Output:

***
***

Analysis: Outer runs 2 times, Inner runs 3 times. Total stars = $2 \times 3 = 6$.

# Example 20: Nested Loop - Triangle Pattern (Level 80)

for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= i; j++) {
        System.out.print(j);
    }
    System.out.println();
}

Execution count: $1 + 2 + 3 + 4 = 10$ times.
Output:

1
12
123
1234

# Example 21: Checking for a Substring (Level 80)

How many times does "th" appear in "the thistle"?

String s = "the thistle";
int count = 0;
for (int i = 0; i <= s.length() - 2; i++) {
    if (s.substring(i, i + 2).equals("th")) {
        count++;
    }
}

Logic: Loop goes to length - 2 to prevent StringIndexOutOfBoundsException.

# Example 22: Divisibility Algorithm (Level 85)

Find all factors of 12.

int n = 12;
for (int i = 1; i <= n; i++) {
    if (n % i == 0) System.out.print(i + " ");
}

Output: 1 2 3 4 6 12 .

# Example 23: Sentinel Value Loop (Level 85)

int input = 0; 
int sum = 0;
// Hypothetical loop reading user input
while (input != -1) { // -1 is the sentinel
    sum += input;
    input = // read next value
}

# Example 24: Comparing Boolean logic with Truth Tables (Level 90)

Prove (A && B) is NOT the same as (A || B).

| A | B | A && B | A || B |
|---|---|--------|--------|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | F |
Since rows 2 and 3 differ, they are not equivalent.

# Example 25: Complex Nested Logic - Prime Check (Basic) (Level 90)

int n = 7;
boolean isPrime = true;
for (int i = 2; i < n; i++) {
    if (n % i == 0) isPrime = false;
}

Logic: If any number between 2 and $n-1$ divides $n$, it is not prime.

# Example 26: Informal Runtime - Nested (Level 92)

int count = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        count++;
    }
}

Total count = $N \times M$.

# Example 27: Informal Runtime - Triple Nested (Level 95)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // statement
        }
    }
}

Total executions = $n \times n \times n = n^3$.

# Example 28: Off-by-one Error (Level 95)

String s = "Java";
for (int i = 0; i <= s.length(); i++) {
    System.out.println(s.substring(i, i+1));
}

Error: When i = s.length(), i+1 is out of bounds. The condition should be i < s.length().

# Example 29: String processing - Removing Vowels (Level 97)

String s = "education";
String result = "";
for (int i = 0; i < s.length(); i++) {
    String c = s.substring(i, i + 1);
    if (!(c.equals("a") || c.equals("e") || c.equals("i") || c.equals("o") || c.equals("u"))) {
        result += c;
    }
}

Result: "dctn".

# Example 30: Multi-way selection logic (Level 98)

int x = 15;
if (x > 10) {
    System.out.print("A");
} else if (x > 5) {
    System.out.print("B");
} else {
    System.out.print("C");
}

Logic: Even though $15 > 5$ is true, only "A" prints because it was the first true condition.

# Example 31: De Morgan's on inequalities (Level 100)

Negate: (age >= 18 && hasID == true).
Result: !(age >= 18) || !(hasID == true) $\rightarrow$ (age < 18 || hasID == false).

# Example 32: Nested Loops with dependent boundaries (Level 100)

int count = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        count++;
    }
}

Analysis: This follows the arithmetic series $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

# Example 33: Loop with double update (Level 100)

for (int i = 0; i < 10; i += 2) {
    System.out.print(i + " ");
}

Output: 0 2 4 6 8 . (Skips every other number).

# Example 34: Reference null check (Level 100)

String str = null;
if (str != null && str.length() > 0) {
    System.out.println("Valid String");
}

Logic: The first condition is false, so str.length() is not called, preventing a crash.

# Example 35: Character Search Algorithm (Level 100)

Find the index of the first 'x' in a string, or -1 if not found.

String s = "pixel";
int index = -1;
for (int i = 0; i < s.length(); i++) {
    if (s.substring(i, i+1).equals("x")) {
        index = i;
        break; // In AP CSA, we usually use a boolean or check index == -1
    }
}

Logic: This demonstrates searching and early termination concepts.