In Insertion Sort on an array of $N$ elements, how many times does the outer loop execute, and what is the invariant at the start of outer loop iteration `i`?

• The outer loop runs from **`i = 1` to `i = N - 1`** (a total of **$N - 1$ passes**). • **Loop Invariant**: At the start of pass `i`, the subarray `arr[0..i - 1]` (the first `i` elements) consists of the original first `i` elements in **sorted order**.

Distinguish between Method Overriding (across superclass/subclass) and Method Overloading, and explain how `super.methodName(...)` works.

• **Method Overriding**: A subclass defines a method with the **exact same method signature** (name, parameter types, and compatible return type) as an inherited method in its superclass, replacing its behavior for instances of the subclass. • **Calling the Superclass Version**: Inside a subclass method, writing **`super.methodName(args)`** invokes the superclass's version of that method (avoiding infinite recursion when extending superclass behavior, e.g., `return super.getPay() + bonus;`).

How do Constructors work in a Subclass, and what happens if a Subclass Constructor does NOT explicitly call `super(...)` on its very first line?

• **Constructors are NEVER inherited** by subclasses. • **Explicit `super(...)` Call**: To call a superclass constructor, `super(args);` **MUST be the very first statement** in the subclass constructor. • **Implicit `super()` Rule**: If a subclass constructor does NOT explicitly write `super(...)` on line 1, the Java compiler automatically inserts a no-argument call **`super();`** as the first line. **Compile-Time Error Trap**: If the superclass has a parameterized constructor (e.g., `public Animal(String name)`) and **NO no-arg constructor `public Animal()`**, omitting `super(name)` in the subclass constructor causes a **compile-time error**!

In Polymorphism (`SuperClass obj = new SubClass();`), state the Golden Rule for Compile-Time Type Checking vs. Run-Time Dynamic Method Dispatch (Late Binding).

Consider `Animal a = new Dog();` (where **Declared/Compile-Time Type** is `Animal` and **Actual/Run-Time Object Type** is `Dog`): 1. **At COMPILE TIME, the Compiler checks the DECLARED TYPE (`Animal`, Left Side)**: - The method being called (`a.speak()` or `a.wagTail()`) **MUST exist in the `Animal` class (or its superclasses)**! If `wagTail()` is defined ONLY in `Dog` and NOT in `Animal`, then `a.wagTail();` causes a **COMPILE-TIME ERROR** (unless explicitly downcast via `((Dog) a).wagTail()`). 2. **At RUN TIME, the JVM executes the OVERRIDDEN method of the ACTUAL OBJECT TYPE (`Dog`, Right Side)**: - If `a.speak()` compiles, Java uses **Dynamic Method Dispatch** to run `Dog`'s overridden `speak()` method!

On an AP CS A Multiple-Choice Question showing an array before sorting and after 3 passes of an unknown sort, how do you tell whether the algorithm is Selection Sort or Insertion Sort?

Consider initial array: `{8, 5, 2, 9, 1, 6}`. • **After 3 Passes of Selection Sort**: The **3 smallest elements in the ENTIRE array (`1, 2, 5`)** are locked in their final absolute positions at indices `0, 1, 2`: **`{1, 2, 5, 9, 8, 6}`**. • **After 3 Passes of Insertion Sort** (indices `i = 1, 2, 3`): The **first 4 elements (`8, 5, 2, 9`) are sorted relative to one another**, while elements at index `4` and `5` (`1, 6`) have **NEVER been touched yet**: **`{2, 5, 8, 9, 1, 6}`**! *(Rule of thumb: If the global minimum `1` moved from the back to index `0`, it MUST be Selection Sort; if the back of the array is completely untouched, it MUST be Insertion Sort!)*

How does a Tree-Recursive Method with TWO recursive calls (like Fibonacci `fib(n) = fib(n - 1) + fib(n - 2)`) behave, and how many total calls or additions does it make?

```java public static int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } ``` Draw a **recursion tree** rather than trying to trace in your head: • `fib(0) = 0`, `fib(1) = 1`, `fib(2) = 1`, `fib(3) = 2`, `fib(4) = 3`, `fib(5) = 5`, `fib(6) = 8`. • Because each call branches into two subcalls, the number of calls grows **exponentially ($O(2^n)$)**, recomputing small subproblems like `fib(2)` many times.

What is the universal Superclass of all classes in Java, and which two methods does every Java class inherit from it on the AP CS A subset?

Every class in Java implicitly or explicitly extends **`java.lang.Object`**. The two `Object` methods tested on AP CS A are: 1. **`public String toString()`**: Returns a String representation of the object. 2. **`public boolean equals(Object other)`**: By default in `Object`, `.equals()` just checks `this == other` (memory address equality), until overridden by subclasses like `String` or `Integer`.

What does the following recursive method compute for positive integers `a` and `b`: `public static int mystery(int a, int b) { if (b == 0) return 0; return a + mystery(a, b - 1); }`?

It adds `a` to itself `b` times, computing the **product $a \times b$**: • `mystery(a, 0) = 0` • `mystery(a, 1) = a + 0 = a` • `mystery(a, b) = a * b`. *(Note: If the base case were `if (b == 0) return 1;` and the recursive step were `return a * mystery(a, b - 1);`, it would compute the **power $a^b$**!)*

