AP CSA Unit 6: Algorithms, Inheritance & Recursion

1. Big Idea: Algorithms Give Objects and Data a Purpose

Units 1–5 taught students how to store information, make decisions, repeat actions, design objects, and organize collections. Unit 6 asks the next question: How do we use those tools to solve problems efficiently and flexibly?

2. Searching Algorithms

Linear Search: Stack of Papers

Linear search checks values one at a time. It works on unsorted or sorted data, but it may need to inspect every element.

public static int linearSearch(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

Binary Search: Dictionary Strategy

Binary search repeatedly checks the middle of a sorted collection and throws away half of the remaining search space.

public static int binarySearch(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (target < nums[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

3. Sorting Algorithms

Sorting puts data into an order. AP CSA expects students to recognize, trace, and reason about standard sorts.

for (int i = 0; i < arr.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}

Merge Sort: Merge Two Sorted Race Results

Merge sort breaks a list into smaller lists, sorts them, then merges sorted pieces back together.

// AP students should understand the recursive idea more than memorize full code:
// 1. Split the array into halves.
// 2. Recursively sort each half.
// 3. Merge the two sorted halves.

4. Inheritance: Class Family Trees

Inheritance models an is-a relationship. A Runner is an Athlete. A Jumper is an Athlete. Shared information belongs in the superclass.

public class Athlete {
    private String name;
    private int grade;

    public Athlete(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }

    public String getName() {
        return name;
    }

    public int getGrade() {
        return grade;
    }

    public String toString() {
        return name + " (grade " + grade + ")";
    }
}

public class Runner extends Athlete {
    private double bestMile;

    public Runner(String name, int grade, double bestMile) {
        super(name, grade);
        this.bestMile = bestMile;
    }

    public double getBestMile() {
        return bestMile;
    }

    public String toString() {
        return super.toString() + ", mile PR: " + bestMile;
    }
}

5. Polymorphism: One Clipboard, Different Athletes

Polymorphism means a superclass reference can point to a subclass object. The reference type controls what methods are visible at compile time, but the actual object controls overridden behavior at run time.

Athlete a = new Runner("Mia", 12, 5.12);
System.out.println(a.toString());

Even though the variable type is Athlete, Java runs the Runner version of toString() because the actual object is a Runner.

// a.getBestMile(); // compile error if a is declared as Athlete

6. Interfaces and Comparable

An interface is a contract. A class that implements an interface promises to provide certain methods.

For AP CSA, the most useful interface to preview is Comparable, which allows objects to define how they should be ordered.

public class Runner extends Athlete implements Comparable<Runner> {
    private double bestMile;

    public int compareTo(Runner other) {
        if (bestMile < other.bestMile) {
            return -1;
        } else if (bestMile > other.bestMile) {
            return 1;
        } else {
            return 0;
        }
    }
}

7. Recursion: A Method Calling Itself

Recursion solves a problem by reducing it to a smaller version of the same problem.

Countdown Example

public static void countdown(int n) {
    if (n == 0) {
        System.out.println("Go!");
    } else {
        System.out.println(n);
        countdown(n - 1);
    }
}

countdown(3) prints 3, calls countdown(2)
countdown(2) prints 2, calls countdown(1)
countdown(1) prints 1, calls countdown(0)
countdown(0) prints Go!

Factorial Example

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

Recursive Binary Search

public static int binarySearch(int[] nums, int target, int low, int high) {
    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;

    if (nums[mid] == target) {
        return mid;
    } else if (target < nums[mid]) {
        return binarySearch(nums, target, low, mid - 1);
    } else {
        return binarySearch(nums, target, mid + 1, high);
    }
}

8. Try It in Java

Use the IDE to run the examples. A good student task is to change the data, add print statements, and trace the result before running.

Starter Program: Athlete Ranking System

import java.util.ArrayList;

class Athlete {
    private String name;
    private int grade;

    public Athlete(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }

    public String getName() { return name; }
    public int getGrade() { return grade; }

    public String toString() {
        return name + " grade " + grade;
    }
}

class Runner extends Athlete {
    private double mileTime;

    public Runner(String name, int grade, double mileTime) {
        super(name, grade);
        this.mileTime = mileTime;
    }

    public double getMileTime() { return mileTime; }

    public String toString() {
        return super.toString() + " mile: " + mileTime;
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Runner> team = new ArrayList<Runner>();
        team.add(new Runner("Mia", 12, 5.12));
        team.add(new Runner("Alex", 11, 5.35));
        team.add(new Runner("Sam", 10, 5.05));

        Runner best = team.get(0);
        for (Runner r : team) {
            if (r.getMileTime() < best.getMileTime()) {
                best = r;
            }
        }

        System.out.println("Best runner: " + best);
    }
}

9. AP-Style Tracing Challenges

int[] a = {4, 2, 7, 1};
int max = a[0];
for (int i = 1; i < a.length; i++) {
    if (a[i] > max) {
        max = a[i];
    }
}
System.out.println(max);

public static int mystery(int n) {
    if (n == 0) return 0;
    return n + mystery(n - 1);
}
System.out.println(mystery(4));

Athlete a = new Runner("Mia", 12, 5.12);
System.out.println(a.toString());

int[] nums = {9, 1, 4, 7, 2};
binarySearch(nums, 7);

10. Debugging Challenges

public static int factorial(int n) {
    return n * factorial(n);
}

public Runner(String name, int grade, double mileTime) {
    this.mileTime = mileTime;
}

Athlete a = new Runner("Mia", 12, 5.12);
System.out.println(a.getMileTime());

11. AP-Style Multiple Choice

12. FRQ Practice

FRQ A: Search and Rank Runners

Assume a Runner class has getName() and getMileTime(). Write a method bestRunner that takes an ArrayList<Runner> and returns the runner with the lowest mile time. If the list is empty, return null.

public static Runner bestRunner(ArrayList<Runner> team) {
    if (team.size() == 0) {
        return null;
    }

    Runner best = team.get(0);
    for (Runner r : team) {
        if (r.getMileTime() < best.getMileTime()) {
            best = r;
        }
    }
    return best;
}

FRQ B: Recursive Sum

Write a recursive method sumTo that returns the sum of all integers from 1 to n. For example, sumTo(4) returns 10.

public static int sumTo(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sumTo(n - 1);
}

FRQ C: Inheritance Design

Design a superclass EventPerformance and a subclass RunningPerformance. The superclass should store athlete name and event name. The subclass should add time in seconds and override toString().

13. AP Exam Strategy: Recognize the Problem Type

14. Capstone Project: Track Meet Ranking System

This project ties together the entire AP CSA site. Students build a program that ranks athletes or physics simulation results using inheritance and algorithms.

Required Features

• Superclass: Athlete or Performance
• At least two subclasses, such as Runner and FieldEventAthlete
• ArrayList storage
• Linear search by name or event
• Sorting or ranking algorithm written by the student
• At least one overridden toString()
• At least one recursive method or recursive search extension
• Testing table with expected and actual output

Project Options