AP Computer Science A · Unit 4 lecture · Part 14 of 14 · 12 min

Unit 4 wrap-upPut it together

Mr. Thompkins
That was a long unit, and you made it. Let's line up the three collections side by side, collect the traps in one place, and then do one Data Analysis FRQ the way it's graded.
arrayArrayList2D array
createnew int[5]new ArrayList<Integer>()new int[3][4]
sizea.lengthlist.size()g.length rows, g[0].length cols
reada[i]list.get(i)g[r][c]
changea[i] = v;list.set(i, v);g[r][c] = v;
grow or shrinknever: fixed sizeadd, add(i, x), remove(i)never: fixed size
holdsprimitives or referencesreferences only (Integer)primitives or references
out of rangeArrayIndexOutOfBoundsIndexOutOfBoundsArrayIndexOutOfBounds
Arrays, ArrayLists and 2D arrays on one page.

Four threads tie the unit together. First, indexes start at 0 and stop at length - 1 or size() - 1, and every off-by-one error lives at those edges. Second, collections hold references: arrays, rows and list elements can all be aliases, and an enhanced for variable is always a copy. Third, the same handful of algorithms (sum, count, max, any and all, neighbors, search, sort) appear in every collection, with only the syntax changing. Fourth, the data itself matters: where it came from, what's missing, and who it describes.

?Wait, which algorithms need sorted data?
Only binary search. Linear search works on anything. Selection, insertion and merge sort are how you get sorted data in the first place.
Pause and think
Connect two sections: why does removing from an ArrayList in a forward loop cause a bug, but replacing elements with set in a forward loop doesn't?
I thought about it. Show me
remove shifts every later element one index left, so the element after the removed one lands at index i, which the loop has already passed. set replaces one element and nothing moves, so every index still holds the element the loop expects.

The two data FRQs

Two of the four FRQs come from this unit. Question 3, Data Analysis with ArrayList (5 points), usually gives you a class, a list of its objects, and a method to write that traverses the list, tests each object with its methods, and computes, adds or removes something. Question 4, 2D Array (6 points), gives you a 2D array, usually inside a class, and asks you to traverse it to compute or find something. Both reward clean loops, correct bounds and a return in the right place.

Data Analysis with ArrayList
A Reading object has getTitle(), which returns a String, and getPages(), which returns an int. Write the static method removeShort(ArrayList<Reading> log, int minPages), which removes every Reading with fewer than minPages pages from log and returns the total number of pages of the Readings it removed. For a log of Dune (412), Frog Poems (38), Atlas (96) and Haiku Now (24) with minPages 100, it returns 158 and leaves only Dune.
1public static int removeShort(ArrayList<Reading> log,2                              int minPages)3{4    int pagesRemoved = 0;5    for (int i = log.size() - 1; i >= 0; i--)16    {7        Reading r = log.get(i);28        if (r.getPages() < minPages)29        {10            pagesRemoved += r.getPages();311            log.remove(i);412        }13    }14    return pagesRemoved;515}
  1. line 5 Point 1: traverse every element, backward
  2. line 7-8 Point 2: get each Reading and call its method
  3. line 10 Point 3: add up the pages before removing
  4. line 11 Point 4: remove without skipping anything
  5. line 14 Point 5: return the total, after the loop
output › log [Dune 412, Frog Poems 38, Atlas 96, Haiku Now 24], minPages 100: returns 158, and only Dune is left
  1. It removes from a list, so traverse backward: for (int i = log.size() - 1; i >= 0; i--).
    Why?
    This earns the traversal point and protects the "no skipping" point at the same time.
  2. Get each object once and store it: Reading r = log.get(i);
  3. Test it with its method: if (r.getPages() < minPages).
    Why?
    Strictly fewer than minPages. A book with exactly minPages stays.
  4. Inside the if, add its pages to a total declared before the loop, then remove it: pagesRemoved += r.getPages(); log.remove(i);
    Why?
    Add before or after the remove both work here, because r still refers to the object. What matters is that you saved it in r first.
  5. After the loop, return pagesRemoved;. Check: 24 + 96 + 38 = 158, and only Dune is left.

Answer: Traverse backward, store each Reading, and for each one under minPages, add its pages and remove it; return the total after the loop. For the example: 158.

Stuck? Get a hint
  1. Which direction is safe when you remove?
  2. The total has to exist before the loop and be returned after it.
  3. Call getPages() on each Reading to decide.

Traps that cost points

