4.13 Implementing 2D Algorithms

1. Reference Guide

Key Topics

• A 2D array is an array of arrays. Every algorithm here is a 1D algorithm you already know, run once per row.
• Always use <, never <=. grid.length is one index past the last valid row.
• return leaves the whole method from any depth, so it is the cleanest way to stop a search.

Picking an Algorithm

• Where is it? → search, return {row, col}, and return at the first match
• Total, average, or count → one traversal with accumulators; guard divide-by-zero and cast to double
• Best so far → track a “champion” that starts at a value guaranteed to lose, such as -1
• Per-row answer → declare the accumulator inside the row loop so it restarts for each row

2. LxD Cycle Process

Empathize: Students can trace a nested loop when told exactly how, but stall when a question needs the location of a match, a per-row total, or a “best so far.” Dividing two ints also gives a wrong average with no error.

Define:

• POV: CSA students need to see 2D algorithms as the 1D loops they already know, run once per row.
• Learning Goal: Students will traverse a grid in row-major and column-major order, search it and return a location, accumulate counts and averages, and track a running maximum.

Ideate:

• HMW Question: How might we make the early return and the int division bug visible so students feel why each fix exists?
• Activity: Trace traversal order in the MCQ, analyze your own homework minutes in the popcorn hack, then write findFirstBelow and podTotals.

Prototype:

• A reference guide, three runnable Java examples, a personalized popcorn hack, an MCQ knowledge check, and a scaffolded grade rubric.
• Excellence means explaining why the loop bounds are not swapped, why return stops the search, and why the average needs a cast.

Test:

• Ask peers in peer review to complete the practice without additional explanation.
• Observe whether peers skip the -1 seats and restart the total for every row.
• On submission, collect evidence from runner output, MCQ results, AI grading and student explanations.
• After teaching, grading and analysis, come back and revise lesson to complete teaching cycle for continuous improvement.

3. College Board Requirements

AP CSA Unit 4, Topic 4.13 Implementing 2D Array Algorithms. Paraphrased from the course and exam description (College Board, 2025, p. 124):

• Standard 2D array algorithms use nested-loop traversals to find a minimum or maximum value, compute a sum or average, and count the elements that have a particular property.
• These algorithms can work on every element or on a designated row, column, or other part of the array.
• Traversal order, row-major or column-major, depends on which loop is on the outside.

4. Lesson Plan

Learning Objective: Write nested loops over a 2D array to traverse it, search it for a value and its location, accumulate sums, counts and averages, and track a running maximum.

Success Criteria: You can explain why col is bounded by chart[row].length, why return stops the search, and why (double) is needed for the average.

Tech Talk (5 minutes)

The Sub Call. Your teacher is out sick and everything you need lives in one seating chart. A seating chart is a 2D array: rows are pods and columns are seats. A 2D array is an array wearing another array as a trenchcoat.

chart                <- outer array: one slot per ROW
   chart[row]           <- the array inside it: one slot per SEAT
      chart[row][col]      <- one specific seat

for (int row = 0; row < chart.length; row++) {              // rows
    for (int col = 0; col < chart[row].length; col++) {     // seats in that row
        // work with chart[row][col]
    }
}

5. Code Examples

A. Traversal order. The TraversalOrder class walks the same grid row-major and column-major

Common starting mistake:

for (int col = 0; col < grid.length; col++)         // wrong: grid.length counts rows
for (int col = 0; col < grid[row].length; col++)    // right: columns in this row

Terminology:

Row-major is the default: the row loop is on the outside. Swap which loop is outside and you get column-major. That swap is the entire idea of traversal order.

// CODE_RUNNER: Predict both lines before running, then add a third row of 7, 8, 9
// Row-major vs. column-major
public class TraversalOrder {
    public static void main(String[] args) {
        int[][] grid = {
            {1, 2, 3},
            {4, 5, 6}
        };

        String rowMajor = "";
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length; col++) {
                rowMajor += grid[row][col] + " ";
            }
        }
        System.out.println("row-major:    " + rowMajor);

        String colMajor = "";
        for (int col = 0; col < grid[0].length; col++) {
            for (int row = 0; row < grid.length; row++) {
                colMajor += grid[row][col] + " ";
            }
        }
        System.out.println("column-major: " + colMajor);
    }
}