Suppose a sorted array has $N = 2,000$ elements. What is the maximum number of comparisons required by Binary Search, and how does doubling $N$ to $4,000$ change that maximum?

• Since $2^{10} = 1,024$ and $2^{11} = 2,048$, for $N = 2,000$, Binary Search requires at most **$11$ comparisons**. • **Doubling $N$ Rule for Binary Search**: Because each comparison cuts the remaining search space in **half**, **doubling the array size $N$ adds only $+1$ additional comparison** in the worst case (so $N = 4,000 < 4,096 = 2^{12}$ requires at most **$12$ comparisons**!).

Trace the classic recursive value-returning functions: (a) Factorial `fact(n)`, (b) Sum of Digits `sumDigits(n)`, and (c) Base-2 Exponent `pow2(n)`.

• **(a) Factorial ($n!$)**: `if (n <= 1) return 1; return n * fact(n - 1);` (`fact(4)` $= 4 \times 3 \times 2 \times 1 = 24$). • **(b) Sum of Digits**: `if (n < 10) return n; return (n % 10) + sumDigits(n / 10);` (`sumDigits(385)` $= 5 + 8 + 3 = 16$). • **(c) Power ($2^n$)**: `if (n == 0) return 1; return 2 * pow2(n - 1);`.

How do you trace a Recursive String Method such as `rev(String s)` that returns `rev(s.substring(1)) + s.substring(0, 1)`?

```java public static String rev(String s) { if (s.length() <= 1) return s; return rev(s.substring(1)) + s.substring(0, 1); } ``` Every recursive step moves the first character `s.substring(0, 1)` to the **end** and recursively reverses the remaining tail `s.substring(1)`: `rev("cat")` $\rightarrow$ `rev("at") + "c"` $\rightarrow$ `(rev("t") + "a") + "c"` $\rightarrow$ **`"tac"`** (reverses the entire String!).

What happens if a Subclass defines an Instance Variable with the exact same name as an Instance Variable in its Superclass (Field Hiding) or defines a `static` method with the same signature?

Unlike non-`static` instance methods, **instance variables and `static` methods are NOT polymorphic**—they are bound at **compile time** based on the reference's declared type! On the AP CS A exam, subclasses should NEVER redeclare superclass instance variables; instead, pass initial values to the superclass constructor via **`super(args)`**.

Convert the following iterative loop into an equivalent Recursive Method: `int sum = 0; for (int i = 0; i < arr.length; i++) sum += arr[i];`

```java public static int sumArray(int[] arr, int index) { if (index == arr.length) { return 0; // Base case: past the end of the array } return arr[index] + sumArray(arr, index + 1); } ``` Called initially via `sumArray(arr, 0)`.

