AP Computer Science A: Lesson 4.5

Implementing Array Algorithms

Unit 4: Data Collections

This notebook serves as a complete lesson plan, presentation guide, live coding scratchpad, and homework lab for Topic 4.5.

1. Reference Guide

Key Topics

Term Definition Example / Context
Accumulator A variable declared before a loop used to build up a result, such as a sum or count. int sum = 0; before looping to add arr[i] to sum.
Min / Max Algorithm An algorithm that assumes the first element is the extreme value, then updates if a more extreme value is found. int max = arr[0]; rather than starting at 0 to handle negative values.
Flag Variable A boolean variable used to record whether a certain condition was met during the traversal. boolean hasZero = false; updated to true if arr[i] == 0 is found.
Shifting Elements Moving all elements in an array one index left or right, often requiring a temporary variable. Moving arr[i+1] to arr[i] inside a loop.
  • Contextual Rule: Standard array algorithms are the building blocks of most data processing tasks. Always initialize search variables correctly before the loop, and return the final result after the loop finishes executing.

2. LxD Cycle Process

Empathize

Students often struggle with standard algorithms by initializing minimum variables to 0, which breaks when an array only contains negative numbers. They also frequently return inside the loop prematurely before fully traversing the array.

Define

  • POV: CSA students need to visualize array traversal algorithms as a step-by-step physical process so they stop relying on memorization and understand the logic of tracking "current best" or "running totals."
  • Learning Goal: Students will implement standard algorithms to find a minimum/maximum, compute a sum/average, and count elements matching specific criteria.

Ideate

  • HMW Question: How might we get students to realize the importance of initializing a max variable to arr[0] instead of 0?
  • HMW Question: How might we help students separate the logic of finding an item from the logic of returning the result?
  • Activity: Unplugged sorting/searching activity using a deck of playing cards to manually track "current max" before writing the Java code.

Prototype

  • A reference guide of standard algorithms, an unplugged card activity, a pair-programming tracing worksheet, and a Free Response Question (FRQ) practice prompt.
  • Students physically trace algorithms before coding them in an IDE.

Test

  • Review student tracing tables for common off-by-one errors.
  • Analyze execution results in unit tests to see if students handle edge cases (e.g., negative numbers for max algorithms).

3. College Board Requirements

  • AP CSA Unit 4, Topic 4.5: Standard Array Algorithms.
  • There are standard algorithms that utilize array traversals to: determine a minimum or maximum value, compute a sum, count elements, and determine if at least one element meets criteria.
  • There are standard algorithms for shifting or rotating elements left or right.

4. Lesson Plan

Learning Objective: Implement standard array algorithms to process collections of data, including finding extreme values, summing, and counting.

Success Criteria: You can write a loop to traverse an array and correctly apply accumulator, flag, and min/max logic to process the data without throwing an ArrayIndexOutOfBoundsException.

Presentation & Slide Deck

  • Slide 1: Welcome & Warm-Up
    • Title: Standard Array Algorithms: The Toolkit
    • Warm-Up Prompt: "If I ask you to find the tallest student in this room, what are the exact steps your brain takes to figure it out?"
    • Teacher Script: "Your brain automatically scans the room, picks a starting person, and then compares everyone else to that first person. If someone is taller, they become the new 'tallest'. Today, we are going to teach Java how to do exactly what your brain just did."

    • 2. LxD Cycle Process

    Empathize

    Students often struggle with standard algorithms by initializing minimum variables to 0, which breaks when an array only contains negative numbers. They also frequently return inside the loop prematurely before fully traversing the array.

    Define

    • POV: CSA students need to visualize array traversal algorithms as a step-by-step physical process so they stop relying on memorization and understand the logic of tracking "current best" or "running totals."
    • Learning Goal: Students will implement standard algorithms to find a minimum/maximum, compute a sum/average, and count elements matching specific criteria.

    Ideate

    • HMW Question: How might we get students to realize the importance of initializing a max variable to arr[0] instead of 0?
    • HMW Question: How might we help students separate the logic of finding an item from the logic of returning the result?
    • Activity: Unplugged sorting/searching activity using a deck of playing cards to manually track "current max" before writing the Java code.

    Prototype

    • A reference guide of standard algorithms, an unplugged card activity, a pair-programming tracing worksheet, and a Free Response Question (FRQ) practice prompt.
    • Students physically trace algorithms before coding them in an IDE.

    Test

    • Review student tracing tables for common off-by-one errors.
    • Analyze execution results in unit tests to see if students handle edge cases (e.g., negative numbers for max algorithms).
    Slide 3: Finding Min and Max
    • Scenario: Finding the coldest day of the year.
    • Common Trap: Initializing min = 0. If all temperatures are above 0, the program incorrectly reports 0.
    • The Fix: Always set min = arr[0] and start your loop at index 1.
    </li>

In-Class Unplugged Activity

  • Group Exercise (15 mins): "The Card Shark Algorithm"
    • Break students into pairs.
    • Give each pair 5 random playing cards.

Prompts:

  • One student plays the "Processor" (can only look at one card at a time and keep one "current best" in mind).
  • The other student plays the "Array" (reveals cards one by one).
  • Write pseudocode based on the physical steps taken to find the highest card. 
// CODE_RUNNER: Run it, then change one score and predict the new output
// Buggy Implementation - Live Demo
int[] arr = {10, 20, 30, 40};
for (int i = 0; i < arr.length; i++) {
    arr[i] = arr[i + 1]; // ArrayIndexOutOfBoundsException when i = arr.length - 1!
}

Slide 3: Corrected Implementation

// CODE_RUNNER: Run it, then change one score and predict the new output
// Corrected Shift Left Implementation
int[] arr = {10, 20, 30, 40};
int temp = arr[0]; // Save the first element

for (int i = 0; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1]; // Shift remaining elements left
}
arr[arr.length - 1] = temp; // Place first element at the end

// Print result: [20, 30, 40, 10]

📄 Student Homework Assignment Handout

Title: Temperature Data Processor Lab

Instructions: Complete the static methods in the TemperatureAnalyzer class below using standard 1D array traversal algorithms.

// CODE_RUNNER: Run it, then change one score and predict the new output
public class TemperatureAnalyzer {

    /**
     * Counts how many times two consecutive days both had 
     * temperatures strictly greater than 90 degrees.
     */
    public static int countHeatWaves(int[] temps) {
        int count = 0;
        // TODO: Implement using a loop bound of temps.length - 1
        for (int i = 0; i < temps.length - 1; i++) {
            if (temps[i] > 90 && temps[i + 1] > 90) {
                count++;
            }
        }
        return count;
    }

    /**
     * Reverses the elements of the temps array in-place 
     * using a while loop and a swap mechanism.
     */
    public static void reverseLog(int[] temps) {
        int left = 0;
        int right = temps.length - 1;
        while (left < right) {
            int temp = temps[left];
            temps[left] = temps[right];
            temps[right] = temp;
            left++;
            right--;
        }
    }
}