AP Computer Science A · Unit 4 · 30-40% of the exam · about 140 minutes

Unit 4: Data Collections

By the end: Store, traverse and change data in arrays, ArrayLists and 2D arrays, read data from text files, run and trace the standard algorithms (linear and binary search, selection, insertion and merge sort), trace recursion, and think about where data comes from and who it leaves out.

Mr. Thompkins
  1. 4.1-4.2 Data: ethics, bias and using data sets · 8 min

    Before the code: where data comes from

    • A data set is a collection of related data, often rows (records) and columns (fields). Programs use it to answer questions and find patterns.
    • Check data before trusting it: errors and missing values must be handled, never counted as real values.
    • Personal data carries privacy risks. Collect only what you need, protect it, and remove what identifies people.
  2. 4.3 Array creation and access · 8 min

    Arrays: many values, one name

    • new type[n] makes n elements with defaults (0, 0.0, false, null). An initializer list sets the values and the length.
    • Indexes run from 0 to length - 1. length is a field: no parentheses.
    • An index outside that range throws ArrayIndexOutOfBoundsException when the code runs.
  3. 4.4 Array traversals · 8 min

    Traversals: visit every element

    • Standard traversal: for (int i = 0; i < arr.length; i++).
    • Change the start, the step or the stop to visit only part of the array, or go backward from length - 1.
    • The enhanced for variable is a copy: assigning to it never changes the array.
  4. 4.5 Implementing array algorithms · 12 min

    The array algorithm toolbox

    • Average: sum, then cast before dividing. Min and max: start at arr[0] (or Integer.MIN_VALUE / MAX_VALUE), never 0.
    • Any: return true when found, false after the loop. All: return false when one fails, true after the loop.
    • Neighbors: compare a[i] with a[i + 1] and stop at length - 1. Duplicates: nested loop with j starting at i + 1.
  5. 4.6 Using text files · 9 min

    Reading data from a text file

    • new Scanner(new File("name.txt")) opens a file. Import java.io.File, java.io.IOException and java.util.Scanner.
    • A method that opens a file needs throws IOException in its header.
    • while (in.hasNext()) reads until the input runs out. Close the Scanner at the end.
  6. 4.7 Wrapper classes · 5 min

    Integer and Double: numbers as objects

    • Integer wraps an int; Double wraps a double. Both are immutable.
    • Autoboxing (int to Integer) and unboxing (Integer to int) happen automatically.
    • Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.parseInt and Double.parseDouble are on the Quick Reference.
  7. 4.8 ArrayList methods · 9 min

    ArrayList: a list that grows

    • ArrayList<E> holds object references and changes size. import java.util.ArrayList;
    • size(), add(obj), add(index, obj), get(index), set(index, obj), remove(index): know what each returns.
    • add(index, obj) shifts later elements right; remove(index) shifts them left.
  8. 4.9-4.10 ArrayList traversals and algorithms · 11 min

    Looping through a list that changes

    • Traverse with for (int i = 0; i < list.size(); i++) and list.get(i), or an enhanced for to read.
    • A removal shifts later elements left. Traverse backward, or only do i++ when you keep the element.
    • Never change a list's size inside an enhanced for over that list: ConcurrentModificationException.
  9. 4.11-4.12 2D array creation, access and traversals · 10 min

    2D arrays: rows and columns

    • new int[rows][cols]; an initializer list is a list of rows. Access with g[row][col].
    • g.length is the number of rows; g[0].length is the number of columns.
    • A 2D array is an array of rows: g[r] is a whole 1D array.
  10. 4.13 Implementing 2D array algorithms · 9 min

    2D algorithms: rows, columns and neighbors

    • Per-row work: reset inside the outer loop. One column: fix c, move r. Whole grid: one variable outside both loops.
    • Check the edges before reading a neighbor: r > 0, r < g.length - 1, c > 0, c < g[0].length - 1.
    • Rows are references: you can swap or pass whole rows.
  11. 4.14-4.15 Searching and sorting · 12 min

    Linear search, selection sort and insertion sort

    • Linear search: check each element in order; return the index, or -1 after the loop. Works on unsorted data.
    • Selection sort: each pass swaps the smallest remaining value into place. The front is final after each pass.
    • Insertion sort: each pass slides the next value left into the sorted part. The front is sorted but can still change.
  12. 4.16 Recursion · 10 min

    Recursion: a method that calls itself

    • A recursive method calls itself. It needs a base case, and each call must move toward it.
    • Each call has its own parameters and local variables. Paused calls finish in reverse order.
    • Code before the recursive call runs on the way down; code after it runs on the way back up.
  13. 4.17 Recursive searching and sorting · 11 min

    Binary search and merge sort

    • Binary search needs sorted data. Check the middle, discard half, repeat until found or low > high.
    • Binary search takes about log2(n) steps: 10 for 1,000 elements, 20 for a million.
    • Merge sort: split in half, sort each half recursively, merge. One element is the base case.
  14. Unit 4 wrap-up · 12 min

    Put it together