What does the following recursive method compute (Euclid's Algorithm): `public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }`?

It computes the **Greatest Common Divisor (GCD)** of `a` and `b`. For example, `gcd(48, 18)` $\rightarrow$ `gcd(18, 48 % 18 = 12)` $\rightarrow$ `gcd(12, 18 % 12 = 6)` $\rightarrow$ `gcd(6, 12 % 6 = 0)` $\rightarrow$ returns **`6`**.

How do you trace a Recursive Method that modifies an Array in place, such as `recurArray(int[] arr, int index)`?

Because arrays are passed as **object references**, every recursive call in `recurArray(arr, index + 1)` operates on the **exact same shared array in memory**: • Changes made **before** the recursive call are visible to deeper recursive calls. • Changes made **after** the recursive call occur from the back of the array toward the front as the recursion unwinds.

In Java Inheritance (`public class SubClass extends SuperClass`), what defines an 'IS-A' relationship vs. a 'HAS-A' relationship, and can a subclass directly access `private` instance variables of its superclass?

• **IS-A Relationship (Inheritance via `extends`)**: `Dog extends Animal` means every `Dog` **IS-A** `Animal`. Java supports single inheritance only (a class can `extend` only ONE direct superclass, though hierarchies can be multi-level). • **HAS-A Relationship (Composition)**: A class contains an instance variable that is a reference to another object (e.g., `Car` has a `private Engine eng;`). • **Crucial Encapsulation Rule**: A subclass **CANNOT directly access `private` instance variables or `private` methods of its superclass**! It must use the superclass's `public` (or `protected`) accessor/mutator methods or pass arguments to `super(...)`.

In Selection Sort on an array of $N$ elements, how many times does the outer loop execute, and what is the invariant after `k` passes?

• The outer loop runs from **`i = 0` to `i = N - 2`** (a total of **$N - 1$ passes**, since once the first $N - 1$ smallest elements are in place, the last element at `N - 1` is automatically the largest). • **Loop Invariant**: After `k` passes, the **first `k` elements `arr[0..k - 1]` are the `k` smallest elements of the entire array in their final sorted positions**.

In an Inheritance Hierarchy, if `Class B extends Class A` and `B`'s constructor is `public B(int x, int y) { super(x); this.y = y; }`, in what order do the constructors execute when `new B(3, 5)` is called?

1. `new B(3, 5)` enters `B`'s constructor and immediately calls `super(3)` on line 1. 2. `A`'s constructor calls `Object()`'s constructor first, then executes the body of `A(3)` to completion. 3. Control returns to `B`'s constructor, which executes `this.y = 5;`. **Rule**: Superclass constructors **always finish executing their bodies before** the subclass constructor body runs!

Compare Linear (Sequential) Search and Binary Search, including their preconditions and maximum number of comparisons for an array of size $N$.

• **Linear (Sequential) Search**: - **Precondition**: Works on **ANY** array or `ArrayList` (sorted or unsorted). - **Comparisons**: Best case $= 1$ (target at index `0`); Worst case (target at end or not present) $= \mathbf{N}$ comparisons ($O(N)$). • **Binary Search**: - **Strict Precondition**: The array/list **MUST BE SORTED** in ascending (or descending) order! - **Mechanism**: Compares `target` to `arr[mid]` where `mid = (low + high) / 2`; if `target arr[mid]`, sets `low = mid + 1`. - **Maximum Comparisons**: $\lfloor \log_2(N) \rfloor + 1$ ($O(\log N)$)—e.g., for $N = 1,000$, at most **$10$** comparisons ($2^{10} = 1,024$); for $N = 1,000,000$, at most **$20$** comparisons!

Which Reference Assignments and Downcasts are valid at Compile Time vs. Run Time in an Inheritance Hierarchy (`GradStudent extends Student extends Person`)?

• **Upcasting (Subclass assigned to Superclass reference)**: Always legal without a cast: - `Person p = new Student();` (Valid: a `Student` IS-A `Person`). - `ArrayList list = new ArrayList (); list.add(new GradStudent());` (Valid). • **Assigning Superclass to Subclass without a cast**: - `Student s = new Person();` $\rightarrow$ **COMPILE-TIME ERROR** (a `Person` is not necessarily a `Student`). • **Explicit Downcasting (`(SubClass) ref`)**: - If `Person p = new GradStudent();`, then `Student s = (Student) p;` compiles AND succeeds at run time. - If `Person p = new Person();`, then `Student s = (Student) p;` compiles, but throws a **`ClassCastException` at RUN TIME**!

How does Insertion Sort work, how do you recognize it in code, and why is its Best Case $O(n)$ while its Worst Case is $O(n^2)$?

• **Mechanism**: Starts at index `i = 1` (treating `arr[0]` as a sorted subarray of size 1). In pass `i`, saves `temp = arr[i]` and uses an inner `while` loop (`j = i - 1`) to **shift larger elements (`arr[j] > temp`) one position to the right (`arr[j + 1] = arr[j]`)** until finding the correct spot to insert `temp`. • **How to Recognize in Code**: Outer loop starts at **`i = 1`**; inner `while (j >= 0 && arr[j] > temp)` shifts elements right; `arr[j + 1] = temp;`. • **Performance**: - **Best Case (Already Sorted Ascending)**: Inner `while` condition `arr[j] > temp` is immediately `false` on every pass $\implies$ only **$n - 1$ comparisons and $0$ shifts ($O(n)$)**! - **Worst Case (Reverse Sorted Descending)**: Inner `while` shifts every preceding element on every pass $\implies \frac{n(n-1)}{2}$ comparisons and shifts ($O(n^2)$).

How do you write a complete Subclass on an AP CS A Free-Response Question (e.g., `public class LimitedCustomer extends Customer`) when the superclass has private fields and a method you need to refine?

Follow these 4 rules: 1. **Header**: `public class LimitedCustomer extends Customer` (do NOT redeclare the superclass's private fields!). 2. **Subclass Field**: Declare only the new field(s) unique to the subclass as `private`. 3. **Constructor**: Call **`super(superParams);` on the very first line**, then initialize the subclass's own private field(s). 4. **Overridden Method**: Write the exact same method header as the superclass, and call **`super.methodName(...)`** inside the body to access or extend the superclass's behavior.

Wait—in `SuperClass a = new SubClass();`, if `a.methodA()` (inherited from `SuperClass` and NOT overridden in `SubClass`) internally calls `methodB()` (which IS overridden in `SubClass`), WHICH version of `methodB()` runs?

**`SubClass`'s overridden `methodB()` runs!** This is the #1 AP CS A Inheritance MCQ trap: inside `SuperClass`'s `methodA()`, an unqualified call to `methodB()` is implicitly `this.methodB()`. Because at run time the implicit object `this` is actually an instance of **`SubClass`**, dynamic method dispatch invokes **`SubClass.methodB()`**!

For an 8-element array `{38, 27, 43, 3, 9, 82, 10, 19}`, what does the array look like immediately BEFORE the very final `merge` call of Merge Sort?

Immediately before the final top-level `merge` step combines the left half and right half, the **first 4 elements are completely sorted** and the **last 4 elements are completely sorted** independently: • Left half `{38, 27, 43, 3}` sorted $\rightarrow$ **`{3, 27, 38, 43}`** • Right half `{9, 82, 10, 19}` sorted $\rightarrow$ **`{9, 10, 19, 82}`** • Array just before final `merge`: **`{3, 27, 38, 43, 9, 10, 19, 82}`**.

Trace the recursive Binary Search helper method `bSearch(int[] arr, int low, int high, int target)` and count how many times `bSearch` is called (including the initial call) when searching for a value NOT in the array.

```java public static int bSearch(int[] arr, int low, int high, int target) { if (low > high) return -1; // Base case: not found int mid = (low + high) / 2; if (arr[mid] == target) return mid; else if (target high`** (which returns `-1` without comparing `arr[mid]`)!

How does Merge Sort work recursively ('Divide and Conquer'), and what is its Time Complexity across Best, Average, and Worst cases?

• **Mechanism**: 1. **Divide**: If the subarray has $> 1$ element, split it in half at `mid = (low + high) / 2`. 2. **Conquer (Recurse)**: Recursively call `mergeSort` on the left half `[low..mid]` and the right half `[mid+1..high]`. 3. **Combine (`merge` helper)**: Merge the two sorted halves into a single sorted temporary array by repeatedly comparing the front elements of both halves. • **Performance & Space**: Always runs in **$O(n \log n)$** time in **ALL cases** (best, average, and worst—unaffected by initial order of elements), at the cost of requiring a **temporary array ($O(n)$ extra memory)** during the `merge` step.

What are the two required components of every valid Recursive Method, and what exception is thrown if a recursive method never reaches its Base Case?

1. **Base Case (Halting Case)**: A conditional branch (`if`) that solves the simplest input directly and returns **without making another recursive call**. 2. **Recursive Call (General Case)**: Calls the same method with a modified argument that makes **strict progress toward the Base Case**. • If the base case is missing or unreachable (infinite recursion), the call stack runs out of memory and throws a **`StackOverflowError`** at run time.

Trace Iterative or Recursive Binary Search step-by-step on the sorted 8-element array `arr = {2, 5, 8, 12, 16, 23, 38, 56}` (indices `0` to `7`) when searching for `target = 23`.

• **Iteration 1**: `low = 0`, `high = 7` $\implies$ `mid = (0 + 7) / 2 = 3`. Check `arr[3] = 12`. Since `23 > 12`, eliminate left half and set **`low = mid + 1 = 4`**. • **Iteration 2**: `low = 4`, `high = 7` $\implies$ `mid = (4 + 7) / 2 = 5`. Check `arr[5] = 23`. Match found at index `5` in **2 comparisons**! *(Exam Tip: Always check whether the code updates `low = mid + 1` / `high = mid - 1` and trace the exact integer division `(low + high) / 2`!)*

How does Selection Sort work, how do you recognize it in code, and how do its comparisons and swaps depend on whether the array is already sorted?

• **Mechanism**: In pass `i` (from `0` to `n - 2`), **Selection Sort** scans the unsorted suffix `i` through `n - 1` to find the **index of the minimum element (`minIndex`)**, and then **swaps `arr[i]` with `arr[minIndex]`** at the end of the pass. • **How to Recognize in Code**: Outer loop `i` from `0` to `n - 2`; variable `minIdx = i`; inner loop `j` from `i + 1` to `n - 1` updating `if (arr[j] < arr[minIdx]) minIdx = j;`; **single swap OUTSIDE the inner loop**. • **Performance**: Always makes the **exact same number of comparisons** $\frac{n(n-1)}{2}$ ($O(n^2)$) and at most $n - 1$ swaps **regardless of whether the array is initially sorted, reverse-sorted, or random**!

Compare the Statement Execution Counts of Selection Sort, Insertion Sort, and Merge Sort when given (1) an Already-Sorted Array vs. (2) a Reverse-Sorted Array of size $N$.

How do you trace a Recursive Method that has statements AFTER the recursive call (Unwinding the Call Stack), such as `mystery(n)` printing before vs. after the recursive call?

Consider: ```java public static void printA(int n) { if (n > 0) { System.out.print(n + " "); printA(n - 1); } } public static void printB(int n) { if (n > 0) { printB(n - 1); System.out.print(n + " "); } } ``` • **`printA(3)` (Print BEFORE recursive call)**: Prints in forward order as calls go down the stack: **`3 2 1 `**. • **`printB(3)` (Print AFTER recursive call)**: Pushes `printB(3) -> printB(2) -> printB(1) -> printB(0)` onto the call stack, then prints as the stack **unwinds (LIFO)**: **`1 2 3 `**!

How does Polymorphism work when iterating through an `ArrayList ` or `SuperClass[]` array containing a mix of `SuperClass` and `SubClass` objects?

Suppose `Book` has a method `getInfo()` and `AudioBook extends Book` overrides `getInfo()`: ```java ArrayList library = new ArrayList (); library.add(new Book("Dune")); library.add(new AudioBook("Odyssey", 720)); for (Book b : library) { System.out.println(b.getInfo()); } ``` 1. **Compile Time**: `b` is declared as `Book`, and `Book` has `getInfo()`, so `b.getInfo()` compiles cleanly. 2. **Run Time**: For element `0` (a `Book`), `Book.getInfo()` runs; for element `1` (an `AudioBook`), **`AudioBook.getInfo()` runs automatically via dynamic method dispatch**!

AP Computer Science A: Inheritance, Polymorphism, Recursion & Searching/Sorting Algorithms

High-yield AP Computer Science A Units 9–10 review covering inheritance (`extends`, `super`), method overriding, compile-time vs. run-time polymorphism, `Object` class, recursion tracing, base cases, Linear/Binary Search, and Selection/Insertion/Merge Sort.

Level: advanced
Languages: en → en
Cards: 32
Markdown: AP Computer Science A: Inheritance, Polymorphism, Recursion & Searching/Sorting Algorithms (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	In Insertion Sort on an array of $N$ elements, how many times does the outer loop execute, and what is the invariant at the start of outer loop iteration `i`?	• The outer loop runs from `i = 1` to `i = N - 1` (a total of $N - 1$ passes). • Loop Invariant: At the start of pass `i`, the subarray `arr[0..i - 1]` (the first `i` elements) consists of the original first `i` elements in sorted order.
2	Distinguish between Method Overriding (across superclass/subclass) and Method Overloading, and explain how `super.methodName(...)` works.	• Method Overriding: A subclass defines a method with the exact same method signature (name, parameter types, and compatible return type) as an inherited method in its superclass, replacing its behavior for instances of the subclass. • Calling the Superclass Version: Inside a subclass method, writing `super.methodName(args)` invokes the superclass's version of that method (avoiding infinite recursion when extending superclass behavior, e.g., `return super.getPay() + bonus;`).
3	How do Constructors work in a Subclass, and what happens if a Subclass Constructor does NOT explicitly call `super(...)` on its very first line?	• Constructors are NEVER inherited by subclasses. • Explicit `super(...)` Call: To call a superclass constructor, `super(args);` MUST be the very first statement in the subclass constructor. • Implicit `super()` Rule: If a subclass constructor does NOT explicitly write `super(...)` on line 1, the Java compiler automatically inserts a no-argument call `super();` as the first line. Compile-Time Error Trap: If the superclass has a parameterized constructor (e.g., `public Animal(String name)`) and NO no-arg constructor `public Animal()`, omitting `super(name)` in the subclass constructor causes a compile-time error!
4	In Polymorphism (`SuperClass obj = new SubClass();`), state the Golden Rule for Compile-Time Type Checking vs. Run-Time Dynamic Method Dispatch (Late Binding).	Consider `Animal a = new Dog();` (where Declared/Compile-Time Type is `Animal` and Actual/Run-Time Object Type is `Dog`): 1. At COMPILE TIME, the Compiler checks the DECLARED TYPE (`Animal`, Left Side): - The method being called (`a.speak()` or `a.wagTail()`) MUST exist in the `Animal` class (or its superclasses)! If `wagTail()` is defined ONLY in `Dog` and NOT in `Animal`, then `a.wagTail();` causes a COMPILE-TIME ERROR (unless explicitly downcast via `((Dog) a).wagTail()`). 2. At RUN TIME, the JVM executes the OVERRIDDEN method of the ACTUAL OBJECT TYPE (`Dog`, Right Side): - If `a.speak()` compiles, Java uses Dynamic Method Dispatch to run `Dog`'s overridden `speak()` method!
5	On an AP CS A Multiple-Choice Question showing an array before sorting and after 3 passes of an unknown sort, how do you tell whether the algorithm is Selection Sort or Insertion Sort?	Consider initial array: `{8, 5, 2, 9, 1, 6}`. • After 3 Passes of Selection Sort: The 3 smallest elements in the ENTIRE array (`1, 2, 5`) are locked in their final absolute positions at indices `0, 1, 2`: `{1, 2, 5, 9, 8, 6}`. • After 3 Passes of Insertion Sort (indices `i = 1, 2, 3`): The first 4 elements (`8, 5, 2, 9`) are sorted relative to one another, while elements at index `4` and `5` (`1, 6`) have NEVER been touched yet: `{2, 5, 8, 9, 1, 6}`! (Rule of thumb: If the global minimum `1` moved from the back to index `0`, it MUST be Selection Sort; if the back of the array is completely untouched, it MUST be Insertion Sort!)
6	How does a Tree-Recursive Method with TWO recursive calls (like Fibonacci `fib(n) = fib(n - 1) + fib(n - 2)`) behave, and how many total calls or additions does it make?	```java public static int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } ``` Draw a recursion tree rather than trying to trace in your head: • `fib(0) = 0`, `fib(1) = 1`, `fib(2) = 1`, `fib(3) = 2`, `fib(4) = 3`, `fib(5) = 5`, `fib(6) = 8`. • Because each call branches into two subcalls, the number of calls grows exponentially ($O(2^n)$), recomputing small subproblems like `fib(2)` many times.
7	What is the universal Superclass of all classes in Java, and which two methods does every Java class inherit from it on the AP CS A subset?	Every class in Java implicitly or explicitly extends `java.lang.Object`. The two `Object` methods tested on AP CS A are: 1. `public String toString()`: Returns a String representation of the object. 2. `public boolean equals(Object other)`: By default in `Object`, `.equals()` just checks `this == other` (memory address equality), until overridden by subclasses like `String` or `Integer`.
8	What does the following recursive method compute for positive integers `a` and `b`: `public static int mystery(int a, int b) { if (b == 0) return 0; return a + mystery(a, b - 1); }`?	It adds `a` to itself `b` times, computing the product $a \times b$: • `mystery(a, 0) = 0` • `mystery(a, 1) = a + 0 = a` • `mystery(a, b) = a * b`. (Note: If the base case were `if (b == 0) return 1;` and the recursive step were `return a mystery(a, b - 1);`, it would compute the power $a^b$!)*
9	Suppose a sorted array has $N = 2,000$ elements. What is the maximum number of comparisons required by Binary Search, and how does doubling $N$ to $4,000$ change that maximum?	• Since $2^{10} = 1,024$ and $2^{11} = 2,048$, for $N = 2,000$, Binary Search requires at most $11$ comparisons. • Doubling $N$ Rule for Binary Search: Because each comparison cuts the remaining search space in half, doubling the array size $N$ adds only $+1$ additional comparison in the worst case (so $N = 4,000 < 4,096 = 2^{12}$ requires at most $12$ comparisons!).
10	Trace the classic recursive value-returning functions: (a) Factorial `fact(n)`, (b) Sum of Digits `sumDigits(n)`, and (c) Base-2 Exponent `pow2(n)`.	• (a) Factorial ($n!$): `if (n <= 1) return 1; return n * fact(n - 1);` (`fact(4)` $= 4 \times 3 \times 2 \times 1 = 24$). • (b) Sum of Digits: `if (n < 10) return n; return (n % 10) + sumDigits(n / 10);` (`sumDigits(385)` $= 5 + 8 + 3 = 16$). • (c) Power ($2^n$): `if (n == 0) return 1; return 2 * pow2(n - 1);`.
11	How do you trace a Recursive String Method such as `rev(String s)` that returns `rev(s.substring(1)) + s.substring(0, 1)`?	```java public static String rev(String s) { if (s.length() <= 1) return s; return rev(s.substring(1)) + s.substring(0, 1); } ``` Every recursive step moves the first character `s.substring(0, 1)` to the end and recursively reverses the remaining tail `s.substring(1)`: `rev("cat")` $\rightarrow$ `rev("at") + "c"` $\rightarrow$ `(rev("t") + "a") + "c"` $\rightarrow$ `"tac"` (reverses the entire String!).
12	What happens if a Subclass defines an Instance Variable with the exact same name as an Instance Variable in its Superclass (Field Hiding) or defines a `static` method with the same signature?	Unlike non-`static` instance methods, instance variables and `static` methods are NOT polymorphic—they are bound at compile time based on the reference's declared type! On the AP CS A exam, subclasses should NEVER redeclare superclass instance variables; instead, pass initial values to the superclass constructor via `super(args)`.
13	Convert the following iterative loop into an equivalent Recursive Method: `int sum = 0; for (int i = 0; i < arr.length; i++) sum += arr[i];`	```java public static int sumArray(int[] arr, int index) { if (index == arr.length) { return 0; // Base case: past the end of the array } return arr[index] + sumArray(arr, index + 1); } ``` Called initially via `sumArray(arr, 0)`.
14	What does the following recursive method compute (Euclid's Algorithm): `public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }`?	It computes the Greatest Common Divisor (GCD) of `a` and `b`. For example, `gcd(48, 18)` $\rightarrow$ `gcd(18, 48 % 18 = 12)` $\rightarrow$ `gcd(12, 18 % 12 = 6)` $\rightarrow$ `gcd(6, 12 % 6 = 0)` $\rightarrow$ returns `6`.
15	How do you trace a Recursive Method that modifies an Array in place, such as `recurArray(int[] arr, int index)`?	Because arrays are passed as object references, every recursive call in `recurArray(arr, index + 1)` operates on the exact same shared array in memory: • Changes made before the recursive call are visible to deeper recursive calls. • Changes made after the recursive call occur from the back of the array toward the front as the recursion unwinds.
16	In Java Inheritance (`public class SubClass extends SuperClass`), what defines an 'IS-A' relationship vs. a 'HAS-A' relationship, and can a subclass directly access `private` instance variables of its superclass?	• IS-A Relationship (Inheritance via `extends`): `Dog extends Animal` means every `Dog` IS-A `Animal`. Java supports single inheritance only (a class can `extend` only ONE direct superclass, though hierarchies can be multi-level). • HAS-A Relationship (Composition): A class contains an instance variable that is a reference to another object (e.g., `Car` has a `private Engine eng;`). • Crucial Encapsulation Rule: A subclass CANNOT directly access `private` instance variables or `private` methods of its superclass! It must use the superclass's `public` (or `protected`) accessor/mutator methods or pass arguments to `super(...)`.
17	In Selection Sort on an array of $N$ elements, how many times does the outer loop execute, and what is the invariant after `k` passes?	• The outer loop runs from `i = 0` to `i = N - 2` (a total of $N - 1$ passes, since once the first $N - 1$ smallest elements are in place, the last element at `N - 1` is automatically the largest). • Loop Invariant: After `k` passes, the first `k` elements `arr[0..k - 1]` are the `k` smallest elements of the entire array in their final sorted positions.
18	In an Inheritance Hierarchy, if `Class B extends Class A` and `B`'s constructor is `public B(int x, int y) { super(x); this.y = y; }`, in what order do the constructors execute when `new B(3, 5)` is called?	1. `new B(3, 5)` enters `B`'s constructor and immediately calls `super(3)` on line 1. 2. `A`'s constructor calls `Object()`'s constructor first, then executes the body of `A(3)` to completion. 3. Control returns to `B`'s constructor, which executes `this.y = 5;`. Rule: Superclass constructors always finish executing their bodies before the subclass constructor body runs!
19	Compare Linear (Sequential) Search and Binary Search, including their preconditions and maximum number of comparisons for an array of size $N$.	• Linear (Sequential) Search: - Precondition: Works on ANY array or `ArrayList` (sorted or unsorted). - Comparisons: Best case $= 1$ (target at index `0`); Worst case (target at end or not present) $= \mathbf{N}$ comparisons ($O(N)$). • Binary Search: - Strict Precondition: The array/list MUST BE SORTED in ascending (or descending) order! - Mechanism: Compares `target` to `arr[mid]` where `mid = (low + high) / 2`; if `target < arr[mid]`, sets `high = mid - 1`; if `target > arr[mid]`, sets `low = mid + 1`. - Maximum Comparisons: $\lfloor \log_2(N) \rfloor + 1$ ($O(\log N)$)—e.g., for $N = 1,000$, at most $10$ comparisons ($2^{10} = 1,024$); for $N = 1,000,000$, at most $20$ comparisons!
20	Which Reference Assignments and Downcasts are valid at Compile Time vs. Run Time in an Inheritance Hierarchy (`GradStudent extends Student extends Person`)?	• Upcasting (Subclass assigned to Superclass reference): Always legal without a cast: - `Person p = new Student();` (Valid: a `Student` IS-A `Person`). - `ArrayList<Person> list = new ArrayList<Person>(); list.add(new GradStudent());` (Valid). • Assigning Superclass to Subclass without a cast: - `Student s = new Person();` $\rightarrow$ COMPILE-TIME ERROR (a `Person` is not necessarily a `Student`). • Explicit Downcasting (`(SubClass) ref`): - If `Person p = new GradStudent();`, then `Student s = (Student) p;` compiles AND succeeds at run time. - If `Person p = new Person();`, then `Student s = (Student) p;` compiles, but throws a `ClassCastException` at RUN TIME!
21	How does Insertion Sort work, how do you recognize it in code, and why is its Best Case $O(n)$ while its Worst Case is $O(n^2)$?	• Mechanism: Starts at index `i = 1` (treating `arr[0]` as a sorted subarray of size 1). In pass `i`, saves `temp = arr[i]` and uses an inner `while` loop (`j = i - 1`) to shift larger elements (`arr[j] > temp`) one position to the right (`arr[j + 1] = arr[j]`) until finding the correct spot to insert `temp`. • How to Recognize in Code: Outer loop starts at `i = 1`; inner `while (j >= 0 && arr[j] > temp)` shifts elements right; `arr[j + 1] = temp;`. • Performance: - Best Case (Already Sorted Ascending): Inner `while` condition `arr[j] > temp` is immediately `false` on every pass $\implies$ only $n - 1$ comparisons and $0$ shifts ($O(n)$)! - Worst Case (Reverse Sorted Descending): Inner `while` shifts every preceding element on every pass $\implies \frac{n(n-1)}{2}$ comparisons and shifts ($O(n^2)$).
22	How do you write a complete Subclass on an AP CS A Free-Response Question (e.g., `public class LimitedCustomer extends Customer`) when the superclass has private fields and a method you need to refine?	Follow these 4 rules: 1. Header: `public class LimitedCustomer extends Customer` (do NOT redeclare the superclass's private fields!). 2. Subclass Field: Declare only the new field(s) unique to the subclass as `private`. 3. Constructor: Call `super(superParams);` on the very first line, then initialize the subclass's own private field(s). 4. Overridden Method: Write the exact same method header as the superclass, and call `super.methodName(...)` inside the body to access or extend the superclass's behavior.
23	Wait—in `SuperClass a = new SubClass();`, if `a.methodA()` (inherited from `SuperClass` and NOT overridden in `SubClass`) internally calls `methodB()` (which IS overridden in `SubClass`), WHICH version of `methodB()` runs?	`SubClass`'s overridden `methodB()` runs! This is the #1 AP CS A Inheritance MCQ trap: inside `SuperClass`'s `methodA()`, an unqualified call to `methodB()` is implicitly `this.methodB()`. Because at run time the implicit object `this` is actually an instance of `SubClass`, dynamic method dispatch invokes `SubClass.methodB()`!
24	For an 8-element array `{38, 27, 43, 3, 9, 82, 10, 19}`, what does the array look like immediately BEFORE the very final `merge` call of Merge Sort?	Immediately before the final top-level `merge` step combines the left half and right half, the first 4 elements are completely sorted and the last 4 elements are completely sorted independently: • Left half `{38, 27, 43, 3}` sorted $\rightarrow$ `{3, 27, 38, 43}` • Right half `{9, 82, 10, 19}` sorted $\rightarrow$ `{9, 10, 19, 82}` • Array just before final `merge`: `{3, 27, 38, 43, 9, 10, 19, 82}`.
25	Trace the recursive Binary Search helper method `bSearch(int[] arr, int low, int high, int target)` and count how many times `bSearch` is called (including the initial call) when searching for a value NOT in the array.	```java public static int bSearch(int[] arr, int low, int high, int target) { if (low > high) return -1; // Base case: not found int mid = (low + high) / 2; if (arr[mid] == target) return mid; else if (target < arr[mid]) return bSearch(arr, low, mid - 1, target); else return bSearch(arr, mid + 1, high, target); } ``` Watch the MCQ trap: If the question asks 'How many times is `bSearch` called?' (rather than 'How many array comparisons are made?') and `target` is NOT found, remember to count the final base-case call where `low > high` (which returns `-1` without comparing `arr[mid]`)!
26	How does Merge Sort work recursively ('Divide and Conquer'), and what is its Time Complexity across Best, Average, and Worst cases?	• Mechanism: 1. Divide: If the subarray has gt; 1$ element, split it in half at `mid = (low + high) / 2`. 2. Conquer (Recurse): Recursively call `mergeSort` on the left half `[low..mid]` and the right half `[mid+1..high]`. 3. Combine (`merge` helper): Merge the two sorted halves into a single sorted temporary array by repeatedly comparing the front elements of both halves. • Performance & Space: Always runs in $O(n \log n)$ time in ALL cases (best, average, and worst—unaffected by initial order of elements), at the cost of requiring a temporary array ($O(n)$ extra memory) during the `merge` step.
27	What are the two required components of every valid Recursive Method, and what exception is thrown if a recursive method never reaches its Base Case?	1. Base Case (Halting Case): A conditional branch (`if`) that solves the simplest input directly and returns without making another recursive call. 2. Recursive Call (General Case): Calls the same method with a modified argument that makes strict progress toward the Base Case. • If the base case is missing or unreachable (infinite recursion), the call stack runs out of memory and throws a `StackOverflowError` at run time.
28	Trace Iterative or Recursive Binary Search step-by-step on the sorted 8-element array `arr = {2, 5, 8, 12, 16, 23, 38, 56}` (indices `0` to `7`) when searching for `target = 23`.	• Iteration 1: `low = 0`, `high = 7` $\implies$ `mid = (0 + 7) / 2 = 3`. Check `arr[3] = 12`. Since `23 > 12`, eliminate left half and set `low = mid + 1 = 4`. • Iteration 2: `low = 4`, `high = 7` $\implies$ `mid = (4 + 7) / 2 = 5`. Check `arr[5] = 23`. Match found at index `5` in 2 comparisons! (Exam Tip: Always check whether the code updates `low = mid + 1` / `high = mid - 1` and trace the exact integer division `(low + high) / 2`!)
29	How does Selection Sort work, how do you recognize it in code, and how do its comparisons and swaps depend on whether the array is already sorted?	• Mechanism: In pass `i` (from `0` to `n - 2`), Selection Sort scans the unsorted suffix `i` through `n - 1` to find the index of the minimum element (`minIndex`), and then swaps `arr[i]` with `arr[minIndex]` at the end of the pass. • How to Recognize in Code: Outer loop `i` from `0` to `n - 2`; variable `minIdx = i`; inner loop `j` from `i + 1` to `n - 1` updating `if (arr[j] < arr[minIdx]) minIdx = j;`; single swap OUTSIDE the inner loop. • Performance: Always makes the exact same number of comparisons $\frac{n(n-1)}{2}$ ($O(n^2)$) and at most $n - 1$ swaps regardless of whether the array is initially sorted, reverse-sorted, or random!
30	Compare the Statement Execution Counts of Selection Sort, Insertion Sort, and Merge Sort when given (1) an Already-Sorted Array vs. (2) a Reverse-Sorted Array of size $N$.	\| Algorithm \| Already-Sorted Array \| Reverse-Sorted Array \| \| :--- \| :--- \| :--- \| \| Selection Sort \| $\approx N^2 / 2$ comparisons, $0$ (or $N-1$ self) swaps \| $\approx N^2 / 2$ comparisons, $\le N-1$ swaps \| \| Insertion Sort \| $N - 1$ comparisons, $0$ shifts (Fastest!) \| $\approx N^2 / 2$ comparisons, $\approx N^2 / 2$ shifts (Slowest!) \| \| Merge Sort \| $\approx N \log_2 N$ comparisons & copies \| $\approx N \log_2 N$ comparisons & copies \|
31	How do you trace a Recursive Method that has statements AFTER the recursive call (Unwinding the Call Stack), such as `mystery(n)` printing before vs. after the recursive call?	Consider: ```java public static void printA(int n) { if (n > 0) { System.out.print(n + " "); printA(n - 1); } } public static void printB(int n) { if (n > 0) { printB(n - 1); System.out.print(n + " "); } } ``` • `printA(3)` (Print BEFORE recursive call): Prints in forward order as calls go down the stack: `3 2 1 `. • `printB(3)` (Print AFTER recursive call): Pushes `printB(3) -> printB(2) -> printB(1) -> printB(0)` onto the call stack, then prints as the stack unwinds (LIFO): `1 2 3 `!
32	How does Polymorphism work when iterating through an `ArrayList<SuperClass>` or `SuperClass[]` array containing a mix of `SuperClass` and `SubClass` objects?	Suppose `Book` has a method `getInfo()` and `AudioBook extends Book` overrides `getInfo()`: ```java ArrayList<Book> library = new ArrayList<Book>(); library.add(new Book("Dune")); library.add(new AudioBook("Odyssey", 720)); for (Book b : library) { System.out.println(b.getInfo()); } ``` 1. Compile Time: `b` is declared as `Book`, and `Book` has `getInfo()`, so `b.getInfo()` compiles cleanly. 2. Run Time: For element `0` (a `Book`), `Book.getInfo()` runs; for element `1` (an `AudioBook`), `AudioBook.getInfo()` runs automatically via dynamic method dispatch!