✕ Using arr[arr.length] or i <= arr.length.
✓ The last index is length - 1. Loop with i < arr.length.
✕ Writing arr.length(), list.length or list.size.
✓ Arrays: length. ArrayLists: size(). Strings: length().
✕ Starting a max or min at 0.
✓ Start at the first element, or at Integer.MIN_VALUE / MAX_VALUE.
✕ Dividing two ints for an average.
✓ Cast first: (double) sum / count.
✕ Assigning to the enhanced for variable to change the array.
✓ It's a copy. Use an index loop: arr[i] = ...;
✕ Removing in a forward loop with i++ every time.
✓ Loop backward, or do i++ only when you keep the element.
✕ Adding or removing inside an enhanced for over the same list.
✓ That throws ConcurrentModificationException. Use an index loop.
✕ Reading list.remove(1) on an ArrayList<Integer> as "remove the value 1".
✓ It removes the element at index 1.
✕ Writing ArrayList<int>.
✓ ArrayList<Integer>.
✕ Swapping rows and columns: g.length as the column bound, or g[c][r].
✓ g.length is rows, g[0].length is columns, and access is always g[r][c].
✕ Putting return -1 (or return false) inside the loop.
✓ "Not found" goes after the loop, once everything was checked.
✕ Running binary search on unsorted data.
✓ Binary search needs sorted data. Otherwise use linear search.
✕ Forgetting throws IOException when opening a File.
✓ The method header must declare it.
✕ Printing too early when tracing recursion.
✓ Code after the recursive call runs only as each call returns.

Unit 4 code patterns

int[] a = new int[n]; int[] b = {3, 1, 4};
Create an arrayDefaults 0, 0.0, false, null
for (int i = 0; i < a.length; i++)
Array traversalIndexes 0 to length - 1
for (int v : a)
Enhanced forv is a copy of each value
int t = a[i]; a[i] = a[j]; a[j] = t;
SwapReverse and selection sort
ArrayList<Integer> L = new ArrayList<Integer>();
Create an ArrayListimport java.util.ArrayList
for (int i = L.size() - 1; i >= 0; i--)
Backward traversalSafe for removing
int[][] g = new int[rows][cols];
Create a 2D arrayg.length rows, g[0].length columns
for (int[] row : g) for (int v : row)
2D enhanced forRow-major order
Scanner in = new Scanner(new File("f.txt"));
Open a text fileHeader needs throws IOException
String[] parts = line.split(",");
Split a lineThen Integer.parseInt(parts[1])
int mid = (low + high) / 2;
Binary search middleSorted data only

FRQ strategy for the ArrayList and 2D Array questions

  1. Read the method header and the example first. Know what you return before you write a loop.
  2. Pick the loop on purpose: backward or index-based if you remove; nested r and c loops for 2D; enhanced for only to read.
  3. Write the bounds carefully: size() for lists, length for arrays, g.length for rows and g[0].length (or g[r].length) for columns.
  4. Use the methods the problem gives you on each object, like getPages(). Never reach for private instance variables of another class.
  5. Put each reset, counter and flag in the right place: before all loops for the whole collection, inside the outer loop for per-row values.
  6. Return after the loops, unless you're returning early because you found the answer.
  7. Trace your code on the problem's own example before you move on.
Check yourself
What is printed?
int[][] g = { {5, 0, 3}, {0, 0, 7} };
ArrayList<Integer> keep = new ArrayList<Integer>();
for (int[] row : g)
{
    for (int v : row)
    {
        if (v != 0)
        {
            keep.add(0, v);
        }
    }
}
System.out.println(keep);
  1. A[7, 3, 5]
  2. B[5, 3, 7]
  3. C[7, 0, 0, 3, 0, 5]
  4. D[3, 5, 7]
Show the answer

A. The loops visit 5, 0, 3, 0, 0, 7 in row-major order and keep only the nonzero values. Each one is inserted at index 0, in front of the others: [5], then [3, 5], then [7, 3, 5]. The second choice is the trap: add(v) at the end would give [5, 3, 7], but add(0, v) reverses the order.

Check yourself
A sorted array holds 1,000 student ID numbers. In the worst case, about how many elements does binary search check?
  1. A10
  2. B500
  3. C1,000
  4. D32
Show the answer

A. Each check halves the range: 1,000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1, about 10 checks. 1,000 is the worst case for linear search, which is the trap; 500 is linear search's average, not binary search's.

Mr. Thompkins
That's Unit 4, and with it the whole course content. Go take the Unit 4 quiz, then do one ArrayList FRQ and one 2D Array FRQ from the practice set with a timer. When a question trips you, come back to its section and open the recall cards. You've got this.