Unit 4 wrap-upPut it together

| array | ArrayList | 2D array | |
|---|---|---|---|
| create | new int[5] | new ArrayList<Integer>() | new int[3][4] |
| size | a.length | list.size() | g.length rows, g[0].length cols |
| read | a[i] | list.get(i) | g[r][c] |
| change | a[i] = v; | list.set(i, v); | g[r][c] = v; |
| grow or shrink | never: fixed size | add, add(i, x), remove(i) | never: fixed size |
| holds | primitives or references | references only (Integer) | primitives or references |
| out of range | ArrayIndexOutOfBounds | IndexOutOfBounds | ArrayIndexOutOfBounds |
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?
I thought about it. Show me
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.
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}
- line 5 Point 1: traverse every element, backward
- line 7-8 Point 2: get each Reading and call its method
- line 10 Point 3: add up the pages before removing
- line 11 Point 4: remove without skipping anything
- line 14 Point 5: return the total, after the loop
- 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. - Get each object once and store it: Reading r = log.get(i);
- Test it with its method: if (r.getPages() < minPages).
Why?
Strictly fewer than minPages. A book with exactly minPages stays. - 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. - 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
- Which direction is safe when you remove?
- The total has to exist before the loop and be returned after it.
- Call getPages() on each Reading to decide.
Traps that cost points
Unit 4 code patterns
int[] a = new int[n]; int[] b = {3, 1, 4};for (int i = 0; i < a.length; i++)for (int v : a)int t = a[i]; a[i] = a[j]; a[j] = t;ArrayList<Integer> L = new ArrayList<Integer>();for (int i = L.size() - 1; i >= 0; i--)int[][] g = new int[rows][cols];for (int[] row : g) for (int v : row)Scanner in = new Scanner(new File("f.txt"));String[] parts = line.split(",");int mid = (low + high) / 2;FRQ strategy for the ArrayList and 2D Array questions
- Read the method header and the example first. Know what you return before you write a loop.
- Pick the loop on purpose: backward or index-based if you remove; nested r and c loops for 2D; enhanced for only to read.
- Write the bounds carefully: size() for lists, length for arrays, g.length for rows and g[0].length (or g[r].length) for columns.
- Use the methods the problem gives you on each object, like getPages(). Never reach for private instance variables of another class.
- 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.
- Return after the loops, unless you're returning early because you found the answer.
- Trace your code on the problem's own example before you move on.
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);- A[7, 3, 5]
- B[5, 3, 7]
- C[7, 0, 0, 3, 0, 5]
- 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.
- A10
- B500
- C1,000
- 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.