TraversalOrder.main(null);

B. Finding a seat. The SeatSearch class returns the location of a score and stops early

Common starting mistake:

return new int[] {0, 0};     // wrong: 0 is a real seat, so it can't mean "not found"
return new int[] {-1, -1};   // right: -1 is not a valid index

Terminology:

return leaves the whole method from any depth, so the search stops at the first match. Looking for a score that is not in the grid is always the worst case, because every seat must be checked.

// CODE_RUNNER: Predict both results before running, then search for 87 and watch how many seats are visited
// Search with an early return
import java.util.Arrays;

public class SeatSearch {
    static int visited = 0;

    public static int[] findSeat(int[][] chart, int target) {
        visited = 0;
        for (int row = 0; row < chart.length; row++) {
            for (int col = 0; col < chart[row].length; col++) {
                visited++;
                if (chart[row][col] == target) {
                    return new int[] {row, col};
                }
            }
        }
        return new int[] {-1, -1};
    }

    public static void main(String[] args) {
        int[][] scoreChart = {
            {87, 92, -1, 76, 88, 91},
            {-1, 65, 72, 89, -1, 94},
            {90, 88, 77, -1, 82, 79},
            {68, -1, 95, 91, 84, -1},
            {73, 86, 90, 88, -1, 77}
        };

        int[] found = findSeat(scoreChart, 94);
        System.out.println("94  -> " + Arrays.toString(found) + ", visited " + visited + " of 30 seats");

        int[] missing = findSeat(scoreChart, 100);
        System.out.println("100 -> " + Arrays.toString(missing) + ", visited " + visited + " of 30 seats");
    }
}

SeatSearch.main(null);

C. The headcount. The ClassSummary class counts seats and averages scores in one traversal

Common starting mistake:

double avg = totalScore / occupiedCount;            // int / int truncates first
double avg = (double) totalScore / occupiedCount;   // cast first, then divide

Terminology:

emptyCount, occupiedCount and totalScore are accumulators updated in a single pass. Divide by the occupied seats, since empty seats never took the quiz, and guard against dividing by zero if the whole class is absent.

// CODE_RUNNER: Predict both averages before running, then change one score and run it again
// One traversal, three accumulators
public class ClassSummary {
    public static void main(String[] args) {
        int[][] scoreChart = {
            {87, 92, -1, 76, 88, 91},
            {-1, 65, 72, 89, -1, 94},
            {90, 88, 77, -1, 82, 79},
            {68, -1, 95, 91, 84, -1},
            {73, 86, 90, 88, -1, 77}
        };

        int emptyCount = 0, occupiedCount = 0, totalScore = 0;
        for (int row = 0; row < scoreChart.length; row++) {
            for (int col = 0; col < scoreChart[row].length; col++) {
                if (scoreChart[row][col] == -1) {
                    emptyCount++;
                } else {
                    occupiedCount++;
                    totalScore += scoreChart[row][col];
                }
            }
        }

        System.out.println("empty: " + emptyCount + ", occupied: " + occupiedCount);
        System.out.println("int division: " + (totalScore / occupiedCount));
        System.out.println("with a cast:  " + ((double) totalScore / occupiedCount));
    }
}

ClassSummary.main(null);

6. Hacks & Practice Tasks

Prepare your submission IPYNB

1. Create a new notebook in your portfolio homework area: _notebooks/homework.
2. Add one raw cell at the top with the frontmatter:

---
layout: post
codemirror: true
title: Implementing 2D Algorithms HW
categories: [Java]
lesson_language: Java
lesson_topic: Implementing 2D Algorithms HW
lesson_part: interactive
lesson_type: lesson
permalink: /csa/unit_04/4_13-hw
author: yourGithubID
---

1. Add code cells for the Popcorn Hack and the Homework Hack. Make sure every cell runs with visible output.
2. Submit the link to your published page at the bottom of this page, and paste this in the description box:

Lesson: CSA 4.13 Implementing 2D Algorithms
MCQ 4.13: <paste the copied result line, such as 3/4 | answers: C,B,C,B>
Popcorn: a 3 by 4 grid of my own, most minutes and its location plus the count printed (yes/no)
Homework: findFirstBelow output = <output>
Homework: podTotals output = <output>

Submission Safety Rules (Read First)

• One class per cell, ending with ClassName.main(null);.
• Run each cell and leave the output showing.
• Use your own values, not the sample answer.
• Include your MCQ score.
• Use ## headings or smaller.

Popcorn Hack (In-Class)

2-minute challenge: analyze your own homework minutes for 3 school weeks (4 days each), then run the cell.

1. Store the minutes in an int[][] with one row per week
2. Find the most minutes in one day and where it happened
3. Count the days with at least 60 minutes

Replace the sample values with your own.

// CODE_RUNNER: Replace the sample values with your own, then run it
// Practice #1 - Try it yourself first!
public class MyHomeworkGrid {
    public static void main(String[] args) {
        // Try writing your own code here first!

        // Sample answer:
        int[][] minutes = {
            {45, 60, 30, 75},
            {20, 90, 55, 40},
            {65, 35, 80, 50}
        };

        int best = -1, bestRow = -1, bestCol = -1, count = 0;
        for (int row = 0; row < minutes.length; row++) {
            for (int col = 0; col < minutes[row].length; col++) {
                if (minutes[row][col] > best) {
                    best = minutes[row][col];
                    bestRow = row;
                    bestCol = col;
                }
                if (minutes[row][col] >= 60) count++;
            }
        }
        System.out.println("Most: " + best + " (week " + (bestRow + 1) + ", day " + (bestCol + 1) + "), days at 60+: " + count);
    }
}

MyHomeworkGrid.main(null);

MCQ Check

4 questions, one at a time. Answer, check, then go to the next one. At the end, copy the score line into your submission notes.

Homework Hack

Task: Write two algorithms for the seating chart, where -1 is an empty seat. findFirstBelow returns the {row, col} of the first occupied seat with a score below the threshold, in row-major order, or {-1, -1} if there is none. podTotals returns one total per pod, skipping empty seats.

Solution Skeleton:

// CODE_RUNNER: Fill in the blanks, then run it
import java.util.Arrays;

public class GridAlgorithms {
    // 1. Row-major loops. Skip -1 (empty seat). Return {row, col} the moment you find a score below threshold
    public static int[] findFirstBelow(int[][] chart, int threshold) {
        return new int[] {0, 0};
    }

    // 2. One total per pod. Start each pod's total at 0 inside the row loop and skip -1
    public static int[] podTotals(int[][] chart) {
        return new int[0];
    }

    public static void main(String[] args) {
        int[][] chart = {
            {70, -1, 55},
            {88, 92, -1},
            {40, 65, 90}
        };

        System.out.println(Arrays.toString(findFirstBelow(chart, 60)));   // expect [0, 2]
        System.out.println(Arrays.toString(findFirstBelow(chart, 30)));   // expect [-1, -1]
        System.out.println(Arrays.toString(podTotals(chart)));            // expect [125, 180, 195]
    }
}

GridAlgorithms.main(null);

Grading Plan (1 Point Total)

Quick Validation Checklist

• Each cell ends with ClassName.main(null); and shows output.
• MCQ score in the notes.
• -1 seats are skipped, not counted as scores.
• The pod total restarts for every row.

7. Lesson Revisions

Revision Made: Rebuilt the lesson in the 4.10 layout. The chapter exercises became three runnable examples (traversal order, search with an early return, and accumulators with the int division trap). The top-scorer capstone became the popcorn hack, and the homework now asks for a search and a per-row accumulator.

(Add what you changed after peer review.)

8. Feedback Evidence

Feedback Received: (Add after peer review: what peers did, where they got stuck, and what you changed because of it.)

9. References

College Board. (2025). AP Computer Science A course and exam description (Effective fall 2025). Topic 4.13 Implementing 2D Array Algorithms, p. 124.

Oracle. (n.d.). Arrays. In The Java Tutorials.

Oracle. (n.d.). ArrayIndexOutOfBoundsException. In Java SE 8 documentation.

Need to update a submission later? Open the submissions dashboard.