AP Computer Science A

Lesson 1.1 · Unit 1 · CED topic 1.1

Algorithms, programs, and how Java runs

An algorithm is a finite list of steps that solves a problem. Every algorithm you write this year is built from three kinds of step: sequence (do this, then that), selection (do this only if something is true), and iteration (do this again while something is true). That is the whole toolkit. A program is an algorithm written in a language a machine will accept.

Java takes a detour on its way to the machine. You write source code in a .java file; the compiler (javac) translates it into bytecode in a .class file; the Java Virtual Machine (java) executes that bytecode. That detour gives Java two very different kinds of failure. A compile-time error is caught by javac, so the program never runs at all; a run-time error gets past the compiler and blows up mid-execution, with output already on the screen.

public class Main {
    public static void main(String[] args) {
        // statements run in order, top to bottom
    }
}

public class Main {
    public static void main(String[] args) {
        double celsius = 21.5;
        double fahrenheit = celsius * 9.0 / 5.0 + 32.0;
        System.out.println(celsius + " C is " + fahrenheit + " F");
    }
}

21.5 C is 70.7 F

Main.java:3: error: ';' expected
        double celsius = 21.5
                             ^
1 error

public class Main {
    public static void main(String[] args) {
        int totalPages = 250;
        int pagesPerDay = 0
        System.out.println(totalPages / pagesPerDay);
    }
}

Main.java:4: error: ';' expected
        int pagesPerDay = 0
                           ^
1 error

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at Main.main(Main.java:5)

Lesson 1.2 · Unit 1 · CED topic 1.2

Variables and data types

A variable is a named box in memory, and in Java every box is stamped with a type before anything goes in it. That stamp is permanent: a box declared int holds whole numbers for the rest of its life. The compiler enforces the stamp, which is why so many Java bugs are caught before the program ever runs.

Four types carry almost all of Unit 1. Three are primitive (int for whole numbers, double for numbers with a decimal part, boolean for true/false), and they store the value itself. String is a reference type: the box holds a reference to a text object living elsewhere. So 7 and 7.0 are not the same value. They print differently, they divide differently, and they have different types.

int    quantity  = 3;          // whole number
double unitPrice = 12.50;      // number with a fractional part
boolean taxExempt = false;     // exactly true or false
String itemName  = "Lab notebook";   // text, in double quotes

String itemName = "Lab notebook";
int quantity = 3;
double unitPrice = 12.50;
boolean taxExempt = false;

double subtotal = quantity * unitPrice;
System.out.println("Item:      " + itemName);
System.out.println("Quantity:  " + quantity);
System.out.println("Unit price " + unitPrice);
System.out.println("Subtotal:  " + subtotal);
System.out.println("Exempt:    " + taxExempt);

Item:      Lab notebook
Quantity:  3
Unit price 12.5
Subtotal:  37.5
Exempt:    false

points = points + 3;
average = average * points;
label = label + points;
points = 10;
label = label + " " + average;

int seats = 4;
double price = 15.75;
boolean sold = "false";
String row = C;

Main.java:5: error: incompatible types: String cannot be converted to boolean
        boolean sold = "false";
                       ^
Main.java:6: error: cannot find symbol
        String row = C;
                     ^
  symbol:   variable C
  location: class Main
2 errors

Lesson 1.3 · Unit 1 · CED topic 1.3

Expressions and output

An expression is anything that evaluates to a single value. Java gives you five arithmetic operators (+, -, *, / and %), and the two that cause trouble are the last two. When both operands of / are int, Java does integer division: it throws the fractional part away rather than rounding, so 7 / 2 is 3 and 1 / 2 is 0. The modulus operator % hands you what was thrown away: the remainder.

That pair is not a nuisance; it is a tool. / and % together split any quantity into a whole part and a leftover, which is exactly what making change, splitting seconds into minutes, or peeling digits off a number requires.

int whole     = total / size;    // int / int  -> int, truncated
int leftover  = total % size;    // the remainder
double exact  = total / 2.0;     // one double  -> the whole result is double

int cents = 287;

int dollars  = cents / 100;
int rest     = cents % 100;
int quarters = rest / 25;
rest         = rest % 25;
int dimes    = rest / 10;
rest         = rest % 10;
int nickels  = rest / 5;
int pennies  = rest % 5;

2 dollars
3 quarters
1 dimes
0 nickels
2 pennies

int hours   = totalSeconds / 3600;
int minutes = totalSeconds % 3600 / 60;
int seconds = totalSeconds % 60;

1:2:5

Lesson 1.4 · Unit 1 · CED topic 1.4

Assignment and keyboard input

In algebra, x = x + 3 is a false statement. In Java it is a perfectly ordinary instruction: evaluate the right side, then store the result in the box on the left. The = sign is not a claim about equality, it is a command, and it always runs right to left. That single rule explains most of what confuses people about reassignment.

It also explains why you cannot swap two variables by copying one into the other. The first assignment overwrites the value you still needed, and it is gone: there is no undo. You need a third box to hold it. Input works the same way: a Scanner pulls the next token the user typed and you assign it somewhere.

int temp = a;    // save what a holds
a = b;           // a now holds b's value
b = temp;        // b gets the saved value

import java.util.Scanner;               // at the top of the file
Scanner in = new Scanner(System.in);    // once, before any reading
int    n = in.nextInt();                // next whole number
double d = in.nextDouble();             // next decimal number
String s = in.nextLine();               // rest of the current line

Scanner in = new Scanner(System.in);

System.out.println("Bill total?");
double bill = in.nextDouble();
System.out.println("Party size?");
int people = in.nextInt();

double withTip = bill * 1.18;
double share = withTip / people;
double rounded = (int) (share * 100 + 0.5) / 100.0;

System.out.println("With 18% tip: " + withTip);
System.out.println("Each person pays: " + rounded);

Bill total?
Party size?
With 18% tip: 101.952
Each person pays: 25.49

Scanner in = new Scanner(System.in);
int age = in.nextInt();
String name = in.nextLine();
System.out.println("age=[" + age + "] name=[" + name + "]");

int age = in.nextInt();
in.nextLine();                  // throw away the rest of the number's line
String name = in.nextLine();

age=[16] name=[Maya Chen]

Lesson 1.5 · Unit 1 · CED topic 1.5

Casting and the range of a variable

Java will move a value into a roomier type on its own. Assign an int to a double and it widens quietly, because nothing can be lost. Going the other way loses information, so Java refuses unless you say, in writing, that you accept the loss. That written permission is a cast.

The two things students get wrong are what a cast does and where it goes. A cast to int truncates toward zero: it chops the fractional part off, it never rounds, and (int)(-7.9) is −7, not −8. And a cast binds tightly to the value on its immediate right, so putting it one step too late means the damage is already done.

double d = 5;            // widening: d is 5.0, no cast needed
int    n = (int) 5.9;    // narrowing: n is 5, the .9 is discarded

double avg = (double) sum / count;   // cast sum first, then divide  -> correct
double bad = (double) (sum / count); // divide as ints, then widen   -> too late

int rounded = (int) (x + 0.5);              // round half up (x >= 0)
double cents = (int) (x * 100 + 0.5) / 100.0;  // round to two decimals

int sum = 413;
int count = 5;
double average = sum / count;            // prints 82.0
double fixed1  = (double) sum / count;   // prints 82.6
double fixed2  = (double) (sum / count); // prints 82.0

no cast:     82.0
cast sum:    82.6
cast result: 82.0

int correct = 17;
int items = 24;
double pct = correct / items * 100;

double pct = (double) correct / items * 100;
double toCents = (int) (pct * 100 + 0.5) / 100.0;

broken: 0.0
fixed:  70.83333333333334
to cents: 70.83

Lesson 1.6 · Unit 1 · CED topic 1.6

Compound assignment and increment operators

Updating a variable from its own value is so common that Java gives it shorthand. price = price * 0.9; becomes price *= 0.9;, and count = count + 1; becomes count++;. The shorthand is not only shorter: it names the variable once, so you cannot accidentally update the wrong one.

There is a catch worth knowing before it bites you. A compound assignment carries a hidden cast back to the variable's own type. m = m + 2.7; on an int is a compile-time error, but m += 2.7; compiles happily and silently truncates. The shorthand is not just shorter; on an int it is quietly more permissive.

x += 5;     // x = x + 5;
x -= 5;     // x = x - 5;
x *= 5;     // x = x * 5;
x /= 5;     // x = x / 5;   (int / int still truncates)
x %= 5;     // x = x % 5;

count++;    // count = count + 1;   on a line of its own
count--;    // count = count - 1;

double price = 24.00;
price *= 0.9;      // ten percent off
price += 1.50;     // flat fee

int stock = 12;
stock--;
stock++;
stock++;

list price   24.0
after 10% off 21.6
after fee     23.1
stock 11
stock 13

int m = 9;
m += 2.7;
m /= 4;
m *= 3;

start  m=9
+= 2.7 m=11
/= 4   m=2
*= 3   m=6

Main.java:4: error: incompatible types: possible lossy conversion from double to int
        m = m + 2.7;
              ^
1 error

Lesson 1.7 · Unit 1 · CED topics 1.7–1.8

Using the Java API and documenting code

Almost nothing you need is written from scratch. A library is code somebody else wrote and tested; a package is a named folder of such classes; an import tells the compiler which package to look in. java.lang (home of Math, String and System) is imported for you. Scanner lives in java.util, so it needs one.

On the exam you will meet methods you have never seen, described by a short API entry, and you are expected to call them correctly anyway. An entry gives you four things: the header (return type, name, parameter types in order), what each parameter means, what the return value is, and a sentence of description. Everything you need to write the call is in the header.

// API entry:  public static int max(int a, int b)
//   Returns the greater of a and b.
int best = Math.max(18, 23);          // best is 23

// API entry:  public String substring(int from, int to)
//   Returns the substring from index from, up to but NOT including to.
String part = "Programming".substring(0, 3);   // "Pro"

/**
 * Returns the larger of two quiz scores.
 * Precondition: both scores are at least 0.
 */
public static int betterScore(int a, int b) {
    return Math.max(a, b);
}

System.out.println("apple".compareTo("banana"));
System.out.println("banana".compareTo("apple"));
System.out.println("apple".compareTo("apple"));

-1
1
0

int second = word.indexOf("o", 2);

word.indexOf("o")      ->  1
word.indexOf("o", 2)   ->  3
word.indexOf("o", 4)   ->  6

Lesson 1.8 · Unit 1 · CED topics 1.9–1.10

Method signatures and calling class methods

A method header is a contract written in five parts, and the compiler enforces every one of them. Read public static double milesToKm(double miles) from the left: public says anyone may call it, static says it belongs to the class rather than to an object, double is what it hands back, milesToKm is its name, and (double miles) is the one value it demands.

Arguments are matched to parameters by position and type, never by name. The variable you pass can be called anything; what matters is that the first argument fits the first parameter's type, the second fits the second, and there are exactly as many arguments as parameters. A void method returns nothing, so its call is a statement on its own line and cannot appear inside an expression.

public class Converter {
    public static double milesToKm(double miles) {
        return miles * 1.609344;
    }

    public static String formatLabel(String name, int count) {
        return name + " (" + count + ")";
    }
}

// from main, in another class:
double km = Converter.milesToKm(5.0);
System.out.println(Converter.formatLabel("Ridge Trail", 3));

public static double roundTo(double value, int places) {
    double factor = Math.pow(10, places);
    return (int) (value * factor + 0.5) / factor;
}

8.04672
8.05
Ridge Trail (3)
41.842944
41.8

Main.java:3: error: incompatible types: String cannot be converted to double
        Converter.milesToKm("5");
Main.java:4: error: incompatible types: possible lossy conversion from double to int
        int k = Converter.milesToKm(5.0);
Main.java:5: error: incompatible types: int cannot be converted to String
        Converter.formatLabel(3, "Ridge Trail");
Main.java:6: error: cannot find symbol
        converter.milesToKm(5.0);
  symbol:   variable converter

System.out.println(Converter.formatLabel("Ridge Trail", 3));
System.out.println(Converter.formatLabel("Ridge Trail"));
System.out.println(Converter.formatLabel(Converter.formatLabel("Loop"), 2));

public static String formatLabel(String name) {
    return "[" + name + "]";
}

Ridge Trail (3)
[Ridge Trail]
[Loop] (2)

Lesson 1.9 · Unit 1 · CED topic 1.11

The Math class

Math is a class of static methods, so you never build a Math object: you call everything through the class name. The AP subset contains exactly four of its methods, and knowing that list is worth a question or two on the exam: Math.abs, Math.pow, Math.sqrt and Math.random. Anything else on a released question will be handed to you with its API entry.

Return types matter more here than anywhere else so far. Math.pow and Math.sqrt always return a double, even for a perfect square, so Math.sqrt(16) prints 4.0 and cannot be stored in an int without a cast. Math.abs is overloaded: pass it an int and you get an int back.

Math.abs(x)        // absolute value; int in -> int out, double in -> double out
Math.pow(b, e)     // b raised to the power e; always a double
Math.sqrt(x)       // square root; always a double
Math.random()      // a double r with 0.0 <= r < 1.0  (1.0 is never produced)

// a random integer from min through max, both included:
int n = (int) (Math.random() * (max - min + 1)) + min;

double dist = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));

int die1 = (int) (Math.random() * 6) + 1;
int die2 = (int) (Math.random() * 6) + 1;

7
7.5
1024.0
4.0
1.4142135623730951
distance = 10.0
roll: 4 + 3 = 7

int n = (int) (Math.random() * 11) * 2 + 10;

Lesson 1.10 · Unit 1 · CED topics 1.12–1.13

Objects, classes, and object creation

A class is a blueprint; an object is one thing built from it. The Rectangle class says every rectangle has a width and a height and can report its area. new Rectangle(3.0, 4.0) builds one actual rectangle in memory and runs the constructor, whose job is to give the new object its starting state.

Here is the part that trips people up. A variable of a class type does not contain the object. It contains a reference: the object's address. So b = a; copies an address, not a rectangle, and you end up with two names for one object. Change it through either name and both names see the change. That is aliasing, and the exam tests it constantly.

Rectangle a = new Rectangle(3.0, 4.0);
//  type    name        constructor call with arguments

Rectangle b = a;     // b now refers to the SAME object as a
Rectangle c = null;  // c refers to no object at all

Rectangle a = new Rectangle(3.0, 4.0);
Rectangle b = new Rectangle(5.0, 2.0);
System.out.println("a area " + a.getArea() + ",  b area " + b.getArea());

b = a;
System.out.println("after b = a:  a area " + a.getArea() + ",  b area " + b.getArea());

b.setWidth(10.0);
System.out.println("after b.setWidth(10.0):  a area " + a.getArea() + ",  b area " + b.getArea());
System.out.println("a width " + a.getWidth() + ",  b width " + b.getWidth());

a area 12.0,  b area 10.0
after b = a:  a area 12.0,  b area 12.0
after b.setWidth(10.0):  a area 40.0,  b area 40.0
a width 10.0,  b width 10.0

Rectangle c = null;
System.out.println("about to ask a null for its area");
System.out.println(c.getArea());

about to ask a null for its area
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "Rectangle.getArea()" because "c" is null
    at Main.main(Main.java:5)

Lesson 1.11 · Unit 1 · CED topic 1.14

Calling instance methods

An instance method belongs to an object, not to a class, so it needs an object to work on. You supply one with the dot operator: acct.deposit(75.50) means "run deposit on the object acct refers to". A static method like Math.sqrt needs no object, which is exactly why you write the class name in front of it instead.

The other thing to read off a header is whether the call produces a value. deposit is void: it changes the object and hands nothing back, so the call is a complete statement and can never appear inside a larger expression. getBalance returns a double, so its call is a value and can be printed, stored, or used in arithmetic.

public class BankAccount {
    private double balance;
    public BankAccount(double startingBalance) { balance = startingBalance; }
    public void   deposit(double amount)  { balance = balance + amount; }
    public void   withdraw(double amount) { balance = balance - amount; }
    public double getBalance()            { return balance; }
}

BankAccount acct = new BankAccount(250.00);
acct.deposit(75.50);                      // void: a statement on its own
double twice = acct.getBalance() * 2;     // returns a value: usable in an expression

BankAccount acct = new BankAccount(250.00);
acct.deposit(75.50);
acct.withdraw(40.00);
acct.deposit(14.50);
acct.withdraw(100.25);
double doubled = acct.getBalance() * 2;

start          250.0
deposit 75.50  325.5
withdraw 40.00 285.5
deposit 14.50  300.0
withdraw 100.25 199.75
twice the balance is 399.5

acct.deposit(100.00);
acct.withdraw(25.50);
acct.deposit(20.00);
acct.withdraw(21.75);

180.0
154.5
174.5
152.75

Main.java:4: error: 'void' type not allowed here
        System.out.println(acct.deposit(10.00));
                                       ^
Main.java:5: error: non-static method getBalance() cannot be referenced from a static context
        BankAccount.getBalance();
2 errors

Lesson 1.12 · Unit 1 · CED topic 1.15

String manipulation

A String is an object, and it is immutable: once built, its characters never change. Every String method therefore returns a new String and leaves the original alone. That single fact explains the most common beginner bug in this unit: calling a method and throwing the result away, then wondering why nothing happened.

Indexes run from 0 to length() - 1, and substring(from, to) includes from but stops before to. The AP subset has no charAt, so a single character is s.substring(i, i + 1): a one-character String, compared with equals, never with ==.

s.length()              // number of characters
s.substring(from)       // from that index to the end
s.substring(from, to)   // from that index up to but NOT including to
s.indexOf(str)          // index of the first occurrence, or -1 if absent
s.equals(other)         // true when the characters match
s.compareTo(other)      // negative / zero / positive, alphabetical order
s + t                   // concatenation builds a brand-new String

String full = "Maya Chen";
int space = full.indexOf(" ");
String first = full.substring(0, 1);
String last  = full.substring(space + 1, space + 2);
System.out.println(first + "." + last + ".");

space at index 4
M.C.

String s = "cat";
s.substring(1);            // result discarded
System.out.println(s);     // cat

String a = "hello";
String b = "hello";
String c = new String("hello");
System.out.println(a == b);        // true
System.out.println(a == c);        // false
System.out.println(a.equals(c));   // true

int at = email.indexOf("@");
String user = email.substring(0, at);
String host = email.substring(at + 1);

at index 9
user: chen.maya
host: ascend.org

Unit 1 review · 10 multiple-choice

Unit 1 review: using objects and methods

Ten exam-style multiple-choice questions running in lesson order from how Java compiles and runs through expressions, casting, method signatures, the Math class, objects and Strings: every output below came from actually compiling and running the code, so click an option and read why it is right or wrong.

Multiple choice

1. public class Main {
       public static void main(String[] args) {
           int count = 5;
           double rate = 0.5;
           int total = count * rate;
           System.out.println(total);
       }
   }

   Which of the following best describes the result of attempting to compile and run the program?

   The program compiles and prints 2 The program compiles and prints 2.5 The program does not compile, because a double value cannot be stored in an int variable without a cast The program compiles but throws a run-time exception when the assignment executes

   Java truncates only when you ask it to with a cast. Nothing here says (int), so the compiler refuses the assignment rather than quietly throwing away the 0.5, and no line of the program ever runs.

   2.5 is the correct arithmetic value of count * rate, but the variable it is being stored in is declared int. A value's type and a variable's type must be compatible before the program can be built at all.

   Correct. One int times one double promotes to double, and a double will not fit in an int slot. javac reports it at line 5: incompatible types: possible lossy conversion from double to int. Writing int total = (int) (count * rate); compiles and prints 2.

   A run-time exception happens while the program is executing, which requires the program to have compiled first. This error is caught by the compiler, so there is no class file to run and no exception to throw.

2. int cents = 287;
   System.out.println(cents / 100 + " dollars and " + cents % 100 + " cents");

   What is printed as a result of executing the code segment?

   2 dollars and 87 cents 2.87 dollars and 87 cents 2 dollars and 8 cents 287 dollars and 287 cents

   Correct. Both operands of / are int, so 287 / 100 is 2 with the remainder discarded, and 287 % 100 is that discarded remainder, 87. The two operators are a matched pair: one gives the whole part, the other gives what is left over.

   This is what you would get if / behaved like a calculator. Integer division never produces a fractional part; to see 2.87 you would have to write cents / 100.0 so that one operand is a double.

   8 is the first digit of the remainder, not the remainder. % returns everything left after the last whole 100 is removed, 287 minus 200, which is 87, not 8.

   Neither operator leaves cents alone. This answer treats + as pure concatenation everywhere, but cents / 100 and cents % 100 are arithmetic expressions that are evaluated before anything is joined to a string.

3. int x = 4;
   int y = 9;
   x = y;
   y = x;

   What are the values of x and y after the code segment executes?

   x is 9 and y is 4 x is 9 and y is 9 x is 4 and y is 9 x is 4 and y is 4

   This is the swap the code was probably meant to perform, but it is not what happens. The decisive line is y = x;: by the time it runs, x already holds 9, so 9 is what gets copied back into y.

   Correct. Assignment copies a value at the moment it executes; it does not record a relationship. Line 3 overwrites the 4 in x, and that 4 is gone forever, so line 4 copies 9 into y. A real swap needs a third variable: int temp = x; x = y; y = temp;.

   These are the starting values, which would be right only if both assignments did nothing. Each = is a command to store, so both variables are written to.

   4 is the value x loses on line 3, and nothing ever puts it back. For y to end at 4, the original x would have to have been saved somewhere before line 3 overwrote it.

4. double score = 82.6;
   int rounded = (int) (score + 0.5);
   int truncated = (int) score;
   System.out.println(rounded + " " + truncated);

   What is printed as a result of executing the code segment?

   83 83 82 82 83 82 82.6 82

   Only the first cast rounds, and it rounds because of the + 0.5 written inside the parentheses, not because casting rounds. Line 3 has no + 0.5, so it cannot produce 83.

   This assumes both lines truncate identically, but the parentheses on line 2 change what gets truncated: 82.6 + 0.5 is 83.1, and the cast chops that to 83. Parentheses decide the order, so read them before you read the cast.

   Correct. Line 2 evaluates 83.1 first and then truncates it to 83; line 3 truncates 82.6 straight down to 82. This is the whole round-half-up idiom in two lines: (int) always drops the fraction, so you add 0.5 first when you want rounding.

   rounded is declared int, so it cannot hold 82.6, and the value stored in it is the result of the cast, which has no fractional part at all. The original score is never printed.

5. int points = 7;
   points += 2.8;
   System.out.println(points);

   What is the value of points after the code segment executes?

   10 9 9.8 The code does not compile, because 2.8 is not an int

   10 would require rounding 9.8 up, and nothing here rounds. The implicit cast that compound assignment performs behaves exactly like (int): it discards the fractional part instead of rounding it.

   Correct. points += 2.8; means points = (int) (points + 2.8);. The sum 9.8 is computed as a double and then narrowed, so the 0.8 is thrown away and 9 is stored: the silent truncation that makes compound assignment worth watching.

   points is declared int and an int variable can never hold 9.8. 9.8 is the intermediate value of the addition, not the value that survives the assignment.

   This is the difference between points += 2.8; and points = points + 2.8;. The second form really is a compile-time error; the compound form compiles because it carries a built-in narrowing cast.

6. public class Converter {
       public static double milesToKm(double miles) {
           return miles * 1.609;
       }
   
       public static String formatLabel(String name, int count) {
           return name + ": " + count;
       }
   }

   Each of the following statements appears in the main method of another class. Which one causes a compile-time error?

   double d = Converter.milesToKm(5); String s = Converter.formatLabel("laps", 3); String s = Converter.formatLabel(3, "laps"); double d = Converter.milesToKm(2.5);

   This compiles and returns 8.045. An int argument is widened to double automatically, because no information is lost going from 5 to 5.0: widening is the one conversion Java performs for you.

   This compiles and returns laps: 3. The first argument is a String and the second an int, matching the parameter list (String name, int count) position by position.

   Correct. Arguments are matched to parameters by position, never by name or by guesswork, so 3 lands on the String parameter. javac reports incompatible types: int cannot be converted to String. Swapping the two arguments fixes it.

   This compiles and returns 4.0225. A double literal passed to a double parameter needs no conversion at all, so it is the least problematic call of the four.

7. // roll should end up holding a whole number
   // from 5 through 20, with every value possible
   int roll = /* missing code */;
   System.out.println(roll);

   Which replacement for /* missing code */ makes the segment work as intended for every possible value returned by Math.random?

   (int) (Math.random() * 20) + 5 (int) (Math.random() * 16) + 5 (int) (Math.random() * 15) + 5 (int) (Math.random() * 21) + 5

   This comes from multiplying by the larger endpoint instead of the count of values. Running it 400,000 times produces values from 5 up to 24, so it overshoots the range by four.

   Correct. The range 5 through 20 contains 20 - 5 + 1, or 16, different values. Math.random() returns at least 0.0 and always less than 1.0, so Math.random() * 16 truncates to 0 through 15, and adding 5 shifts that to 5 through 20. Testing both ends confirms it: 0.0 gives 5, and 0.999999 gives 20.

   Using high - low instead of high - low + 1 loses one value. The truncated product runs 0 through 14, so the largest result is 19 and the value 20 can never occur.

   21 is the count of values from 0 through 20, but the range does not start at 0. Because 5 is added afterwards, this reaches 25, which is five past the intended top.

8. public class Rectangle {
       private double width;
       private double height;
       public Rectangle(double w, double h) { width = w; height = h; }
       public void setWidth(double w) { width = w; }
       public double getWidth() { return width; }
       public double getArea() { return width * height; }
   }

   Rectangle a = new Rectangle(3.0, 4.0);
   Rectangle b = new Rectangle(5.0, 2.0);
   b = a;
   b.setWidth(10.0);
   System.out.println(a.getArea() + " " + b.getArea());

   What is printed as a result of executing the code segment?

   12.0 40.0 40.0 40.0 12.0 10.0 40.0 20.0

   This treats b = a; as copying the rectangle rather than copying a reference. If there were still two objects, a would keep its area of 12.0, but after line 3 there is only one object with two names.

   Correct. Line 3 stores the address in a into b, so both variables now point at the 3.0-by-4.0 object and the 5.0-by-2.0 object becomes unreachable. Line 4 is the decisive step: setting the width through b changes the one shared object to 10.0 by 4.0, and both calls report 40.0.

   10.0 is the new width, not the area. getArea returns width * height, and the height of the surviving object is still 4.0.

   20.0 would be the area of the second rectangle after its width changed to 10.0, but that object was abandoned on line 3 and setWidth never touches it. Draw the two arrows before answering an aliasing question.

9. public class BankAccount {
       private double balance;
       public BankAccount(double startingBalance) { balance = startingBalance; }
       public void deposit(double amount) { balance = balance + amount; }
       public void withdraw(double amount) { balance = balance - amount; }
       public double getBalance() { return balance; }
   }

   // in a different class, intended to return twice the account's balance
   public static double doubledBalance(BankAccount acct) {
       /* missing code */
   }

   Which replacement for /* missing code */ makes the method work as intended?

   return acct.balance * 2; return BankAccount.getBalance() * 2; return acct.getBalance() * 2; return getBalance(acct) * 2;

   balance is declared private, so it is visible only inside BankAccount. javac reports balance has private access in BankAccount; the accessor method is the only door into that field.

   getBalance is an instance method, so it needs an object, not a class name. The compiler says non-static method getBalance() cannot be referenced from a static context: a class name works only for static methods such as Math.sqrt.

   Correct. An instance method is called on a reference with the dot operator, and because getBalance returns a double, the call can sit inside a larger expression. Passing an account holding 325.50 returns 651.0.

   This writes the object as an argument instead of as the receiver. There is no method named getBalance in the class doing the calling, so the compiler reports cannot find symbol.

10. String word = "Programming";
    System.out.println(word.substring(3, 7) + word.indexOf("gram"));

    What is printed as a result of executing the code segment?

    ramm3 gramm3 gram3 gram4

    This starts counting at index 1 instead of 0. Index 0 is P, 1 is r, 2 is o and 3 is g, so substring(3, 7) begins at the g, not at the r after it.

    Five characters would come from substring(3, 8). The second argument of substring is the index where the piece stops, and that character is not included, so indexes 3, 4, 5 and 6 give exactly four characters.

    Correct. substring(3, 7) takes indexes 3 through 6 of Programming, which is gram, and indexOf("gram") returns the index where that match begins, which is 3. The + then joins a String to an int, so the int is converted to text and the line prints gram3 with no space.

    4 would be the position of gram if the first character were numbered 1. Java indexes Strings from 0, which is also why indexOf can use -1 as its "not found" signal.

Lesson 2.1 · Unit 2 · CED topic 2.1

Algorithms with selection and repetition

Unit 1 gave you sequence: statements that run once, top to bottom. That is enough to compute something, but not enough to decide anything or to keep working until a job is done. Unit 2 adds selection (run this only when a condition is true) and iteration (run this again while a condition is true). Those three shapes express every algorithm on this exam.

Write the algorithm in numbered English steps before you write any Java. English is quick to fix, and once the steps are right the translation is nearly mechanical: a step that says if becomes an if, a step that says until becomes a loop, everything else is a plain statement. Flowcharts say the same thing in pictures: a diamond is a decision, an arrow flowing backwards is a loop.

total = total + price;        // sequence: runs once, in order

if (condition) {              // selection: runs 0 or 1 times
    // ...
}

while (condition) {           // iteration: runs 0, 1, or many times
    // ...
}

int attempts = 0;                                   // step 1
boolean unlocked = false;
while (attempts < 3 && !unlocked) {                // step 2   ITERATION
    attempts++;                                     // step 3
    String typed = entry(attempts);
    if (typed.equals(correct)) {                    // step 4   SELECTION
        unlocked = true;
    } else {
        System.out.println("Attempt " + attempts + ": " + typed + " rejected");
    }
}
if (unlocked) {                                     // step 6
    System.out.println("Unlocked on attempt " + attempts);
} else {
    System.out.println("Locked out");
}

Attempt 1: 4017 rejected
Attempt 2: 4701 rejected
Unlocked on attempt 3

public static double shippingCharge(double weightKg, int zone) {
    double charge = 4.95;
    double remaining = weightKg;       // loop control variable: remaining
    while (remaining > 20.0) {
        charge = charge + 7.50;
        remaining = remaining - 20.0;  // the update that ends the loop
    }
    charge = charge + 7.50;
    if (zone == 3) {
        charge = charge + 3.00;
    }
    return charge;
}

53.0 kg, zone 3: 30.45
12.0 kg, zone 1: 12.45

public static int doses(int start, int floorValue) {
    int count = 0;
    int size = start;
    while (size >= floorValue) {
        size = size / 2;
        count++;
    }
    return count;
}

    after halving 1: 600
    after halving 2: 300
    after halving 3: 150
    after halving 4: 75
halvings = 4

Lesson 2.2 · Unit 2 · CED topic 2.2

Boolean expressions

A condition is not a special kind of grammar that only fits inside parentheses. It is an ordinary expression whose type happens to be boolean, and boolean has exactly two values: true and false. That means age >= 13 is a value in the same way that 3 + 4 is a value. You can print it, pass it to a method, return it, or park it in a variable and use it three lines later.

Doing exactly that is the mark of readable code. When a test is named: boolean oldEnough = age >= 13;: the reader learns what the test means, and you compute it once instead of retyping it in four places where three of them can drift out of date. Two comparisons need care: double values that came out of arithmetic almost never land on an exact target, and == on objects asks whether two references point at the same object, not whether they hold the same characters.

boolean isMember = true;            // a boolean holds exactly true or false

boolean equal     = a == b;         // equal to
boolean different = a != b;         // not equal to
boolean under     = a < b;          // less than
boolean atMost    = a <= b;         // less than or equal to
boolean over      = a > b;          // greater than
boolean atLeast   = a >= b;         // greater than or equal to

boolean sameName  = name.equals("Ana");   // objects: equals, never ==

boolean isMember = true;
int age = 15;

boolean oldEnough = age >= 13;
boolean tooOld    = age > 19;

System.out.println("isMember:  " + isMember);
System.out.println("oldEnough: " + oldEnough);
System.out.println("tooOld:    " + tooOld);
System.out.println("age == 15: " + (age == 15));
System.out.println("age != 15: " + (age != 15));

isMember:  true
oldEnough: true
tooOld:    false
age == 15: true
age != 15: false

double x = 0.1 + 0.2;
System.out.println(x);
System.out.println(x == 0.3);
System.out.println(Math.abs(x - 0.3) < 0.000001);

String stored = "Ana";
String part = "An";
String typed = part + "a";
System.out.println(typed == stored);
System.out.println(typed.equals(stored));

0.30000000000000004
false
true
false
true

int a = 5;
int b = 5;
double d = 0.1 * 3;
String s1 = "yes";
String s2 = "y" + "es";
String s3 = "y";
s3 = s3 + "es";

System.out.println(a == b);
System.out.println(d == 0.3);
System.out.println(s1 == s2);
System.out.println(s1 == s3);
System.out.println(s1.equals(s3));

true
false
true
false
true

Lesson 2.3 · Unit 2 · CED topic 2.3

if statements and control flow

An if statement guards a block: the block runs when the condition is true and is skipped entirely when it is false. Add else and you get a fork: exactly one of the two blocks runs, never both, never neither. Everything after the if statement resumes as normal, no matter which way the fork went.

Two pieces of punctuation cause most of the damage in this lesson. The braces are optional when the body is a single statement, which tempts people to leave them out and then add a second line later that quietly falls outside the guard. And a semicolon right after if (...) is legal Java: it makes the body an empty statement, so the block below it always runs. Neither mistake is a compile error, so the compiler will not save you. Write the braces every time.

if (condition) {
    // runs only when condition is true
}

if (condition) {
    // exactly one of these two blocks runs
} else {
    // ...
}

public static String letterGrade(int score) {
    System.out.println("checking " + score);
    if (score >= 90) {
        return "A";
    }
    if (score >= 80) {
        return "B";
    }
    if (score >= 70) {
        return "C";
    }
    System.out.println("no band matched");
    return "F";
}

checking 91
returns A
checking 72
returns C
checking 55
no band matched
returns F

public static String broken(int score) {
    String g = "F";
    if (score >= 90); {
        g = "A";
    }
    return g;
}

broken(91) returns A
broken(55) returns A

public static void noBraces(int score) {
    if (score >= 90)
        System.out.println("A band");
        System.out.println("certificate printed");
}

certificate printed

public static int fee(int daysLate) {
    if (daysLate > 0)
        System.out.println("Late fee applies");
        return daysLate * 25;
    return 0;
}

L3b.java:6: error: unreachable statement
        return 0;
        ^
1 error

public static int fee(int daysLate) {
    if (daysLate > 0) {
        System.out.println("Late fee applies");
        return daysLate * 25;
    }
    return 0;
}

Late fee applies
fee(3) = 75
fee(0) = 0

Lesson 2.4 · Unit 2 · CED topic 2.4

Nested conditionals and multi-way selection

Real rules rarely have two cases. When they have five, you have two ways to write them. An if / else if / else chain lays the cases side by side and guarantees that exactly one of them runs. Nesting puts one if inside another and is the right shape when the second question only makes sense after the first is answered: you ask the weight tier within a zone, because the tiers differ by zone.

A chain has a property that independent if statements do not: once a test passes, every later test is skipped. That is exactly what you want for mutually exclusive cases, and it makes the order of the tests part of the logic. Put the most specific test first. Write the same five cases as five separate if statements and each one is evaluated on its own, which is how one order ends up charged in four tiers at once.

if (test1) {            // the chain: at most one block runs,
    // ...               // and the first true test wins
} else if (test2) {
    // ...
} else {
    // the catch-all; optional
}

if (outer) {            // the nest: the inner question is only
    if (inner) {        // asked when the outer answer was true
        // ...
    }
}

public static double shippingCost(int zone, double kg) {
    double cost = 0.0;
    if (zone == 1) {
        if (kg <= 1.0) {
            cost = 4.50;
        } else if (kg <= 5.0) {
            cost = 7.25;
        } else {
            cost = 12.00;
        }
    } else {
        if (kg <= 1.0) {
            cost = 6.75;
        } else if (kg <= 5.0) {
            cost = 11.50;
        } else {
            cost = 18.90;
        }
    }
    return cost;
}

zone 1, 0.8 kg: 4.5
zone 1, 3.0 kg: 7.25
zone 1, 9.0 kg: 12.0
zone 2, 0.8 kg: 6.75
zone 2, 5.0 kg: 11.5
zone 2, 9.0 kg: 18.9

public static double rewardBuggy(double total) {
    double off = 0.0;
    if (total >= 25.0)  { off = off + 2.00; }
    if (total >= 50.0)  { off = off + 5.00; }
    if (total >= 100.0) { off = off + 12.00; }
    if (total >= 200.0) { off = off + 25.00; }
    if (total >= 500.0) { off = off + 70.00; }
    return off;
}

public static double reward(double total) {
    double off = 0.0;
    if (total >= 500.0) {
        off = 70.00;
    } else if (total >= 200.0) {
        off = 25.00;
    } else if (total >= 100.0) {
        off = 12.00;
    } else if (total >= 50.0) {
        off = 5.00;
    } else if (total >= 25.0) {
        off = 2.00;
    }
    return off;
}

public static String band(int score) {
    if (score >= 70) {
        return "C";
    } else if (score >= 80) {
        return "B";
    } else if (score >= 90) {
        return "A";
    }
    return "F";
}

band(95)  = C
band(85)  = C
band(75)  = C
band(55)  = F

if (score >= 90) {
    return "A";
} else if (score >= 80) {
    return "B";
} else if (score >= 70) {
    return "C";
}
return "F";

Lesson 2.5 · Unit 2 · CED topic 2.5

Compound boolean expressions

Three operators combine conditions. && ("and") is true only when both sides are true; || ("or") is true when at least one side is true; ! ("not") flips a single value. They let one condition say what four nested if statements would otherwise have to.

Java evaluates them left to right with short-circuiting: as soon as the answer is settled, the rest is never evaluated. A false left side of &&, or a true left side of ||, skips the right side entirely. That is not a detail you can ignore: it is the mechanism behind the guard idiom, where the left side checks that something is safe to touch and the right side touches it.

!p            // highest: applies to the one operand on its right
p && q        // then and
p || q        // then or, lowest of the three

// so   a || b && c   groups as   a || (b && c)

if (s != null && s.length() > 0) {    // the guard idiom: the left side
    // safe to use s here                 protects the right side
}

public static boolean isLeapYear(int year) {
    return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
}

1900: false
2000: true
2023: false
2024: true

no-parens version agrees on 1600..2400: true
forgot-400 version agrees on 1600..2400: false
correct(2000)    = true
forgot400(2000)  = false

String note = null;
if (note != null && note.length() > 0) {
    System.out.println("has a note");
} else {
    System.out.println("no note printed - the guard worked");
}
System.out.println("now the operands the other way round:");
if (note.length() > 0 && note != null) {
    System.out.println("never reached");
}

no note printed - the guard worked
now the operands the other way round:
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "String.length()" because "<local1>" is null
    at L5.main(L5.java:35)

public static boolean canCheckOut(boolean isMember, int booksOut, boolean hasFines) {
    return isMember && booksOut < 5 && !hasFines;
}

member, 4 out, no fines: true
member, 5 out, no fines: false
member, 2 out, fines:    false
guest,  0 out, no fines: false

a || b && c   = true
a || (b && c) = true
(a || b) && c = false

Lesson 2.6 · Unit 2 · CED topic 2.6

Comparing and simplifying boolean expressions

Two conditions are equivalent when they produce the same value for every possible input, not for the inputs you happened to try. The exam tests this directly: it shows you a working condition and four proposed replacements and asks which ones keep the method working "for all values". The only way to answer with confidence is a truth table that includes the boundary cases.

Two simplifications are worth knowing by name. De Morgan's laws push a ! through a compound condition and flip the connector: the negation of "a and b" is "not a or not b", and the negation of "a or b" is "not a and not b". And any method shaped like if (test) return true; else return false; is just return test;: the condition is already a boolean, so wrapping it in an if to produce a boolean adds nothing.

!(p && q)   is equivalent to   !p || !q
!(p || q)   is equivalent to   !p && !q

// redundant
if (score >= 60) {
    return true;
} else {
    return false;
}

// the same method
return score >= 60;

public static boolean outOfRangeA(int x, int lo, int hi) {
    if (x < lo) {
        return true;
    } else if (x > hi) {
        return true;
    } else {
        return false;
    }
}

public static boolean outOfRangeB(int x, int lo, int hi) {
    return x < lo || x > hi;
}

public static boolean outOfRangeC(int x, int lo, int hi) {
    return !(x >= lo && x <= hi);
}

all three versions agree for x = -2..12: true
outOfRangeB(0, 1, 10)  = true
outOfRangeB(1, 1, 10)  = false
outOfRangeB(10, 1, 10) = false
outOfRangeB(11, 1, 10) = true

public static boolean comfortable(int temp, int humid) {
    if (!(temp > 30 || humid > 70)) {
        return true;
    } else {
        return false;
    }
}

public static boolean comfortable(int temp, int humid) {
    return temp <= 30 && humid <= 70;
}

agree for temp 20..40 and humidity 50..90: true
comfortableShort(28, 65) = true
comfortableShort(30, 70) = true
comfortableShort(31, 65) = false
comfortableShort(28, 71) = false

Lesson 2.7 · Unit 2 · CED topic 2.7

while loops

A while loop repeats a block for as long as a condition holds. The condition is tested before each pass, including the very first, so a loop whose condition starts out false runs zero times: that is a feature, not an edge case. Use while when you do not know in advance how many passes you need: keep dividing until the number is gone, keep reading until the sentinel arrives.

Every correct while loop does three jobs with its loop control variable, and they sit in three different places. Initialize it before the loop, test it in the header, and update it inside the body. Skip the initialization and the code will not compile; skip the update and the program runs forever. Almost every broken loop you will meet is missing one of the three.

int n = start;               // 1. initialize, before the loop
while (n > 0) {              // 2. test, at the top of every pass
    // do the work
    n = n / 10;              // 3. update, inside the body
}
// control arrives here the first time the test is false

public int digitCount(int n) {
    int count = 0;
    while (n > 0) {
        n = n / 10;
        count++;
    }
    return count;
}

Scanner in = new Scanner(System.in);
int total = 0;
int readings = 0;
int value = in.nextInt();          // prime the loop: read one before testing
while (value != -1) {
    total = total + value;
    readings = readings + 1;
    value = in.nextInt();          // read the next one at the end of the body
}
System.out.println("readings: " + readings);
System.out.println("total: " + total);

readings: 3
total: 25

int n = 4073;
int count = 0;
while (n > 0) {
    count++;
    System.out.println("pass " + count + ":   n = " + n + "   count = " + count);
}

pass 1:   n = 4073   count = 1
pass 2:   n = 4073   count = 2
pass 3:   n = 4073   count = 3
pass 4:   n = 4073   count = 4
pass 5:   n = 4073   count = 5
pass 6:   n = 4073   count = 6

public int digitSum(int n) {
    int sum = 0;
    while (n > 0) {
        sum = sum + n % 10;
        n = n / 10;
    }
    return sum;
}

Lesson 2.8 · Unit 2 · CED topic 2.8

for loops

A for loop is a while loop with the three jobs collected into one header, where you can see them all at once. Use it when the number of passes is known before the loop starts: count to n, walk the indexes of a String, step through a range. Use while when it is not.

The order in which the three parts run is worth saying out loud, because every "how many times" question depends on it: the initialization runs once; then the condition is tested; if it is true the body runs; then the update runs; then the condition is tested again. The update happens after the body, not before, and the final update is what makes the condition fail.

for (int i = 0; i < n; i++) {      // initialization; condition; update
    // body
}

int i = 0;                         // the same loop, spelled out
while (i < n) {
    // body
    i++;
}

public int sumMultiplesOfThree(int limit) {
    int sum = 0;
    for (int k = 3; k < limit; k = k + 3) {
        sum = sum + k;
    }
    return sum;
}

sumMultiplesOfThree(20)  = 63
sumMultiplesOfThree(100) = 1683
sumMultiplesOfThree(3)   = 0
while version (20)       = 63
while version (100)      = 1683

for (i = 2; i <= 20; i = i + 4) {
    System.out.println("body runs with i = " + i);
}

body runs with i = 2
body runs with i = 6
body runs with i = 10
body runs with i = 14
body runs with i = 18
iterations 5   last i 18   i after loop 22

Lesson 2.9 · Unit 2 · CED topic 2.9

Implementing selection and iteration algorithms

Almost every loop the exam asks you to write is one of four accumulator patterns: a running sum, a count of the items that match a condition, a running maximum or minimum, and an early return that stops as soon as an answer is known. Learn the four shapes and most free-response loops become a matter of filling in the condition.

Two decisions separate a working accumulator from a broken one. First, what the accumulator starts at: 0 for a sum, 0 for a count, and, this is the one people get wrong, the first value in the data for a maximum or a minimum. Second, where the return goes: after the loop when you must see everything, inside the loop when the first match settles the question.

int sum = 0;                     // running sum
int count = 0;                   // count matching
int max = value(lo);             // running maximum: the FIRST value, never 0
for (int k = lo + 1; k <= hi; k++) {
    if (value(k) > max) {
        max = value(k);
    }
}

for (int k = lo; k <= hi; k++) { // early return: stop at the first match
    if (matches(k)) {
        return k;
    }
}
return -1;                       // no match found

value(1..12): 4 15 24 31 36 39 40 39 36 31 24 15

public int largestValue(int lo, int hi) {
    int max = value(lo);
    for (int k = lo + 1; k <= hi; k++) {
        if (value(k) > max) {
            max = value(k);
        }
    }
    return max;
}

public double averageAbove(int lo, int hi, int threshold) {
    int sum = 0;
    int count = 0;
    for (int k = lo; k <= hi; k++) {
        if (value(k) > threshold) {
            sum = sum + value(k);
            count++;
        }
    }
    if (count == 0) {
        return -1.0;
    }
    return (double) sum / count;
}

largestValue(1, 12) = 40
countAbove(1, 12, 30) = 7
averageAbove(1, 12, 30) = 36.0
averageAbove(1, 12, 100) = -1.0

temp(1..5): -4 -7 -10 -13 -16

public int maxTempWrong(int firstDay, int lastDay) {
    int max = 0;                                  // the bug
    for (int day = firstDay; day <= lastDay; day++) {
        if (temp(day) > max) {
            max = temp(day);
        }
    }
    return max;
}

maxTempWrong(1, 5) = 0
maxTempRight(1, 5) = -4

public int firstDayBelow(int limit) {
    for (int day = 1; day <= 5; day++) {
        if (temp(day) < limit) {
            return day;
        }
    }
    return -1;
}

temp(1..5): -4 -7 -10 -13 -16
firstDayBelow(-9)  = 3
firstDayBelow(-20) = -1

Lesson 2.10 · Unit 2 · CED topic 2.10

Implementing String algorithms

A String traversal is an ordinary for loop over indexes 0 to length() - 1. The AP subset has no charAt, so the character at index i is s.substring(i, i + 1): a one-character String, which means you compare it with equals, never with ==.

Because Strings are immutable, you never modify one in place. You build a new one, and which side of the + you put the new character on decides whether you get a copy or a reversal. That one-character choice is the whole difference between the two methods below.

for (int i = 0; i < s.length(); i++) {
    String ch = s.substring(i, i + 1);    // the character at index i
    if (ch.equals("a")) {
        // ...
    }
}

result = result + ch;   // appends: builds a copy
result = ch + result;   // prepends: builds the reversal

public int countVowels(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        String ch = s.substring(i, i + 1);
        if (ch.equals("a") || ch.equals("e") || ch.equals("i")
                || ch.equals("o") || ch.equals("u")) {
            count++;
        }
    }
    return count;
}

public String reverse(String s) {
    String result = "";
    for (int i = 0; i < s.length(); i++) {
        result = s.substring(i, i + 1) + result;
    }
    return result;
}

countVowels("programming") = 3
countVowels("rhythm") = 0
reverse("class") = ssalc
reverse("") = []

public boolean isPalindrome(String s) {
    return s.equals(reverse(s));
}

isPalindrome("racecar") = true
isPalindrome("level") = true
isPalindrome("class") = false

public int countOccurrences(String s, String target) {
    int count = 0;
    String rest = s;
    int pos = rest.indexOf(target);
    while (pos >= 0) {
        count++;
        rest = rest.substring(pos + 1);
        pos = rest.indexOf(target);
    }
    return count;
}

countOccurrences("mississippi", "ss") = 2
countOccurrences("mississippi", "i") = 4
countOccurrences("mississippi", "z") = 0

Lesson 2.11 · Unit 2 · CED topic 2.11

Nested iteration

A nested loop is a loop whose body contains another loop. The rule that explains all of their behavior is this: the inner loop runs to completion on every single pass of the outer loop. The inner loop control variable is re-initialized each time, counts all the way up, and finishes, before the outer variable advances by one.

When the inner bound does not mention the outer variable, the total number of inner passes is the product of the two counts. When it does, the total is a sum instead, and that is the case the exam asks about. Outer loop means rows, inner loop means the items within a row: the shape you will reuse for 2D arrays in Unit 4.

for (int r = 1; r <= rows; r++) {         // outer: runs `rows` times
    for (int c = 1; c <= cols; c++) {     // inner: restarts at 1 every pass
        // this statement runs rows * cols times
    }
    // reached once per row, after the inner loop has finished
}

public void multiplicationTable(int n) {
    for (int r = 1; r <= n; r++) {
        String line = "";
        for (int c = 1; c <= n; c++) {
            int product = r * c;
            if (product < 10) {
                line = line + "  " + product;
            } else {
                line = line + " " + product;
            }
        }
        System.out.println(line);
    }
}

public void triangle(int n) {
    for (int r = 1; r <= n; r++) {
        String line = "";
        for (int c = 1; c <= r; c++) {
            line = line + "*";
        }
        System.out.println(line);
    }
}

  1  2  3  4
  2  4  6  8
  3  6  9 12
  4  8 12 16
*
**
***
****

int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        count++;
    }
}

public int pairsCheckedUntil(int n, int target) {
    int checked = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            checked++;
            if (i * j == target) {
                return checked;
            }
        }
    }
    return -1;
}

pairsCheckedUntil(6, 12) = 12
pairsCheckedUntil(6, 37) = -1

int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        count++;
    }
}

upperTriangle(6) = 21
n(n+1)/2 = 21

Lesson 2.12 · Unit 2 · CED topic 2.12

Informal run-time analysis

"How fast is this method?" is really the question "how many times does its innermost statement execute, as a function of the input size n?" You answer it by counting, not by timing: timings depend on the machine, but the count is a property of the code. AP Computer Science A asks for the count itself, in plain numbers, rather than big-O notation.

Three shapes cover nearly everything here. A single loop over the data runs about n times; a loop nested inside another over the same data runs about n² times; a loop that halves its variable each pass runs about log base 2 of n times. The gap between them is invisible at n = 4 and decisive at n = 1000.

for (int i = 0; i < n; i++) {        // about n executions
    count++;
}

for (int i = 0; i < n; i++) {        // about n * n executions
    for (int j = 0; j < n; j++) {
        count++;
    }
}

int x = n;                           // about log base 2 of n executions
while (x > 1) {
    x = x / 2;
    count++;
}

for (int i = 1; i < n; i = i * 3) {
    count++;
}

    body runs with i = 1
    body runs with i = 3
    body runs with i = 9
    body runs with i = 27
    body runs with i = 81
iterations = 5

Unit 2 review · 10 multiple-choice

Unit 2 review: selection and iteration

Ten exam-style multiple-choice questions in lesson order (boolean expressions and String comparison, if and nested if, compound conditions and De Morgan's laws, while and for loops, the accumulator patterns, String traversal, nested iteration and statement counting) with every printed value taken from a real run of the code.

Multiple choice

1. A program stores a secret pass phrase and then assembles the phrase the user types, one piece at a time, before checking it.

   String secret = "ope";
   String typed = "op";
   typed = typed + "e";
   System.out.println((typed == secret) + " " + typed.equals(secret));

   What is printed as a result of executing the code segment?

   true true false true false false true false

   This assumes == compares the letters. For objects, == asks whether the two variables hold the same address, and the concatenation on line 3 built a brand-new String object rather than reusing the one named secret.

   Correct. The decisive line is line 3: joining "op" and "e" at run time produces a new object, so typed and secret are two different objects that happen to hold the same characters. == reports false on the addresses while equals reports true on the contents.

   equals compares character by character, and both Strings hold o, p, e in that order, so the second value cannot be false. Getting this half wrong usually means treating equals as a synonym for ==.

   This has the two comparisons backwards. == is the one that fails on separately built Strings, and equals is the one that succeeds, which is exactly why the exam insists on equals for every String comparison.

2. int x = 5;
   if (x > 10);
   {
       x = x + 1;
   }
   System.out.println(x);

   What is the value of x after the code segment executes?

   5 6 11 The code segment does not compile

   5 is what you would get if the block belonged to the if. Read the semicolon at the end of line 2: it closes the if immediately, so the block below is no longer attached to any condition.

   Correct. The semicolon after if (x > 10) is a complete empty statement, so the if controls nothing at all. The braces that follow are just an ordinary block that always executes, and x goes from 5 to 6 even though x > 10 is false.

   11 would require the condition to be true and the body to add 6, neither of which happens. The body adds 1, and the condition is irrelevant because nothing depends on it.

   A semicolon there is legal Java, which is exactly why this bug is dangerous: the compiler accepts it silently and the program simply does the wrong thing. Removing the semicolon is the fix.

3. public static double shipping(double pounds) {
       double cost = 0.0;
       if (pounds > 10.0) {
           cost = cost + 12.0;
       }
       if (pounds > 5.0) {
           cost = cost + 8.0;
       }
       else {
           cost = cost + 4.0;
       }
       return cost;
   }

   System.out.println(shipping(12.0) + " " + shipping(7.0) + " " + shipping(3.0));

   What is printed as a result of executing the code segment?

   12.0 8.0 4.0 20.0 8.0 4.0 20.0 12.0 4.0 12.0 12.0 4.0

   This is the result the author probably wanted, and it is what an if / else if chain would produce. The two if statements here are independent, though, so the first one does not stop the second from being tested.

   Correct. The 12-pound order is charged twice: 12 is greater than 10, adding 12.0, and it is also greater than 5, adding 8.0, for 20.0. The 7-pound order fails the first test and passes the second, giving 8.0, and the 3-pound order falls to the else, giving 4.0. Writing else if on line 5 would make all three tiers exclusive.

   7 pounds never reaches the 12.0 charge, because 7.0 > 10.0 is false. The double charge in this method can only happen above 10 pounds, where both conditions are true at once.

   This mixes up which order is overcharged. 12 pounds triggers both additions and 7 pounds triggers only one, so the first value must be the larger of the two, not the smaller.

4. String word = null;
   if (word != null && word.length() > 2) {
       System.out.println("long");
   }
   else {
       System.out.println("skipped");
   }

   What is printed as a result of executing the code segment?

   long skipped Nothing is printed, because the program throws a NullPointerException Nothing is printed, because the if statement has no true branch to take

   long requires both operands of && to be true, and the first one is already false because word holds null. A false left operand settles an && on its own.

   Correct. && short-circuits: once word != null evaluates to false, the whole condition is known to be false and word.length() is never evaluated. The else branch runs and prints skipped. This ordering is the standard null guard, and reversing the two operands would break it.

   Calling length() on null would indeed throw a NullPointerException, but that call never happens here. Short-circuiting is what protects it, which is the entire reason the null test is written first.

   An if with an else always takes exactly one of its two branches, so something is always printed. A false condition sends control to the else, it does not skip the statement altogether.

5. The method below is being rewritten so that it returns its answer directly instead of returning true or false from an if-else.

   public static boolean isSafe(int x, int y) {
       if (!(x > 10 && y > 10)) {
           return true;
       }
       else {
           return false;
       }
   }

   public static boolean isSafe(int x, int y) {
       /* missing code */
   }

   Which replacement for /* missing code */ makes the method work as intended for all int values of x and y?

   return x <= 10 && y <= 10; return x <= 10 || y <= 10; return x > 10 || y > 10; return !(x <= 10 && y <= 10);

   Negating && gives ||, not &&. Testing both versions on every pair from 0 through 20 shows 220 disagreements, the first at x = 0, y = 11, where the original returns true and this replacement returns false.

   Correct. De Morgan's law turns !(x > 10 && y > 10) into !(x > 10) || !(y > 10), and negating each relational operator gives x <= 10 || y <= 10. Checked against the original on all 441 pairs from 0 through 20, it agrees every time, and returning the condition directly is always better than if (c) return true; else return false;.

   This drops the outer ! and changes && to ||, so it returns the exact opposite in most cases. At x = 0, y = 0 the original returns true while this returns false.

   This negates the wrong expression. !(x <= 10 && y <= 10) is equivalent to x > 10 || y > 10, which disagrees with the original on 221 of the 441 pairs tested, starting at x = 0, y = 0.

6. int n = 4073;
   int count = 0;
   while (n > 0) {
       n = n / 10;
       count++;
   }

   How many times does the body of the loop execute?

   3 4 5 The body executes without stopping, because n never becomes negative

   3 counts the divisions that leave something behind and forgets the last one. The fourth pass starts with n equal to 4, and 4 > 0 is true, so the body runs a fourth time before the condition finally fails.

   Correct. Integer division walks n through 4073, 407, 40, 4, then 0. The pass that decides the answer is the fourth: n is 4, the condition is still true, the body runs and makes n zero, and the fifth test fails. The result is the number of digits in 4073.

   5 counts one test too many. The pass that sets n to 0 is the fourth; the fifth time the condition is checked it is false, so no fifth body executes: count bodies, not tests.

   The loop stops when n reaches 0, and it does not need to go negative. Integer division of a positive number by 10 always shrinks it, so this loop is guaranteed to terminate; it is deleting the update line that would make it infinite.

7. int sum = 0;
   for (int i = 3; i < 30; i = i + 3) {
       sum = sum + i;
   }
   System.out.println(sum);

   Which of the following code segments produces the same output as the code segment above?

   int sum = 0; int i = 3; while (i <= 30) { sum = sum + i; i = i + 3; } System.out.println(sum); int sum = 0; int i = 3; while (i < 30) { i = i + 3; sum = sum + i; } System.out.println(sum); int sum = 0; int i = 3; while (i < 30) { sum = sum + i; i = i + 3; } System.out.println(sum); int sum = 0; int i = 3; while (i < 30) { sum = sum + i; } i = i + 3; System.out.println(sum);

   Changing < to <= lets i reach 30 and adds one extra term, so this prints 165 instead of 135. The bound in a for header must survive the translation unchanged.

   Updating before accumulating skips the first value and picks up an extra one at the end: this adds 6 through 30 and prints 162. In a for loop the update runs after the body, so the body must come first here too.

   Correct. A for loop is a while loop with its three parts moved: initialization before the loop, the same condition in the header, and the update as the last statement of the body. Both segments add 3, 6, 9, and on up to 27 and print 135.

   Moving the update outside the braces means i stays 3 forever and the condition never becomes false. Compiled and run, this segment never terminates and prints nothing at all.

8. public static int largest(int low, int high) {
       int max = 0;
       for (int n = low; n <= high; n++) {
           int value = 12 - n * n;
           if (value > max) {
               max = value;
           }
       }
       return max;
   }

   What does the call largest(4, 7) return?

   12 0 -4 -37

   12 is the constant in the formula, not a value the formula produces here. value would only be 12 if n were 0, and this call starts n at 4.

   Correct. The four values are 12 - 16, 12 - 25, 12 - 36 and 12 - 49, or -4, -13, -24 and -37. Every one of them fails value > max on the very first comparison, so max never moves off its starting 0 and the method returns a number the formula never produced. Start the running maximum at the first data value instead.

   -4 is the true largest value, and it is what the method should return, but it never gets stored, because -4 is not greater than the initial 0. This is the gap the question is testing.

   -37 is the smallest of the four values and the last one computed. The if only overwrites max with something larger, so the final value computed has no special status.

9. String word = "class";
   String result = "";
   for (int i = 0; i < word.length(); i++) {
       result = word.substring(i, i + 1) + result;
   }
   System.out.println(result);

   What is printed as a result of executing the code segment?

   class ssalc lass Nothing is printed, because the segment throws a StringIndexOutOfBoundsException

   class is what you get from result = result + word.substring(i, i + 1);, with the accumulator on the left. The order of the two operands around + is the whole difference between copying a String and reversing it.

   Correct. Each new character is glued to the front of what has been built so far, so result grows c, lc, alc, salc, ssalc. The decisive pass is the last one, i = 4: the s at index 4 goes in front of salc and produces ssalc.

   This loses the first character, which would happen if the loop started at i = 1. The header starts at 0, and index 0 is the c, so all five characters are visited.

   The largest value i reaches is 4, so the last call is substring(4, 5), which is legal on a five-character String: the second argument may equal the length. The condition i < word.length() is what keeps it in bounds.

10. int count = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < i; j++) {
            count++;
        }
    }
    System.out.println(count);

    How many times does the body of the inner loop execute?

    25 20 10 15

    25 is 5 times 5, the count you get when the inner bound is the same constant as the outer one. Here the inner condition is j < i, so the inner loop runs a different number of times on each outer pass.

    20 would be 5 times 4, which treats the inner loop as running 4 times every pass. It runs 4 times only on the final pass, when i is 4.

    Correct. The inner loop runs 0 times when i is 0, then 1, 2, 3 and 4 times, and 0 + 1 + 2 + 3 + 4 is 10: the formula n * (n - 1) / 2 with n equal to 5. The first outer pass is the one people miss: an empty inner loop still counts as an outer pass. Even so, this shape grows like n squared, so doubling n roughly quadruples the count.

    15 is 1 + 2 + 3 + 4 + 5, which would be right if the inner condition were j <= i. With j < i the inner body runs exactly i times on each pass, so the sum starts at 0 and stops at 4.

Lesson 3.1 · Unit 3 · CED topics 3.1–3.2

Abstraction and program design

Until now you have used classes somebody else wrote. From here you write them, and the hard part is not the Java: it is deciding what the class is. Every class answers two questions: what must this thing remember, and what must it be able to do? The answers become the private instance variables and the public methods, in that order.

That is what abstraction buys you. A caller holding a lunch account should be able to deposit money and buy a meal without knowing whether the balance is stored in dollars or in cents. Every field you invent is data somebody has to keep correct, and design decisions reach real people: an assumption you bake into a method quietly decides who can use the program at all.

public class ClassName {
    private Type fieldName;          // what the object must REMEMBER

    public ClassName(Type param) {   // how a new object STARTS
    }

    public Type methodName(Type p) { // what the object must DO
    }
}

public LunchAccount(String studentName, int idNumber)
public double  getBalance()
public void    deposit(double amount)
public boolean buyMeal(double price)
public void    setFreeLunch(boolean status)

public boolean buyMeal(double price) {
    if (freeLunch) {
        return true;
    }
    if (balance >= price) {
        balance = balance - price;
        return true;
    }
    return false;
}

balance 0.0
after deposit 20.0
buyMeal(3.75) true
balance 16.25
buyMeal(50.00) false
balance 16.25
buyMeal(50.00) true
balance 16.25

private String subject;
private String tutorName;
private int capacity;
private int filled;

public TutorSlot(String subject, String tutorName, int capacity)
public String  getSubject()
public int     spotsLeft()
public boolean signUp()

Lesson 3.2 · Unit 3 · CED topic 3.3

Anatomy of a class

A class file has a fixed shape, and the compiler expects each part in its place: the class header, then the private instance variables, then the constructor, then the methods. The class is the description. An object is one thing built from it by new. One Student class can produce three hundred student objects, and each one carries its own copy of every instance variable.

Instance variables are private for a reason worth stating plainly: a private field can only be changed by code inside the class, so every rule the class wants to enforce is enforceable. Make the field public and any line of any program can overwrite it, and the rule is gone. Fields you never assign are not garbage, either: Java gives every instance variable a default: 0, 0.0, false, or null for a reference.

public class Student {          // class header
    private String name;        // instance variable
    private int points;         // instance variable

    public Student(String startName) {   // constructor: same name, NO return type
        name = startName;
        points = 0;
    }

    public int getPoints() {    // accessor: returns a field, changes nothing
        return points;
    }

    public void addPoints(int earned) {  // mutator: changes a field, returns nothing
        points = points + earned;
    }
}

public void addPoints(int earned) {
    int capped = earned;
    if (capped > 10) {
        capped = 10;
    }
    points = points + capped;
}

points 0
points 7
points 17

private String label;
private int count;
private double rate;
private boolean active;

public Blank() {
}

label=null  count=0  rate=0.0  active=false

Main.java:4: error: points has private access in Student
        s.points = -400;
         ^
1 error

through the mutator: 10
straight at the field: -400

Lesson 3.3 · Unit 3 · CED topic 3.4

Constructors

A constructor is the method that runs once, at birth, to put an object into a legal starting state. It is written differently from every other method: its name is exactly the class name, and it has no return type at all, not even void. Write public void Rectangle(...) and you have not written a constructor; you have written an ordinary method that happens to be capitalized, and new Rectangle(3.0, 4.0) will not compile.

A class may have several constructors as long as their parameter lists differ: that is ordinary overloading. Java hands you a free no-argument constructor only if you write none yourself. The moment you write one constructor with parameters, the free one disappears, and that is the single most common surprise in this topic.

public class Rectangle {
    private double width;
    private double height;

    public Rectangle() {                 // no-argument constructor
        width = 1.0;
        height = 1.0;
    }

    public Rectangle(double startWidth, double startHeight) {   // overloaded
        width = startWidth;
        height = startHeight;
    }
}

Rectangle a = new Rectangle();
Rectangle b = new Rectangle(3.0, 4.0);
Rectangle c = new Rectangle(2.5, 2.5);

a 1.0 x 1.0  area 1.0
b 3.0 x 4.0  area 12.0
c 2.5 x 2.5  area 6.25

Main.java:3: error: constructor Rectangle in class Rectangle cannot be applied to given types;
        Rectangle a = new Rectangle();
                      ^
  required: double,double
  found:    no arguments
  reason: actual and formal argument lists differ in length
1 error

public class Counter {
    private int count;

    public int getCount() {
        return count;
    }
}

count 0

public Locker() {
    number = 0;
    assigned = false;
}

public Locker(int startNumber) {
    number = startNumber;
    assigned = false;
}

new Locker()      number 0    assigned false
new Locker(214)   number 214  assigned false

Lesson 3.4 · Unit 3 · CED topic 3.5

Writing accessor and mutator methods

Once the fields are private, the methods are the whole interface. Two shapes cover most of them. An accessor returns information and changes nothing: its header has a return type and usually no parameters. A mutator changes the object and usually returns nothing: its header is void and it takes the new value as a parameter.

The interesting work happens inside a mutator. Because it is the only door into the field, it is also the only place a class can defend itself against a bad value. A thermostat that accepts 200 degrees is not a thermostat with a bug in it later; it is a thermostat with a bug in it now. Clamping the value, rather than storing it and hoping, is what makes the private field worth having.

public int getTarget() {          // accessor: return type, no parameters
    return target;
}

public void setTarget(int degrees) {   // mutator: void, one parameter
    target = clamp(degrees);           // one method of the class calling another
}

private int clamp(int degrees) {       // private: a tool for this class only
    // return degrees pulled inside the legal range
}

private int clamp(int degrees) {
    if (degrees < 50) {
        return 50;
    }
    if (degrees > 85) {
        return 85;
    }
    return degrees;
}

start 68
setTarget(45) -> 50
setTarget(50) -> 50
setTarget(68) -> 68
setTarget(85) -> 85
setTarget(90) -> 85
Lab 2 ends at 85

public Thermostat(String startRoom, int startTarget) {
    room = startRoom;
    target = clamp(startTarget);       // not  target = startTarget;
}

public boolean nudge(int change) {
    int wanted = target + change;
    target = clamp(wanted);
    return wanted == target;
}

start 84
nudge(1) returned true   target 85
nudge(4) returned false  target 85

Lesson 3.5 · Unit 3 · CED topic 3.6

Passing and returning object references

Java always passes a copy of what the variable holds. For an int that is a copy of the number, so a method can never change the caller's int. For an object, what the variable holds is a reference, so the method gets a copy of the address: a second arrow pointing at the very same object. Call a mutator through that arrow and the caller's object changes for good.

The same fact runs in the other direction. If an accessor returns the reference stored in a private field, the caller now holds an arrow into your object's insides and can rearrange them without calling a single one of your methods. private did not stop it, because you handed the reference over yourself.

public static void transfer(Account from, Account to, double amount) {
    from.withdraw(amount);   // reaches the caller's object
    to.deposit(amount);      // reaches the caller's object
}

public static void swap(Account x, Account y) {
    Account temp = x;
    x = y;                   // moves this method's OWN arrow
    y = temp;                // the caller never sees either move
}

before: Maya 300.0  Ravi 50.0
after:  Maya 180.0  Ravi 170.0

public ArrayList<String> getRoster() {
    return roster;              // hands out the field itself
}

roster size 3
after the caller edits getRoster():  size 3  [Bo, Cy, Intruder]

public ArrayList<String> getRosterCopy() {
    ArrayList<String> copy = new ArrayList<String>();
    for (int i = 0; i < roster.size(); i++) {
        copy.add(roster.get(i));
    }
    return copy;
}

after the caller edits getRosterCopy(): size 3  [Ana, Bo, Cy]
the caller's own copy:                  [Bo, Cy, Intruder]

before swap:  a is Maya  b is Ravi
inside swap:  x is Ravi   y is Maya
after swap:   a is Maya  b is Ravi

Lesson 3.6 · Unit 3 · CED topic 3.7

Class variables and class methods

An instance variable belongs to an object: build four tickets and there are four copies of holder. A static variable, a class variable, belongs to the class itself, and there is exactly one copy no matter how many objects exist, or whether any exist at all. That is what makes it the right tool for a fact about the whole class: how many objects have been created, or what the next ID number should be.

A static method follows the same logic. It runs on the class, not on an object, so there is no object for it to look at, and that single sentence explains every compile error in this topic. A static method cannot read an instance variable and cannot use this, because neither one exists until somebody supplies an object.

public class Ticket {
    private static int nextId = 1000;   // ONE copy, shared by the class

    private int id;                     // one copy per object
    private String holder;

    public Ticket(String startHolder) {
        holder = startHolder;
        id = nextId;      // take the current number
        nextId++;         // and move the shared counter on
    }

    public static void resetIds() {     // called as Ticket.resetIds()
        nextId = 1000;
    }
}

nextId before any ticket: 1000
a.getId() 1000   nextId 1001
b.getId() 1001   nextId 1002
c.getId() 1002   nextId 1003
d.getId() 1003   nextId 1004
a still has id 1000
after resetIds(): nextId 1000, a.getId() 1000

public static void resetIds() {
    nextId = 1000;
    id = 0;             // which ticket's id?
}

Ticket.java:27: error: non-static variable id cannot be referenced from a static context
        id = 0;
        ^
1 error

p.getVotes() 2
q.getVotes() 1
Poll.getTotalVotes() 3
Poll.MAX_OPTIONS 4

Lesson 3.7 · Unit 3 · CED topic 3.8

Scope and access

Scope is the region of code in which a name means something. Three kinds of variable live for three different lengths of time. An instance variable is declared inside the class but outside every method, and it lives as long as the object does. A parameter exists for one call. A local variable exists from its declaration to the closing brace of the block that holds it, and a loop body is a block, so a variable declared inside it is gone by the next line after the loop.

Access is a different question: who is allowed to say the name at all. private means only this class; public means anybody. The convention the exam expects is private fields and public methods, with a private helper method whenever a piece of logic is nobody else's business. When a parameter happens to share a field's name, the parameter wins inside that method, it shadows the field, and that is where an entire class of silent bugs comes from.

public class Profile {
    private String nickname;             // scope: the whole class, life: the object

    public int longestGap(int[] days) {  // days: scope and life = this call
        int best = 0;                    // best: scope = the method body
        for (int i = 1; i < days.length; i++) {   // i: scope = the for statement
            int gap = days[i] - days[i - 1];      // gap: scope = the loop body
            if (gap > best) {
                best = gap;
            }
        }
        return best;                     // gap and i no longer exist here
    }
}

private String nickname;

public void setNickname(String nickname) {
    nickname = nickname;          // parameter = parameter
}

before setNickname: mya
after  setNickname: mya

public void setNickname(String newName) {
    nickname = newName;
}

for (int i = 1; i < days.length; i++) {
    int gap = days[i] - days[i - 1];
}
System.out.println(gap);
System.out.println(i);

Main.java:7: error: cannot find symbol
        System.out.println(gap);
                           ^
  symbol:   variable gap
  location: class Main
Main.java:8: error: cannot find symbol
        System.out.println(i);
                           ^
  symbol:   variable i
  location: class Main
2 errors

Lesson 3.8 · Unit 3 · CED topic 3.9

The this keyword

Inside any instance method, this is a reference to the object the method was called on. When a caller writes c.setText("FINAL"), then for the duration of that call this is the object c refers to. You have been using it invisibly all along: writing text inside a method is shorthand for this.text.

Saying it out loud earns its keep in three places. It disambiguates a field from a parameter that shares its name, which lets you name the parameter after the thing it actually is. It can be passed to another method, so an object can hand itself over. And this(...) as the first statement of a constructor calls a different constructor of the same class, so the real work lives in one place.

public Thermostat(String room, int target) {
    this.room = room;              // field = parameter, same name, no ambiguity
    this.target = clamp(target);
}

public Thermostat(String room) {
    this(room, 68);                // call the other constructor; MUST be first
}

public String tag() {
    return Registry.describe(this);   // hand this whole object to another method
}

public void setTextShadowed(String text) {
    text = text;              // both names mean the parameter
}

public void setTextRenamed(String newText) {
    text = newText;           // only one name in scope: the field
}

public void setTextThis(String text) {
    this.text = text;         // left side is the field, right side the parameter
}

shadowed: draft
renamed:  FINAL
this:     FINAL

public Thermostat(String room) {
    this(room, 68);
}

one: Lab 2 @ 68
two: Gym @ 85

public void setText(String text) {
    this.text = text;         // field  =  parameter
}

this.text = this.text;  ->  draft
this.text = text;       ->  FINAL

Lesson 3.9 · Unit 3 · CED topics 3.3–3.9

Designing a complete class, end to end

Question 2 of the free-response section always asks for one complete class, and it hands you a specification table of the members it wants. The workflow that earns the points is mechanical, and doing it in order is most of the battle: declare the private fields, write the constructor, write each method in the order the table lists it, then walk every row of the examples table through the code you just wrote.

That last step is the one students skip and the one that finds the bug. The examples table is not decoration: it is the scoring guide showing you its hand. If your class reproduces every row, the correctness points are already in your pocket.

public class CoffeeCard {
    private String owner;        // 1. what the table says it remembers
    private int punches;
    private int freeDrinks;

    public CoffeeCard(String owner) {    // 2. the constructor, every field set
    }

    public void buy() {                  // 3. each method, in the table's order
    }

    public int getFreeDrinks() {
    }

    public boolean redeem() {
    }

    public String toString() {           // 4. exact text, to the character
    }
}

public void buy() {
    punches++;
    if (punches == 5) {
        freeDrinks++;
        punches = 0;
    }
}

public boolean redeem() {
    if (freeDrinks > 0) {
        freeDrinks--;
        return true;
    }
    return false;
}

public String toString() {
    return owner + " " + punches + "/5, " + freeDrinks + " free";
}

new card        Maya 0/5, 0 free
after buy 1     Maya 1/5, 0 free
after buy 2     Maya 2/5, 0 free
after buy 3     Maya 3/5, 0 free
after buy 4     Maya 4/5, 0 free
after buy 5     Maya 0/5, 1 free
after buy 6     Maya 1/5, 1 free
redeem() returns true   Maya 1/5, 0 free
redeem() returns false   Maya 1/5, 0 free

after buy 5     Maya 5/5, 1 free
after buy 6     Maya 6/5, 1 free

public int punchesToNextFree() {
    return 5 - punches;
}

after 0 buys  Maya 0/5, 0 free   need 5
after 3 buys  Maya 3/5, 0 free   need 2
after 6 buys  Maya 1/5, 1 free   need 4

Lesson 3.10 · Unit 3 · CED topic 3.10 (inheritance strand)

Inheritance: writing a subclass

Unit 3 closes with the inheritance strand of the revised framework. Confirm the exact topic numbers against the published CED before release; the content below is the strand as the course outline describes it.

Inheritance is for an is-a relationship. A student ticket is a ticket, it has everything a ticket has and adds a discount, so StudentTicket extends Ticket is the right shape. Write extends and the subclass immediately has every public method of the superclass without copying a line.

What it does not get is access to the superclass's private fields. private means "this class only", and a subclass is a different class. The subclass reaches the data the same way any outsider does, through the inherited public accessors, and it hands the superclass its share of the construction work with super(...).

public class StudentTicket extends Ticket {
    private int percentOff;                 // only the NEW field is declared here

    public StudentTicket(String event, double basePrice, int percentOff) {
        super(event, basePrice);            // MUST be the first statement
        this.percentOff = percentOff;
    }

    public double getPrice() {              // overrides Ticket's version
        double full = super.getPrice();     // ask the superclass for its answer
        return full * (100 - percentOff) / 100.0;
    }
}

public double getPrice() {
    double full = super.getPrice();
    double cut = full * (100 - percentOff) / 100.0;
    return (int) (cut * 100 + 0.5) / 100.0;
}

25 off  -> stored 25  price 30.0
60 off  -> stored 50  price 20.0
-5 off  -> stored 0  price 40.0
event through the inherited accessor: Recital
Recital $30.0 (25% student)

StudentTicket.java:4: error: constructor Ticket in class Ticket cannot be applied to given types;
    public StudentTicket(String event, double basePrice, int percentOff) {
                                                                         ^
  required: String,double
  found:    no arguments
  reason: actual and formal argument lists differ in length
1 error

StudentTicket.java:11: error: call to super must be first statement in constructor
        super(event, basePrice);
             ^
1 error

StudentTicket.java:20: error: basePrice has private access in Ticket
        double full = basePrice;
                      ^
1 error

public class SeniorTicket extends Ticket {
    private double discount;

    public SeniorTicket(String event, double basePrice, double discount) {
        super(event, basePrice);
        if (discount < 0) {
            discount = 0;
        }
        if (discount > basePrice) {
            discount = basePrice;
        }
        this.discount = discount;
    }

    public double getDiscount() {
        return discount;
    }

    public double getPrice() {
        return (int) ((super.getPrice() - discount) * 100 + 0.5) / 100.0;
    }
}

discount 12.50 -> stored 12.5  price 27.5
discount 55.00 -> stored 40.0  price 0.0

Lesson 3.11 · Unit 3 · CED topic 3.10 (inheritance strand)

Overriding, polymorphism, and the Object superclass

This lesson completes the inheritance strand that closes Unit 3 in the revised framework. Confirm the exact topic numbers against the published CED before release.

An override is a subclass method with the same signature (same name, same parameter list) as one it inherited. From then on, an object of the subclass runs its own version. The power comes from what you may do with the result: a superclass reference is allowed to refer to a subclass object, so Ticket t may hold a StudentTicket, and one loop over an array of Ticket can drive objects of several different classes.

Two types are in play, and keeping them apart is the whole topic. The declared type decides which methods you are allowed to call: the compiler checks that, before the program runs. The actual type of the object decides which version runs: the JVM decides that, at run time. Every class also inherits from Object, which is where toString() and equals() come from.

Ticket[] cart = new Ticket[4];
cart[0] = new Ticket("Recital", 40.00);
cart[1] = new StudentTicket("Recital", 40.00, 25);   // legal: a StudentTicket IS a Ticket

for (int i = 0; i < cart.length; i++) {
    System.out.println(cart[i].getPrice());   // declared Ticket, runs the object's version
}

// cart[1].getPercentOff();                  // will NOT compile: Ticket has no such method
((StudentTicket) cart[1]).getPercentOff();    // cast tells the compiler what it really is

0: Recital $40.0   getPrice() = 40.0
1: Recital $30.0 (25% student)   getPrice() = 30.0
2: Playoff $18.5   getPrice() = 18.5
3: Playoff $16.65 (10% student)   getPrice() = 16.65
total 105.15

Ticket x = new Ticket("Recital", 40.00);
Ticket y = new Ticket("Recital", 40.00);
System.out.println("x.equals(y) " + x.equals(y));
System.out.println("x.equals(x) " + x.equals(x));

x.equals(y) false
x.equals(x) true

Main.java:6: error: cannot find symbol
        System.out.println(cart[1].getPercentOff());
                                  ^
  symbol:   method getPercentOff()
  location: class Ticket
1 error

System.out.println(((StudentTicket) cart[1]).getPercentOff());   // prints 25

0: Recital $40.0   getPrice() = 40.0
1: Recital $40.0 (25% student)   getPrice() = 40.0
2: Playoff $18.5   getPrice() = 18.5
3: Playoff $18.5 (10% student)   getPrice() = 18.5
total 117.0

Unit 3 review · 10 multiple-choice

Unit 3 review: Class Creation

Ten exam-style questions on a code stimulus, running from class design and constructors through references, static members, scope and this to the inheritance strand: click an option to see why it is right or wrong, and read the stimulus line by line before you choose.

Multiple choice

1. public class Student {
       private String name;
       private int points;
   
       public Student(String startName) {
           name = startName;
           points = 0;
       }
   
       public int getPoints() {
           return points;
       }
   
       public void addPoints(int earned) {
           int capped = earned;
           if (capped > 10) {
               capped = 10;
           }
           points = points + capped;
       }
   }

   // inside main, in a different class
   Student s = new Student("Ana");
   s.addPoints(7);
   s.addPoints(25);
   s.points = 40;
   System.out.println(s.getPoints());

   What is the result of compiling and running the code segment in main?

   17 40 32 The code does not compile, because points has private access in Student

   17 is what this segment would print with the fourth line deleted: addPoints(7) adds 7, and addPoints(25) is pulled down to 10 by the local variable capped, so the field holds 7 + 10. Nothing runs, though, because the program is rejected before it is ever executed.

   40 assumes s.points = 40; is a legal statement. It is not: points is declared private, so only code written inside Student may name it, and main lives in another class.

   32 is 7 + 25, the total you would get if addPoints stored earned directly. It does not, the cap is enforced through capped, and in any case the segment never compiles.

   Correct. javac reports error: points has private access in Student and stops. That is exactly what private buys you: the cap inside addPoints is the only way points can ever enter the object, so no caller can leave it in a state the class forbids.

2. public class Locker {
       private int number;
       private boolean assigned;
   
       public Locker(int startNumber) {
           number = startNumber;
           assigned = false;
       }
   
       public int getNumber() {
           return number;
       }
   }

   Which of the following statements, placed in main, causes a compile-time error?

   Locker a = new Locker(214); Locker[] all = new Locker[3]; Locker b = new Locker(); Locker c = new Locker(0);

   This matches the only constructor the class has, one int argument, so it compiles and builds a locker numbered 214. The constructor's name and parameter list are the whole contract.

   Creating an array of objects runs no constructor at all. It makes three slots holding null, which compiles cleanly; the error would come later, at run time, if you called a method through one of those null slots.

   Correct. Java supplies a free no-argument constructor only to a class that declares no constructor whatsoever. Locker declares one, so the free one is gone and javac answers constructor Locker in class Locker cannot be applied to given types; required: int, found: no arguments.

   Zero is an ordinary int argument, so this compiles and stores 0 in number. A value being unusual is not the same as a value being illegal: only a mutator or constructor that validates could reject it.

3. public class Thermostat {
       private String room;
       private int target;
   
       public Thermostat(String startRoom, int startTarget) {
           room = startRoom;
           target = clamp(startTarget);
       }
   
       public int getTarget() {
           return target;
       }
   
       public void setTarget(int degrees) {
           target = clamp(degrees);
       }
   
       private int clamp(int degrees) {
           if (degrees < 50) {
               return 50;
           }
           if (degrees > 85) {
               return 85;
           }
           return degrees;
       }
   }

   Thermostat t = new Thermostat("Lab 2", 90);
   System.out.print(t.getTarget() + " ");
   t.setTarget(45);
   System.out.print(t.getTarget() + " ");
   t.setTarget(70);
   System.out.println(t.getTarget());

   What is printed as a result of executing the code segment?

   85 50 70 90 45 70 90 50 70 85 45 70

   Correct. The first value decides it: new Thermostat("Lab 2", 90) passes 90 through clamp, which returns 85 because 90 is above the ceiling. setTarget(45) is then pulled up to the floor of 50, and 70 is inside the legal range so it is stored untouched.

   This is the output of a class that stores whatever it is handed. Both the constructor and the mutator call clamp, so 90 and 45 never reach the field unchanged: that is the whole reason the field is private.

   90 for the first value assumes the constructor assigns startTarget directly. It does not: it calls the same helper the mutator calls. Writing the rule once, in a private helper, is what keeps the two entry points from drifting apart.

   45 for the second value assumes the clamping happens only at construction. setTarget also calls clamp, and 45 is below 50, so the field becomes 50. A range stated in a specification applies at every door into the object.

4. public static void grow(Rectangle r, double factor) {
       r.setWidth(r.getWidth() * factor);
   }
   
   public static void replace(Rectangle r) {
       r = new Rectangle(1.0, 1.0);
   }
   
   public static void main(String[] args) {
       Rectangle a = new Rectangle(3.0, 4.0);
       Rectangle b = a;
       grow(a, 2.0);
       replace(a);
       System.out.println(a.getWidth() + " " + b.getWidth());
   }

   What is printed as a result of executing main?

   6.0 3.0 3.0 3.0 6.0 6.0 1.0 1.0

   This treats b = a; as copying the rectangle. It copies the reference, so a and b are two arrows pointing at one object, and a change made through either arrow is visible through the other.

   3.0 for both says grow could not reach the caller's object. It could: r is a copy of the reference, and r.setWidth(...) follows that reference to the very same rectangle a names.

   Correct. The decisive call is grow, which sets the shared object's width to 6.0 through the copied reference. replace then only repoints its own parameter r at a new rectangle, and that arrow dies at the closing brace, so both a and b still report 6.0.

   1.0 assumes replace can change which object a refers to. A method can change an object you hand it, but it can never change which object your variable points at: assigning to a parameter moves only the method's own arrow.

5. public class Ticket {
       private static int nextId = 1000;
   
       private int id;
       private String holder;
   
       public Ticket(String startHolder) {
           holder = startHolder;
           id = nextId;
           nextId++;
       }
   
       public int getId() {
           return id;
       }
   
       public static void resetIds() {
           nextId = 1000;
       }
   }

   Ticket a = new Ticket("Ana");
   Ticket b = new Ticket("Bo");
   Ticket.resetIds();
   Ticket c = new Ticket("Cy");
   System.out.println(a.getId() + " " + b.getId() + " " + c.getId());

   What is printed as a result of executing the code segment?

   1000 1001 1002 1000 1000 1000 1000 1001 1000 1001 1002 1001

   This is the output with the resetIds() call deleted. The call is there, and it assigns 1000 to the one shared counter, so the third ticket cannot receive 1002.

   All three equal would mean each object has its own copy of nextId. It is declared static, so there is exactly one copy for the whole class, and the first two tickets took different numbers out of it.

   Correct. The third value is where the answer is decided: resetIds() moved the shared counter back to 1000, so Cy's ticket takes 1000 again. It did nothing to Ana's ticket, whose id was copied out of the counter two statements earlier and has been her own instance variable ever since.

   These are the numbers you get if the constructor increments before it assigns. It assigns first (id = nextId;) and then advances the counter, so the first ticket issued gets the starting value 1000.

6. public class Profile {
       public int longestGap(int[] days) {                    // line 2
           for (int i = 1; i < days.length; i++) {            // line 3
               int best = 0;                                  // line 4
               int gap = days[i] - days[i - 1];               // line 5
               if (gap > best) {                              // line 6
                   best = gap;                                // line 7
               }
           }
           return best;                                       // line 10
       }
   }

   The method is intended to return the largest gap between consecutive values of days, but the class does not compile. Which change makes it compile and work as intended for every array of length at least 2?

   Change line 6 to if (gap >= best) { Change line 10 to return gap; Change line 4 to int best = days[0]; Delete line 4 and declare int best = 0; on the line above the for loop

   Swapping > for >= changes only which of two equal gaps wins, and the class still will not compile. The error is not about the comparison at all.

   Returning gap fails twice over: gap is also declared inside the loop body, so it is out of scope at line 10, and even in scope it would report the last gap rather than the largest one.

   Seeding the running maximum with an element is sometimes the right habit, but the declaration is still inside the loop, so it resets on every pass and is still out of scope at line 10. The class does not compile either way.

   Correct. javac says cannot find symbol: variable best at line 10, because a local variable declared inside the loop body dies at that body's closing brace. Declared above the loop, best is initialized once, survives every pass, and is still in scope at the return, on {1, 3, 8, 9, 15} the fixed method returns 6.

7. public class Label {
       private String text;
   
       public Label(String text) {
           this.text = text;
       }
   
       public String getText() {
           return text;
       }
   
       public void setText(String text) {
           text = text;                    // line 13
       }
   }

   Label c = new Label("draft");
   c.setText("FINAL");
   System.out.println(c.getText());        // prints draft

   Which of the following replacements for line 13 makes setText work as intended, so that the segment prints FINAL?

   this.text = this.text; this.text = text; text = this.text; Label.text = text;

   Both sides now name the field, so the statement copies the field onto itself and the parameter is never read. It compiles without a murmur and still prints draft: assigning a variable to itself breaks no rule of Java.

   Correct. Inside the method the bare name text means the parameter, because a parameter shadows a field of the same name; this.text always means the field of the object the method was called on. So the left side is the field, the right side is the argument, and the run prints FINAL.

   This is the original bug pointed the other way: it copies the field into the parameter, which is discarded when the method returns. The field is never written, so the output stays draft.

   Qualifying a field with the class name only works for a static field, and text is an instance variable. This one does not even compile: non-static variable text cannot be referenced from a static context.

8. public class PunchPass {
       private String owner;
       private int punches;
       private int freeRides;
   
       public PunchPass(String owner) {
           this.owner = owner;
           punches = 0;
           freeRides = 0;
       }
   
       public void buy() {
           /* to be implemented */
       }
   
       public String toString() {
           return owner + " " + punches + "/3, " + freeRides + " free";
       }
   }

   One purchase adds one punch; every third punch becomes one free ride and the punch count returns to zero. Which implementation of buy() makes a new pass print Maya 1/3, 2 free after seven calls, and behave correctly for any number of calls?

   punches++; if (punches == 3) { freeRides++; punches = 0; } punches++; if (punches % 3 == 0) { freeRides++; } punches++; if (punches >= 3) { freeRides++; } punches++; if (punches == 3) { punches = 0; freeRides = 1; }

   Correct. The fifth and the sixth calls decide it: the sixth call takes the counter to 3, which awards the second free ride and resets the counter, so the seventh call leaves exactly one punch on a pass holding two free rides; Maya 1/3, 2 free.

   The free-ride count is right, but the punch count is not: without punches = 0; the counter keeps climbing, so seven calls print Maya 7/3, 2 free. The specification says the count returns to zero, and toString makes the omission visible.

   Nothing ever resets the counter, so from the third purchase onward every call awards another free ride. Seven calls print Maya 7/3, 5 free, and a pass advertising seven punches out of three is the tell that the reset is missing.

   Assigning freeRides = 1; instead of incrementing it throws away every ride already earned, so the count can never exceed one. Seven calls print Maya 1/3, 1 free, which is right on the punches and wrong on the rides.

9. public class Ticket {
       private String event;
       private double basePrice;
   
       public Ticket(String event, double basePrice) {
           this.event = event;
           this.basePrice = basePrice;
       }
   
       public String getEvent() {
           return event;
       }
   
       public double getPrice() {
           return basePrice;
       }
   }
   
   public class StudentTicket extends Ticket {
       private int percentOff;
   
       public StudentTicket(String event, double basePrice, int percentOff) {
           super(event, basePrice);
           this.percentOff = percentOff;
       }
   
       public double getPrice() {
           /* line 9 of the subclass */
       }
   }

   Which of the following replacements for line 9 makes new StudentTicket("Recital", 40.0, 25).getPrice() return 30.0?

   return basePrice * (100 - percentOff) / 100.0; return super.getPrice() * (100 - percentOff) / 100.0; return getPrice() * (100 - percentOff) / 100.0; return super.getPrice() * percentOff / 100.0;

   A subclass is a different class, so the superclass's private fields are invisible to it no matter how plainly they are printed in the question. javac stops with basePrice has private access in Ticket.

   Correct. super.getPrice() asks the superclass for the value it alone can reach, and 40.0 times 75 divided by 100.0 is 30.0. Note that the division is by 100.0 and not 100, so no integer division rounds the answer down.

   An unqualified getPrice() inside getPrice calls this same overriding method again, with no base case to stop it. The program compiles and then dies at run time with StackOverflowError.

   This computes the discount rather than the price: 40.0 times 25 divided by 100.0 is 10.0, the money saved. Subtracting it from the base price, or multiplying by 100 - percentOff, gives the amount actually charged.

10. // Ticket declares getEvent(), getPrice() and toString().
    // StudentTicket extends Ticket, overrides getPrice() and toString(),
    // and adds public int getPercentOff().
    
    Ticket t = new StudentTicket("Recital", 40.0, 25);

    Which of the following statements, placed immediately after the declaration above, fails to compile?

    System.out.println(t.getEvent()); System.out.println(t.getPrice()); System.out.println(t.getPercentOff()); System.out.println(((StudentTicket) t).getPercentOff());

    Every Ticket has getEvent(), so the compiler is satisfied and the run prints Recital. The subclass inherited that method whole, without a line being rewritten.

    This compiles because Ticket declares getPrice(), and at run time the object's own overriding version executes, so it prints 30.0 rather than 40.0. That split is the point of polymorphism: the declared type decides what may be called, the actual object decides what runs.

    Correct. The declared type of t is Ticket, and Ticket declares no getPercentOff, so the compiler refuses with cannot find symbol: method getPercentOff(), location: variable t of type Ticket, even though the object really is a StudentTicket.

    The cast promises the compiler that the object is a StudentTicket, which it is, so this compiles and prints 25. Note the extra parentheses: you must cast first and call second, or the cast would apply to the result of the call.

Lesson 4.1 · Unit 4 · CED topic 4.1

Ethical and social issues around collecting data

Unit 4 is about programs that hold a data set rather than a handful of loose variables. The moment a program holds data about people, two questions come with it: what did it collect, and how long does it keep it? Neither is a legal technicality. A field you store is a field that can leak, be subpoenaed, be sold with the company, or be wrong about someone who has no way to correct it.

The exam asks about this in plain language: identify what personal data a program collects, say who could be harmed, and name a change that reduces the harm. The answers are concrete: drop a field, shorten a retention window, ask before collecting, or fix the sample the program was tuned on.

public class AttendanceRecord {
    private String studentId;     // needed: which student this row is about
    private String date;          // needed: which day
    private boolean present;      // needed: the fact being recorded

    // private String homeAddress;   // not needed to take attendance
    // private String photo;         // not needed to take attendance
}

public static void report(String group, int samples, int errors, int total) {
    double share = samples * 100.0 / total;
    double errorRate = errors * 100.0 / samples;
    System.out.println(group + ": " + samples + " photos, " + round1(share)
        + "% of the training set, wrong " + round1(errorRate) + "% of the time");
}

total samples = 1000
Group A: 820 photos, 82.0% of the training set, wrong 3.0% of the time
Group B: 150 photos, 15.0% of the training set, wrong 8.0% of the time
Group C: 30 photos, 3.0% of the training set, wrong 30.0% of the time

Lesson 4.2 · Unit 4 · CED topics 4.2–4.3

Data sets and creating arrays

Seven quiz scores in seven variables named quiz1 through quiz7 is not seven times the work: it is seven times the work forever, because no loop can touch them. An array is one name for a fixed-size run of same-typed boxes, numbered from 0. One name means one loop, and one loop means the average of seven scores is the same code as the average of seven hundred.

Two facts about arrays cause most of the pain. The size is fixed the instant the array is created and can never change. And the valid indexes run from 0 to length - 1, so an array of length 7 has no element 7.

int[] scores = new int[7];               // 7 boxes, each holding the default value
int[] quiz   = {88, 92, 75, 100, 64, 92, 81};   // size comes from the list

scores[0] = 88;                          // store into a box
int first = quiz[0];                     // read a box
int n = quiz.length;                     // a field, no parentheses

int[] scores = new int[7];
scores[0] = 88;
scores[1] = 92;
scores[2] = 75;
scores[3] = 100;
scores[4] = 64;
scores[5] = 92;
scores[6] = 81;

int[] quiz = {88, 92, 75, 100, 64, 92, 81};

System.out.println("scores.length = " + scores.length);
System.out.println("quiz.length   = " + quiz.length);
System.out.println("scores[0] = " + scores[0] + "   quiz[0] = " + quiz[0]);
System.out.println("scores[6] = " + scores[6] + "   quiz[6] = " + quiz[6]);
System.out.println("last element = " + quiz[quiz.length - 1]);

scores.length = 7
quiz.length   = 7
scores[0] = 88   quiz[0] = 88
scores[6] = 81   quiz[6] = 81
last element = 81

int default     0
double default  0.0
boolean default false
String default  null

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6
    at Main.main(Main.java:8)

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 6
    at Main.main(Main.java:4)

double[] data = {3.5, 7.25, 1.0, 9.75, 4.5};

Lesson 4.3 · Unit 4 · CED topic 4.4

Traversing an array

A traversal visits every element once. Java gives you two loops for it, and choosing between them is a real decision, not a style preference. The indexed for loop hands you i, so it can read the slot, write the slot, compare a slot to its neighbor, skip slots, or run backwards. The enhanced for loop hands you a copy of each value in order, which is shorter to write and impossible to get off by one.

Everything the enhanced loop cannot do follows from that one word, copy. It cannot change the array, it does not know the index, and it always starts at the beginning and runs to the end.

for (int i = 0; i < scores.length; i++) {      // indexed: i is the position
    System.out.println(i + ": " + scores[i]);
}

for (int s : scores) {                         // enhanced: s is a copy of the value
    System.out.println(s);
}

for (int i = 0; i < scores.length; i++) {
    System.out.print(scores[i] + " ");
}

for (int i = 0; i < scores.length; i += 2) {
    System.out.print(scores[i] + " ");
}

for (int s : scores) {
    s = 0;                      // assigns to the copy, not to the array
}

every element:  88 92 75 100 64 92 81 79
every other:    88 75 64 81
enhanced for:   88 92 75 100 64 92 81 79
after s = 0:    88 92 75 100 64 92 81 79 

i = 6  ->  81
i = 7  ->  79
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 8 out of bounds for length 8
    at Main.main(Main.java:5)

public static int countAbove(int[] values, int cutoff) {
    int count = 0;
    for (int v : values) {
        if (v > cutoff) {
            count++;
        }
    }
    return count;
}

Lesson 4.4 · Unit 4 · CED topic 4.5

The array algorithms the exam reuses

There is a short list of things people actually do to an array, and the exam draws from it over and over: sum and average, count the elements matching a condition, find the maximum or minimum and the index where it occurs, decide whether the array is sorted, shift the elements, and reverse in place. Learn the shapes once and you stop inventing them under time pressure.

One structural decision runs through all of them. An array parameter is a reference, so a method that writes into it changes the caller's array and usually returns void. A method that must leave the original alone builds and returns a new array instead.

public static int sum(int[] values) {
    int total = 0;                       // accumulator, before the loop
    for (int v : values) {
        total += v;                      // update on every pass
    }
    return total;                        // after the loop, not inside it
}

public static double average(int[] values) {
    if (values.length == 0) {
        return 0.0;                      // guard: no division by zero
    }
    return (double) sum(values) / values.length;
}

public static int indexOfMax(int[] values) {
    int best = values[0];
    int bestIndex = 0;
    for (int i = 1; i < values.length; i++) {
        if (values[i] > best) {
            best = values[i];
            bestIndex = i;
        }
    }
    return bestIndex;
}

sum        = 146
average    = 29.2
indexOfMax = 1
average of an empty array = 0.0

public static int[] doubled(int[] values) {       // builds a new array
    int[] result = new int[values.length];
    for (int i = 0; i < values.length; i++) {
        result[i] = values[i] * 2;
    }
    return result;
}

public static void scaleInPlace(int[] values, int factor) {   // writes into the caller's array
    for (int i = 0; i < values.length; i++) {
        values[i] = values[i] * factor;
    }
}

b 3 5 8    c 6 10 16
b 6 10 16  after scaleInPlace

public static void reverse(int[] values) {
    for (int i = 0; i < values.length / 2; i++) {
        int temp = values[i];
        values[i] = values[values.length - 1 - i];
        values[values.length - 1 - i] = temp;
    }
}

before  12 47 31 47 9
after   9 47 31 47 12 

Lesson 4.5 · Unit 4 · CED topic 4.6

Reading a data set from a text file

Real data sets do not arrive as initializer lists. They arrive as a file of lines, one record per line, fields separated by a comma. Reading one is three jobs stacked: open the file, pull off one line at a time, and cut each line into fields you can convert to numbers.

The tool is a Scanner pointed at a File instead of at System.in. Everything else you already know: indexOf and substring do the cutting, and Integer.parseInt and Double.parseDouble turn the resulting text into numbers.

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public static void load(String fileName) throws IOException {
    Scanner in = new Scanner(new File(fileName));
    while (in.hasNextLine()) {
        String line = in.nextLine();
        // cut the line into fields here
    }
    in.close();
}

Main.java:6: error: unreported exception FileNotFoundException; must be caught or declared to be thrown
        Scanner in = new Scanner(new File("stations.txt"));
                     ^
1 error

Elm St,18.4
Oak Ave,22.1

Pine Rd,31.7
Cedar Ln,27.5

while (in.hasNextLine()) {
    String line = in.nextLine();
    int comma = line.indexOf(",");
    if (comma >= 0) {
        names[count] = line.substring(0, comma);
        levels[count] = Double.parseDouble(line.substring(comma + 1));
        count++;
    }
}

pass 1: comma at 6, name = Elm St, level = 18.4
pass 2: comma at 7, name = Oak Ave, level = 22.1
skipped: no comma on this line
pass 3: comma at 7, name = Pine Rd, level = 31.7
pass 4: comma at 8, name = Cedar Ln, level = 27.5
stations read = 4
mean level = 24.93

name = Elm St
name = Oak Ave
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Range [0, -1) out of bounds for length 0
    at java.base/java.lang.String.substring(String.java:2823)
    at Main.main(Main.java:11)

String line = in.nextLine();
int colon = line.indexOf(":");
if (colon >= 0) {
    names[count] = line.substring(0, colon);
    levels[count] = Double.parseDouble(line.substring(colon + 1));
    count++;
}

Lesson 4.6 · Unit 4 · CED topic 4.7

Wrapper classes and autoboxing

An ArrayList stores objects, and int is not an object. That is the entire reason the wrapper classes exist. Integer is an object whose only job is to hold one int; Double does the same for a double. Wrapped, a number can live in a list.

Java hides the wrapping. Autoboxing converts an int to an Integer wherever an object is expected, and unboxing goes the other way wherever a primitive is expected. You write list.add(88) and int x = list.get(0); and Java inserts both conversions. This is a convenience until the day == tells you the truth about objects instead of the answer you wanted about numbers.

ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(88);                  // autobox: int 88 becomes an Integer
int first = scores.get(0);       // unbox: Integer becomes int
int total = 0;
for (int s : scores) {           // unboxes each element into s
    total += s;
}

ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(88);
scores.add(92);
scores.add(75);
scores.add(100);

int total = 0;
for (int s : scores) {
    total += s;
}
System.out.println("scores = " + scores);
System.out.println("total  = " + total);
System.out.println("mean   = " + (double) total / scores.size());

scores = [88, 92, 75, 100]
total  = 355
mean   = 88.75

Integer big1 = 1000;
Integer big2 = 1000;
Integer small1 = 100;
Integer small2 = 100;

big1 == big2       false
big1.equals(big2)  true
small1 == small2   true
small1.equals(small2) true

public static int largest(ArrayList<Integer> list) {
    int best = Integer.MIN_VALUE;
    for (int v : list) {
        if (v > best) {
            best = v;
        }
    }
    return best;
}

Lesson 4.7 · Unit 4 · CED topics 4.8–4.9

ArrayList: a list that changes size

An array's size is frozen at creation, which is fine for seven quiz scores and useless for a waiting list that grows all afternoon. An ArrayList is a list of object references that resizes itself: add makes it one longer, remove makes it one shorter, and size() always reports the current count.

The price is that you must think about shifting. Inserting at an index pushes every later element one slot right; removing at an index pulls every later element one slot left. Almost every ArrayList bug on the exam is really a shifting bug.

ArrayList<String> names = new ArrayList<String>();

names.add("Ana");            // append at the end
names.add(1, "Bo");          // insert at index 1, shifting the rest right
String s = names.get(0);     // read index 0
names.set(0, "Amir");        // replace index 0, returns the old value
String gone = names.remove(2);   // delete index 2, shifting the rest left
int n = names.size();        // a method, with parentheses

ArrayList<String> waiting = new ArrayList<String>();
waiting.add("Ana");
waiting.add("Ben");
waiting.add("Cleo");
waiting.add("Dev");

waiting.add("Eli");
waiting.add(1, "Bo");
String old = waiting.set(0, "Amir");
String gone = waiting.remove(2);
System.out.println(waiting.get(2));
waiting.add(waiting.size(), "Fay");

start  ->  [Ana, Ben, Cleo, Dev]  size 4
add("Eli")  ->  [Ana, Ben, Cleo, Dev, Eli]  size 5
add(1, "Bo")  ->  [Ana, Bo, Ben, Cleo, Dev, Eli]  size 6
set(0, "Amir") returned Ana  ->  [Amir, Bo, Ben, Cleo, Dev, Eli]  size 6
remove(2) returned Ben  ->  [Amir, Bo, Cleo, Dev, Eli]  size 5
get(2) = Cleo   (list unchanged)
add(size(), "Fay")  ->  [Amir, Bo, Cleo, Dev, Eli, Fay]  size 6

Lesson 4.8 · Unit 4 · CED topic 4.10

Traversing an ArrayList, and the removal trap

Traversing a list looks like traversing an array with two spellings changed: size() instead of length, and get(i) instead of [i]. The enhanced for loop works too, and it is the right choice whenever you are only reading.

The trap is removal. A list shifts when you delete from it, so the element that was at index i + 1 slides down into index i, and a loop that has just done i++ sails straight past it. This one bug appears on the exam every single year.

for (int i = 0; i < list.size(); i++) {     // indexed: reading, writing, or removing
    System.out.println(list.get(i));
}

for (String s : list) {                     // enhanced: reading only
    System.out.println(s);
}

for (int i = list.size() - 1; i >= 0; i--) {    // backward: the safe way to remove
    if (list.get(i).equals("")) {
        list.remove(i);
    }
}

public static void removeEmpty(ArrayList<String> list) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i).equals("")) {
            list.remove(i);              // BUG: i++ still happens
        }
    }
}

result [red, , blue, green]  size 4

for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).equals("")) {
        list.remove(i);
    }
}

int i = 0;
while (i < list.size()) {
    if (list.get(i).equals("")) {
        list.remove(i);
    } else {
        i++;
    }
}

result [red, blue, green]  size 3

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)
    at Main.main(Main.java:10)

public static void removeBelow(ArrayList<Integer> nums, int cutoff) {
    for (int i = nums.size() - 1; i >= 0; i--) {
        if (nums.get(i) < cutoff) {
            nums.remove(i);
        }
    }
}

[8, 11, 7]

Lesson 4.9 · Unit 4 · CED topic 4.11

ArrayList algorithms for data analysis

Question 3 of the free-response section is always the same shape: a class holds a private ArrayList of objects, and you write methods that walk that list, call the objects' accessor methods, and report something. Filter into a new list. Count and average the matches. Find the maximum by a field. Insert into a list you are keeping sorted. Remove everything matching a condition.

Two habits earn points on every one of them. Compare String fields with equals, never ==. And guard the empty case before you divide, returning the sentinel the question names: usually −1.0.

public class AirQualityLog {
    private ArrayList<Reading> readings;    // each Reading has getStation() and getLevel()

    public double averageFor(String station) {
        double total = 0.0;
        int count = 0;
        for (Reading r : readings) {
            if (r.getStation().equals(station)) {
                total += r.getLevel();
                count++;
            }
        }
        if (count == 0) {
            return -1.0;                    // the guard the question asks for
        }
        return total / count;
    }
}

log.add(new Reading("Elm St", 18.4));
log.add(new Reading("Oak Ave", 22.1));
log.add(new Reading("Elm St", 25.0));
log.add(new Reading("Pine Rd", 31.7));
log.add(new Reading("Elm St", 20.1));

averageFor("Elm St")  = 21.166666666666668
rounded              = 21.17
averageFor("Maple")  = -1.0
above(21.0)          = [Oak Ave 22.1, Elm St 25.0, Pine Rd 31.7]

public void insertInOrder(Reading r) {
    int i = 0;
    while (i < readings.size() && readings.get(i).getLevel() <= r.getLevel()) {
        i++;
    }
    readings.add(i, r);
}

add(2, 22.1)  ->  [12.0, 18.4, 22.1, 25.0, 31.7]

i = 0  list level 12.0 <= 5.0  false -> stop
add(0, 5.0)  ->  [5.0, 12.0, 18.4, 22.1, 25.0, 31.7]

i = 6  i == size -> stop
add(6, 40.0)  ->  [5.0, 12.0, 18.4, 22.1, 25.0, 31.7, 40.0]

public double highestAt(String station) {
    double best = -1.0;
    int count = 0;
    for (Reading r : readings) {
        if (r.getStation().equals(station)) {
            if (count == 0 || r.getLevel() > best) {
                best = r.getLevel();
            }
            count++;
        }
    }
    if (count == 0) {
        return -1.0;
    }
    return best;
}

Lesson 4.10 · Unit 4 · CED topic 4.12

Creating and accessing a 2D array

A seating chart, a game board, a spreadsheet of monthly rainfall by city: all of them are a grid, and a grid in Java is a 2D array. The honest description is that int[][] is an array whose elements are themselves int[] arrays: an array of rows.

That description answers the two questions students get wrong. grid.length is the number of rows, because the outer array holds rows. grid[0].length is the number of columns, because it is the length of one row. And every subscript is grid[row][column], in that order, always.

int[][] chart = new int[3][4];         // 3 rows, 4 columns, every cell 0

int[][] sold = {{0, 0, 1, 0},          // row 0
                {1, 1, 0, 0},          // row 1
                {0, 0, 0, 1}};         // row 2

chart[1][0] = 1;                       // row 1, column 0
int seat = sold[2][3];                 // row 2, column 3
int rows = sold.length;                // 3
int cols = sold[0].length;             // 4

int[][] chart = new int[3][4];
chart[0][2] = 1;
chart[1][0] = 1;
chart[1][1] = 1;
chart[2][3] = 1;

int[][] sold = {{0, 0, 1, 0},
                {1, 1, 0, 0},
                {0, 0, 0, 1}};

chart, built with new int[3][4]:
0 0 1 0
1 1 0 0
0 0 0 1
sold, built with an initializer list:
0 0 1 0
1 1 0 0
0 0 0 1
rows    = 3
columns = 4
seats   = 12

int[][] grid = {{14, 22, 35, 41},
                {53, 60, 78, 82},
                {91, 17, 26, 39}};

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
    at Main.main(Main.java:6)

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
    at Main.main(Main.java:6)

int[][] tally = new int[2][5];
tally[tally.length - 1][tally[0].length - 1] = 7;

Lesson 4.11 · Unit 4 · CED topic 4.13

Traversing a 2D array

Visiting every cell takes two loops, one inside the other. The outer loop picks a row, the inner loop walks that row's columns, and the inner loop runs completely for each single pass of the outer one. That is row-major order, and it is the default for a reason: it reads the grid the way you read a page.

Swap which index is on the outside and you get column-major order, which visits the same twelve cells in a different sequence. You need it whenever the question is about a column as a unit (the total for each month, the tallest value in each column), because column-major lets you finish one column before starting the next.

for (int r = 0; r < grid.length; r++) {            // row-major
    for (int c = 0; c < grid[0].length; c++) {
        System.out.print(grid[r][c] + " ");
    }
}

for (int c = 0; c < grid[0].length; c++) {         // column-major
    for (int r = 0; r < grid.length; r++) {
        System.out.print(grid[r][c] + " ");
    }
}

for (int[] row : grid) {                           // nested enhanced for: reading only
    for (int v : row) {
        System.out.print(v + " ");
    }
}

int[][] grid = {{14, 22, 35, 41},
                {53, 60, 78, 82},
                {91, 17, 26, 39}};

row-major:    14 22 35 41 53 60 78 82 91 17 26 39
column-major: 14 53 91 22 60 17 35 78 26 41 82 39
nested enhanced for: 14 22 35 41 53 60 78 82 91 17 26 39 

int colSum = 0;
for (int r = 0; r < grid.length; r++) {
    colSum += grid[r][2];              // column 2, every row
}

row 1 only:   53 60 78 82
sum of column 2 = 139
sub-rectangle rows 0-1, cols 1-2: 22 35 60 78

int borderSum = 0;
for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[0].length; c++) {
        if (r == 0 || r == grid.length - 1 || c == 0 || c == grid[0].length - 1) {
            borderSum += grid[r][c];
        }
    }
}

border cells: 14 22 35 41 53 82 91 17 26 39
border sum = 420

Lesson 4.12 · Unit 4 · CED topic 4.14

2D array algorithms

Question 4 on the exam is a 2D array question, and it draws from a short list: total each row, total each column, find the maximum and report where it is, count the cells matching a condition, build a new transformed grid, and compare a cell with its neighbors. Each one is a nested traversal with a different accumulator.

The one genuinely new skill is bounds guarding. A cell on an edge does not have four neighbors, so any code that looks at grid[r - 1][c] has to prove that row exists first.

public int[] columnTotals() {
    int[] totals = new int[mm[0].length];      // one slot per column
    for (int c = 0; c < mm[0].length; c++) {
        int total = 0;                         // resets for each column
        for (int r = 0; r < mm.length; r++) {
            total += mm[r][c];
        }
        totals[c] = total;
    }
    return totals;
}

int[][] data = {{12,  0, 34,  8},
                { 5, 21,  3, 40},
                {17,  9, 28,  2}};

rowTotal(0) = 54
rowTotal(1) = 69
rowTotal(2) = 56
totals = 34 30 65 50
countAbove(20) = 4
max = 40 at row 1, column 3

public boolean isPeak(int r, int c) {
    if (r > 0 && mm[r - 1][c] >= mm[r][c]) {
        return false;                                  // has a row above
    }
    if (r < mm.length - 1 && mm[r + 1][c] >= mm[r][c]) {
        return false;                                  // has a row below
    }
    if (c > 0 && mm[r][c - 1] >= mm[r][c]) {
        return false;                                  // has a column left
    }
    if (c < mm[0].length - 1 && mm[r][c + 1] >= mm[r][c]) {
        return false;                                  // has a column right
    }
    return true;
}

peak at (0,0) = 12
peak at (0,2) = 34
peak at (1,1) = 21
peak at (1,3) = 40
peak at (2,0) = 17
peak at (2,2) = 28
peaks = 6

public int[] rowTotals() {
    int[] totals = new int[mm.length];         // one slot per ROW
    for (int r = 0; r < mm.length; r++) {
        int total = 0;
        for (int c = 0; c < mm[0].length; c++) {
            total += mm[r][c];
        }
        totals[r] = total;
    }
    return totals;
}

Lesson 4.13 · Unit 4 · CED topics 4.15–4.16

Searching and sorting

Linear search walks the collection from the start and stops at the first match, returning its index, or −1 if it reaches the end. It works on anything (arrays, ArrayLists, sorted data or not), and on n elements it may take n comparisons.

Binary search is far faster and demands a price: the data must already be sorted. It looks at the middle element and throws away half the range on every comparison.

public static int binary(int[] values, int target) {
    int low = 0;
    int high = values.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (values[mid] == target) {
            return mid;
        }
        if (values[mid] < target) {
            low = mid + 1;          // the target is in the right half
        } else {
            high = mid - 1;         // the target is in the left half
        }
    }
    return -1;                      // low passed high: the range is empty
}

  linear used 7 comparisons
linear search for 40 -> index 6
  linear used 9 comparisons
linear search for 22 -> index -1

  start   29 10 14 37 13 25
  pass 1  10 29 14 37 13 25
  pass 2  10 13 14 37 29 25
  pass 3  10 13 14 37 29 25
  pass 4  10 13 14 25 29 37
  pass 5  10 13 14 25 29 37 

  start   29 10 14 37 13 25
  pass 1   10 29 14 37 13 25
  pass 2   10 14 29 37 13 25
  pass 3   10 14 29 37 13 25
  pass 4   10 13 14 29 37 25
  pass 5   10 13 14 25 29 37 

Lesson 4.14 · Unit 4 · CED topics 4.17–4.18

Recursion

A recursive method calls itself on a smaller version of the same problem. The digits of 4073 are the last digit, 3, plus the digits of 407, and 407 is the same kind of problem, only shorter. Keep shrinking and you reach a case so small it needs no further work: the base case.

Every recursive method needs both halves. A base case that stops, and a recursive call that is guaranteed to move toward it. Miss either and the calls pile up until the JVM gives out with StackOverflowError.

public static int digitSum(int n) {
    if (n < 10) {
        return n;                        // base case: a single digit
    }
    return n % 10 + digitSum(n / 10);    // last digit + the rest, which is smaller
}

  call digitSum(4073)
  call digitSum(407)
  call digitSum(40)
  call digitSum(4)
  digitSum(4) base case returns 4
  digitSum(40) returns 4
  digitSum(407) returns 11
  digitSum(4073) returns 14
digitSum(4073) = 14

public static int search(int[] values, int target, int low, int high) {
    if (low > high) {
        return -1;                                        // base case: empty range
    }
    int mid = (low + high) / 2;
    if (values[mid] == target) {
        return mid;                                       // base case: found
    }
    if (values[mid] < target) {
        return search(values, target, mid + 1, high);
    }
    return search(values, target, low, mid - 1);
}

public static int countDigits(int n) {
    if (n < 10) {
        return 1;                        // base case: one digit left
    }
    return 1 + countDigits(n / 10);
}

Unit 4 review · 10 multiple-choice

Unit 4 review: Data Collections

Ten exam-style questions on the unit that carries the most weight on the exam (the ethics of collecting data, arrays and their traversals, file parsing, wrapper classes, ArrayList, 2D grids, searching and sorting, and recursion) with every stated output taken from a real run of the stimulus.

Multiple choice

1. A district's attendance app records who was present each day. For every student it stores the name, the student ID, the home address, a photograph, and the GPS position of the phone at the moment the student signs in. The sign-in itself is what marks a student present; the GPS position has never been used for anything else. The team wants to reduce the harm a future data breach could do, without changing what the app is for.

   Which change does the most to reduce that harm?

   Keep collecting the GPS position, but automatically delete records more than one year old Keep every field, and require a password before staff can open the attendance screen Stop collecting the GPS position at all, since the sign-in already records presence Replace each student's name with the student ID, keeping the address, the photograph and the GPS position

   Shortening how long data is kept genuinely helps, and a retention limit is worth having. But the app still gathers a year of location history on every student, so a breach next week exposes everything collected since last year.

   Access control protects data from people who should not see it; it does nothing about a stolen database, a misconfigured backup, or a subpoena. Adding a password leaves the same pile of sensitive data sitting there.

   Correct. This is data minimization: collect only what the stated purpose requires. Presence is already established by the sign-in, so the location adds nothing to the purpose while adding a daily movement trail for every student, and data that was never collected cannot leak, be subpoenaed, or be repurposed later.

   Removing names sounds like anonymizing, but the record still carries a home address and a photograph, either of which identifies the student immediately. Swapping an identifier for another identifier is not the same as collecting less.

2. int[] scores = {4, 7, 2, 9};
   
   for (int s : scores) {
       s = s * 2;
   }
   
   scores[scores.length - 1] = 0;
   
   for (int v : scores) {
       System.out.print(v + " ");
   }

   What is printed as a result of executing the code segment?

   8 14 4 0 8 14 4 18 4 7 2 9 4 7 2 0

   This assumes the first loop doubled the array and the assignment then changed the last element. Only the second half is true: an enhanced for loop hands you a copy of each element, so writing to s never reaches the array.

   This doubles the array and also reads scores[scores.length - 1] as out of bounds or harmless. The array is unchanged by the first loop, and index length - 1 is in bounds: it is scores[scores.length] that would throw.

   This has the enhanced loop right but misses the assignment. scores[scores.length - 1] = 0; is an ordinary indexed write to element 3, and an indexed write is exactly what the enhanced loop cannot do.

   Correct. The first loop is decided on its very first pass: s = s * 2; writes 8 into a copy that is thrown away when the pass ends, and four passes later the array still holds 4, 7, 2, 9. The indexed assignment does change the array, and scores.length - 1 is 3, the last legal index, so the final element becomes 0.

3. public static int indexOfMax(int[] values) {
       int best = values[0];
       int bestIndex = 0;
       for (int i = 1; i < values.length; i++) {
           if (values[i] >= best) {                 // line 5
               best = values[i];
               bestIndex = i;
           }
       }
       return bestIndex;
   }

   The method is intended to return the smallest index at which the largest value occurs, but on {12, 47, 31, 47, 9} it returns 3. Which of the following replacements for line 5 makes the method work as intended for all arrays of length at least one?

   if (values[i] >= values[bestIndex]) { if (best > values[i]) { if (values[i] > best) { if (values[i] > values[0]) {

   This spells the champion differently but keeps the >=, so a later equal value still displaces the earlier one. Run on the same array it returns 3 again: the second 47, not the first.

   Reversing the comparison turns the method into a minimum finder. On the same array it returns 4, the index of 9, because the only element that ever beats the running value under this test is a smaller one.

   Correct. Index 3 is where the answer is decided: values[3] is 47 and best is already 47, so >= is true and the index moves, while a strict > is false and the first winner keeps the title. The method then returns 1. Match the operator to the sentence: > keeps the first maximum, >= keeps the last.

   Comparing against values[0] forever compares against the first element instead of the running maximum, so every element larger than 12 overwrites bestIndex and the method returns 3, the last such index.

4. String[] lines = {"Elm St,18", "", "Oak Ave,22", "Pine Rd,31"};
   int count = 0;
   int total = 0;
   
   for (int i = 0; i < lines.length; i++) {
       int comma = lines[i].indexOf(",");
       if (comma >= 0) {
           total += Integer.parseInt(lines[i].substring(comma + 1));
           count++;
       }
   }
   
   System.out.println(count + " " + total + " " + total / count);

   What is printed as a result of executing the code segment?

   4 71 17 3 71 23.666666666666668 3 71 23 3 71 24

   This counts the blank line as a record. On the empty string indexOf(",") returns −1, the guard comma >= 0 is false, and neither total nor count is touched, which is exactly the job that one test is doing.

   The first two numbers are right, but the third is not a double. Both total and count are int, so total / count is integer division, decided entirely by the operand types and not by what is printed.

   Correct. The second pass is where it is settled: the blank line is skipped, so three records contribute 18 + 22 + 31 = 71, and 71 / 3 is integer division, which truncates toward zero to 23 rather than rounding. Casting one operand, (double) total / count, is what would give 23.666666666666668.

   24 is what you get by rounding 23.666… to the nearest whole number. Integer division never rounds; it discards the fractional part. Rounding half up takes the (int) (x + 0.5) idiom, and nothing here does that.

5. ArrayList<Integer> nums = new ArrayList<Integer>();
   nums.add(12);
   nums.add(34);
   nums.add(56);
   nums.add(78);
   
   nums.remove(1);
   nums.add(0, 90);
   nums.set(2, 11);
   
   System.out.println(nums + " " + nums.size());

   What is printed as a result of executing the code segment?

   [90, 12, 11, 78] 4 [90, 12, 11, 56, 78] 5 [12, 56, 11, 90] 4 [90, 12, 56, 78] 4

   Correct. Follow the shifts: remove(1) deletes the element at index 1 and returns 34, leaving [12, 56, 78]; add(0, 90) pushes all three one place right, giving [90, 12, 56, 78]; and the decisive step is set(2, 11), which overwrites whatever is at index 2 after those shifts, 56, not 78.

   This reads nums.remove(1) as removing the value 1. On an ArrayList<Integer> an int argument selects the remove(int index) method, so it removes the element at index 1; you would have to write nums.remove(Integer.valueOf(1)) to remove by value.

   This treats add(0, 90) as an append. The two-argument add inserts at the given index and shifts every later element right, so 90 lands at the front; add(90) with one argument is the one that appends.

   This has the removal and the insertion right but treats set as though it only read the list. set(2, 11) replaces the element at index 2 and returns the old value, so the list really does change, though, unlike add and remove, it never changes size().

6. // nums holds [9, 4, 3, 12, 2, 6]
   
   for (int i = 0; i < nums.size(); i++) {
       if (nums.get(i) < 5) {
           nums.remove(i);
       }
   }
   
   System.out.println(nums);

   The segment is intended to remove every element less than 5. What is printed as a result of executing it?

   [9, 12, 6] [9, 3, 12, 6] [9, 3, 12, 2, 6] The code throws a ConcurrentModificationException

   This is what the author intended, and what a backward loop (for (int i = nums.size() - 1; i >= 0; i--)) actually produces on this data. The forward loop does not manage it.

   Correct. The pass at i = 1 decides it: removing the 4 slides the 3 down into index 1, but the loop has already finished with index 1 and moves on to index 2, so the 3 is never examined. The 2 at the end is caught only because it happens to have no removed neighbour before it: adjacent small values are what expose this bug.

   Nothing removed at all would mean the condition never held, but 4, 3 and 2 are all less than 5 and two of them are in fact removed. Note that nums.get(i) is unboxed to an int before the comparison, so < compares numbers, not references.

   That exception belongs to the enhanced for loop, which refuses to let you add to or remove from the collection it is walking. This is an indexed loop, so Java raises no objection: it simply produces the wrong answer, quietly.

7. // Each Reading has getStation() and getLevel().
   // The readings were built from lines of a data file, so their
   // station names are NOT string literals.
   
   public double averageFor(String station) {
       double total = 0.0;
       int count = 0;
       for (Reading r : readings) {
           if (r.getStation() == station) {            // line 9
               total += r.getLevel();
               count++;
           }
       }
       if (count == 0) {
           return -1.0;
       }
       return total / count;
   }

   The log holds Elm St readings of 18.0, 25.0 and 20.0, one Oak Ave reading and one Elm St North reading, yet averageFor("Elm St") returns −1.0. Which replacement for line 9 makes the method return 21.0 here and work for every station name?

   if (station == r.getStation()) { if (r.getStation().compareTo(station) >= 0) { if (r.getStation().indexOf(station) >= 0) { if (r.getStation().equals(station)) {

   Writing the same test backwards changes nothing: == on two String references asks whether they are the same object, and a name built at run time by substring is a different object from the literal in the call, so the count stays 0 and the method still returns −1.0.

   compareTo returns 0 for equal strings, so only == 0 is an equality test. Asking for >= 0 accepts every station at or after this one alphabetically, which here counts all five readings and returns 23.2.

   This matches any name that contains the argument, so Elm St North is counted as an Elm St reading and the method returns 23.5. Substring matching is a different question from equality, and the exam plants a name like Elm St North precisely to catch it.

   Correct. equals compares the characters rather than the references, so the three Elm St readings match whatever built their names, and (18.0 + 25.0 + 20.0) / 3 is 21.0. The empty-case guard still works: a station with no readings leaves count at 0 and returns −1.0 instead of dividing by zero.

8. int[][] grid = {{3, 8, 2, 5},
                   {4, 6, 9, 1},
                   {7, 2, 5, 3}};
   
   for (int c = 0; c < grid[0].length; c++) {
       for (int r = 0; r < grid.length; r++) {
           System.out.print(grid[r][c] + " ");
       }
   }

   What is printed as a result of executing the code segment?

   3 8 2 5 4 6 9 1 7 2 5 3 3 4 7 8 6 2 2 9 5 5 1 3 3 4 7 8 6 2 The code throws an ArrayIndexOutOfBoundsException

   That is row-major order, which is what you get when r is on the outside. Here c is on the outside, so a whole column is finished before the next column begins.

   Correct. The outer loop fixes a column and the inner loop walks the rows of it, so the first three values printed are column 0 top to bottom (3, 4, 7), and the fourth value, 8, is where the order visibly differs from row-major. All twelve cells are still visited, and the last one is still grid[2][3].

   Six values would mean the outer loop ran only twice. It runs grid[0].length times, which is 4: the number of columns, because grid[0] is one row and its length is how many entries that row has.

   Nothing is out of bounds. The bounds are correctly paired with the subscripts they control: c is tested against grid[0].length and used as the second subscript, and r is tested against grid.length and used as the first.

9. public static int[] columnTotals(int[][] grid) {
       int[] totals = new int[grid.length];          // line 2
       for (int c = 0; c < grid[0].length; c++) {
           int total = 0;
           for (int r = 0; r < grid.length; r++) {
               total += grid[r][c];
           }
           totals[c] = total;
       }
       return totals;
   }

   Called on the 3-by-4 grid {{3, 8, 2, 5}, {4, 6, 9, 1}, {7, 2, 5, 3}}, the method throws an exception. Which replacement for line 2 makes it return the column totals for every rectangular grid?

   int[] totals = new int[grid[0].length]; int[] totals = new int[grid.length * grid[0].length]; int[] totals = new int[4]; int[][] totals = new int[grid.length][grid[0].length];

   Correct. The subscript that indexes totals is c, and c runs up to grid[0].length - 1, so the array needs one slot per column. grid.length is the number of rows, 3 here, which is why totals[3] throws Index 3 out of bounds for length 3. With the fix the method returns {14, 16, 16, 9}.

   This is big enough never to throw, which is exactly why it hides the error: on the 3-by-4 grid it returns a twelve-element array, {14, 16, 16, 9, 0, 0, 0, 0, 0, 0, 0, 0}, with eight zero totals for columns that do not exist.

   Hard-coding 4 does return {14, 16, 16, 9} for this grid and then throws Index 4 out of bounds for length 4 the first time the method meets a grid with five columns. A length taken from the data is what makes the method general.

   Returning a grid where a one-dimensional array was promised does not even compile: javac reports incompatible types: int cannot be converted to int[] at the assignment and int[][] cannot be converted to int[] at the return.

10. public static int search(int[] values, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (values[mid] == target) {
            return mid;
        }
        if (values[mid] < target) {
            return search(values, target, mid + 1, high);
        }
        return search(values, target, low, mid - 1);
    }

    int[] a = {5, 9, 12, 18, 23, 27, 34, 41, 50};
    System.out.println(search(a, 7, 0, a.length - 1));

    How many calls to search are made in total, including the original call from println?

    3 4 5 9

    Three is the number of calls that actually examine a midpoint: 23 at index 4, then 9 at index 1, then 5 at index 0. Each one is too big, too big, then too small, so a fourth call is made before the method can answer.

    Correct. The fourth call is the one students forget. After the third call finds 5 < 7 it recurses with low = 1, high = 0; that call examines no element at all, hits the base case low > high, and returns −1. When a target is absent, the empty-range call is what delivers the answer, so it counts.

    Five would be right on a sixteen-element array, where the live range shrinks 16, 8, 4, 2, 1 before emptying. This array holds nine elements, so the range goes 9, 4, 1, 0 and the search is over sooner.

    Nine is the length of the array, and the number of comparisons a linear search would need to report that 7 is absent. Halving the live range on every call is the whole reason binary search is worth keeping the data sorted for.

FRQ 1 · Methods and Control Structures · 22 minutes · 9 points

Write the charge and totalCharge methods of the ParkingGarage class.

A city parking garage charges by the hour, but gives every driver a short free window at the start of a visit so that people who only drop something off are not billed. Once the free window is used up, the garage charges its hourly rate for every started hour past that window: one minute over the free window costs a full hour, sixty-one minutes over costs two hours, and so on. No matter how long a car stays, a single visit is never billed more than the daily maximum of 24.00 dollars.

At the end of each day the attendant hands in a log: the lengths of the day's visits in minutes, written as one string with single commas between the numbers and no spaces, for example 20,75,130. A day with no visits is recorded as the empty string. The class below is used to price a single visit and to price a whole day's log.

public class ParkingGarage {
    /** The dollars charged for each started hour past the free window; always positive. */
    private double hourlyRate;

    /** The number of minutes at the start of a visit that cost nothing; never negative. */
    private int freeMinutes;

    /** Constructs a garage with the given hourly rate and free window. */
    public ParkingGarage(double hourlyRate, int freeMinutes) {
        this.hourlyRate = hourlyRate;
        this.freeMinutes = freeMinutes;
    }

    /** Returns the charge, in dollars, for a single visit lasting minutes minutes,
     *  as described in part (a).
     *  Precondition: minutes >= 0
     */
    public double charge(int minutes) {
        /* to be implemented in part (a) */
    }

    /** Returns the total charge, in dollars, for every visit recorded in log,
     *  as described in part (b).
     *  Precondition: log is not null. log is either the empty string or one or more
     *                non-negative integers separated by single commas, with no spaces
     *                and no comma at either end.
     */
    public double totalCharge(String log) {
        /* to be implemented in part (b) */
    }
}

(a) Write the method charge. A visit of freeMinutes minutes or fewer is free and returns 0.0. Otherwise the garage counts the minutes past the free window and rounds them up to a whole number of started hours, so that any part of an hour is billed as a full hour, and multiplies that count by hourlyRate. If the result is greater than 24.0, the method returns 24.0 instead. Precondition: minutes >= 0. Postcondition: the returned value is at least 0.0 and at most 24.0, and neither instance variable has changed.

public double charge(int minutes)

(b) Write the method totalCharge. The method walks the string log from left to right, using indexOf to find the next comma and substring to cut off the piece in front of it, converts each piece to an int with Integer.parseInt, and adds up the charge for each visit. The empty log returns 0.0. A log with no comma in it holds exactly one visit. Precondition: log is not null and has the form described above. Postcondition: the returned value is the sum of charge applied to every visit length in log, and neither instance variable has changed. In writing totalCharge you may call charge; assume that charge works as specified regardless of what you wrote for part (a).

public double totalCharge(String log)

The table below assumes the garage was built with ParkingGarage g = new ParkingGarage(2.50, 15);. The middle column is what Java actually prints for the returned double, so a charge of two dollars fifty cents appears as 2.5.

public double charge(int minutes) {
    if (minutes <= freeMinutes) {
        return 0.0;
    }
    int extra = minutes - freeMinutes;
    int hours = extra / 60;
    if (extra % 60 > 0) {
        hours++;
    }
    double amount = hours * hourlyRate;
    if (amount > 24.0) {
        amount = 24.0;
    }
    return amount;
}

public double totalCharge(String log) {
    double total = 0.0;
    String rest = log;
    while (rest.length() > 0) {
        String piece = rest;
        int comma = rest.indexOf(",");
        if (comma >= 0) {
            piece = rest.substring(0, comma);
            rest = rest.substring(comma + 1);
        } else {
            rest = "";
        }
        total = total + charge(Integer.parseInt(piece));
    }
    return total;
}

FRQ 2 · Methods and Control Structures · 22 minutes · 9 points

Write the score and rating methods of the PasswordStrength class.

A website rates the passwords people choose and shows them a one-word verdict as they type. The rating is built from a numeric score out of 4. A password earns one point for containing at least one digit, one point for containing at least one uppercase letter, one point for containing at least one lowercase letter, and one point for being long enough. Each of those four things is worth at most one point no matter how many characters satisfy it: a password of twelve digits still earns exactly one point for digits.

"Long enough" is decided by the site, not by the class, so the minimum length is stored in the object when it is constructed. The score is then turned into the word the user sees. The class below does both jobs.

public class PasswordStrength {
    /** The smallest length that earns the length point; always positive. */
    private int minLength;

    /** Constructs a password checker with the given minimum length. */
    public PasswordStrength(int minLength) {
        this.minLength = minLength;
    }

    /** Returns the strength score of pw, a value from 0 through 4,
     *  as described in part (a).
     *  Precondition: pw is not null.
     */
    public int score(String pw) {
        /* to be implemented in part (a) */
    }

    /** Returns the one-word rating of pw, as described in part (b).
     *  Precondition: pw is not null.
     */
    public String rating(String pw) {
        /* to be implemented in part (b) */
    }
}

(a) Write the method score. Walk pw one character at a time, taking each character as the one-character string pw.substring(i, i + 1). A one-character string ch is a digit when ch.compareTo("0") >= 0 and ch.compareTo("9") <= 0; uppercase letters and lowercase letters are tested the same way, against "A" and "Z" and against "a" and "z". Award one point if at least one digit appears anywhere in pw, one point if at least one uppercase letter appears, one point if at least one lowercase letter appears, and one point if the length of pw is at least minLength. Return the total. Precondition: pw is not null; pw may be the empty string. Postcondition: the returned value is an int from 0 through 4 inclusive, and minLength has not changed.

public int score(String pw)

(b) Write the method rating. It returns "weak" when the score is 0 or 1, "fair" when the score is 2 or 3, and "strong" when the score is 4. Precondition: pw is not null. Postcondition: the returned value is exactly one of the three words above, in lowercase, and minLength has not changed. In writing rating you may call score; assume that score works as specified regardless of what you wrote for part (a).

public String rating(String pw)

The table below assumes the checker was built with PasswordStrength p = new PasswordStrength(8);.

public int score(String pw) {
    boolean hasDigit = false;
    boolean hasUpper = false;
    boolean hasLower = false;
    for (int i = 0; i < pw.length(); i++) {
        String ch = pw.substring(i, i + 1);
        if (ch.compareTo("0") >= 0 && ch.compareTo("9") <= 0) {
            hasDigit = true;
        }
        if (ch.compareTo("A") >= 0 && ch.compareTo("Z") <= 0) {
            hasUpper = true;
        }
        if (ch.compareTo("a") >= 0 && ch.compareTo("z") <= 0) {
            hasLower = true;
        }
    }
    int points = 0;
    if (hasDigit) {
        points++;
    }
    if (hasUpper) {
        points++;
    }
    if (hasLower) {
        points++;
    }
    if (pw.length() >= minLength) {
        points++;
    }
    return points;
}

public String rating(String pw) {
    int s = score(pw);
    if (s <= 1) {
        return "weak";
    }
    if (s <= 3) {
        return "fair";
    }
    return "strong";
}

FRQ 3 · Class Design · 22 minutes · 9 points

A coffee shop punch card

This is a Question 2 task: you are handed a description of an object and you write the whole class (the instance variables, the constructor, and every method) from nothing. Nobody gives you a skeleton to fill in, so the first thing a reader checks is whether the class you wrote would compile on its own.

A campus coffee shop gives every regular a paper punch card. The card belongs to one named owner. Each drink the owner buys adds one punch to the card. When the fifth punch is added the shop tears the card down: those five punches become one free drink, and the punch count goes back to zero, so the sixth purchase is punch number one on a fresh card. Free drinks pile up on the card until the owner spends them, and a free drink can only be spent if there is one there to spend.

Write the complete class CoffeeCard to model one punch card.

Instance variables. Your class needs exactly three pieces of state, and all three must be private: the owner's name as a String, the number of punches currently on the card as an int, and the number of unspent free drinks as an int. Choose the names yourself: a reader scores the encapsulation, not your spelling.

Constructor and methods. Your class must declare exactly these members, with these headers. The behavior of each one is described below.

public CoffeeCard(String owner)

public void buy()

public int getFreeDrinks()

public boolean redeem()

public String toString()

CoffeeCard(String owner): creates a brand-new card for the given owner, with zero punches and zero free drinks. Precondition: owner is not null.

buy(): records one purchase. It adds one punch to the card. If that punch is the fifth one, it instead converts the five punches into one more free drink and sets the punch count back to 0. It returns nothing.

getFreeDrinks(): returns the number of unspent free drinks on the card. It must not change the card.

redeem(): spends one free drink. If the card has at least one unspent free drink, redeem removes one from the card and returns true. If the card has no free drinks, it changes nothing at all and returns false. The punch count is never touched by redeem.

toString(): returns the owner's name, a space, the punch count, a slash, the digit 5, a comma, a space, the free-drink count, a space, and the word free. For a card belonging to Maya with one punch and one free drink that string is exactly Maya 1/5, 1 free.

The table traces one card from the moment it is created through six calls to buy and two calls to redeem. Every value in it comes from running the class. The punch count is the number before the slash.

public class CoffeeCard {
    private String owner;
    private int punches;
    private int freeDrinks;

    public CoffeeCard(String owner) {
        this.owner = owner;
        punches = 0;
        freeDrinks = 0;
    }

    public void buy() {
        punches++;
        if (punches == 5) {
            freeDrinks++;
            punches = 0;
        }
    }

    public int getFreeDrinks() {
        return freeDrinks;
    }

    public boolean redeem() {
        if (freeDrinks > 0) {
            freeDrinks--;
            return true;
        }
        return false;
    }

    public String toString() {
        return owner + " " + punches + "/5, " + freeDrinks + " free";
    }
}

Maya 0/5, 0 free
Maya 1/5, 0 free
Maya 2/5, 0 free
Maya 3/5, 0 free
Maya 4/5, 0 free
Maya 0/5, 1 free
Maya 1/5, 1 free
true
Maya 1/5, 0 free
false
Maya 1/5, 0 free

FRQ 4 · Class Design · 22 minutes · 9 points

A student ticket that discounts a price

This is the other shape Question 2 takes: a working class is given to you, and you write a subclass that reuses it. The whole question turns on one fact: a subclass inherits the superclass's methods but cannot see its private fields. Everything the subclass needs to know about the price it has to ask for through a method.

A box office sells tickets to campus events. Every ticket knows its event and its base price. Students get a percentage off that base price, but the box office caps the student discount at 50 percent, and a negative discount makes no sense, so a percentage below 0 is treated as 0 and a percentage above 50 is treated as 50. The discounted price is charged to the nearest cent.

The Ticket class below is given to you and is already written. You may not change it.

public class Ticket {
    private String event;
    private double basePrice;

    public Ticket(String event, double basePrice) {
        this.event = event;
        this.basePrice = basePrice;
    }

    public double getPrice() {
        return basePrice;
    }

    public String getEvent() {
        return event;
    }

    public String toString() {
        return event + " ticket, $" + getPrice();
    }
}

Write the complete class StudentTicket, a subclass of Ticket.

Instance variable. StudentTicket adds exactly one piece of state of its own, and it must be private: an int holding the discount percentage after it has been capped. It must not redeclare the event or the base price: those already exist in Ticket.

Constructor and methods. Your class must declare exactly these members, with these headers.

public StudentTicket(String event, double basePrice, int percentOff)

public double getPrice()

public int getPercentOff()

public String toString()

StudentTicket(String event, double basePrice, int percentOff): passes event and basePrice to the superclass constructor with a call to super, which must be the first statement in the constructor body. It then stores percentOff after capping it into the range 0 through 50: a value below 0 is stored as 0, a value above 50 is stored as 50, and a value already in range is stored unchanged. Precondition: basePrice is at least 0.

getPrice(): overrides the inherited method. It returns the superclass price reduced by the stored percentage, rounded to the nearest cent. Round with the (int)(x * 100 + 0.5) / 100.0 idiom; Math.round is outside the AP Java subset. The base price is private in Ticket, so the only way to read it is super.getPrice().

getPercentOff(): returns the capped percentage that was stored, not the raw argument the caller passed in.

toString(): overrides the inherited method. It returns whatever super.toString() returns, followed by a space, an opening parenthesis, the stored percentage, and the text % student discount).

Every value in the table below was produced by running the two classes. Note the third and fourth rows: because Ticket.toString calls getPrice(), and your override replaces it, super.toString() already reports the discounted price.

public class StudentTicket extends Ticket {
    private int percentOff;

    public StudentTicket(String event, double basePrice, int percentOff) {
        super(event, basePrice);
        if (percentOff < 0) {
            percentOff = 0;
        }
        if (percentOff > 50) {
            percentOff = 50;
        }
        this.percentOff = percentOff;
    }

    public double getPrice() {
        double reduced = super.getPrice() * (100 - percentOff) / 100.0;
        return (int) (reduced * 100 + 0.5) / 100.0;
    }

    public int getPercentOff() {
        return percentOff;
    }

    public String toString() {
        return super.toString() + " (" + percentOff + "% student discount)";
    }
}

30.0
Recital ticket, $30.0 (25% student discount)
50
20.0
Recital ticket, $20.0 (50% student discount)
0
40.0
Recital ticket, $40.0 (0% student discount)
16.99
Jazz Night ticket, $16.99 (15% student discount)

FRQ 5 · Data Analysis with ArrayList · 22 minutes · 9 points

Averaging and pruning an air-quality log

A regional agency records fine-particulate readings from several monitoring stations. Each reading knows which station recorded it, which day of the study it belongs to, and the PM2.5 concentration measured, in micrograms per cubic meter. Readings arrive in the order they are taken, and the agency keeps them in that order.

The Reading class below is given to you. You will not write any part of it; you will only call its accessor methods.

public class Reading
{
    /** The name of the station that recorded this reading; never null. */
    private String station;

    /** The day of the study on which this reading was taken; 1 is the first day. */
    private int day;

    /** The PM2.5 concentration of this reading, in micrograms per cubic meter. */
    private double pm25;

    public Reading(String s, int d, double p)
    {
        station = s;
        day = d;
        pm25 = p;
    }

    /** @return the name of the station that recorded this reading */
    public String getStation()
    {
        return station;
    }

    /** @return the day of the study on which this reading was taken */
    public int getDay()
    {
        return day;
    }

    /** @return the PM2.5 concentration of this reading */
    public double getPm25()
    {
        return pm25;
    }
}

The class AirQualityLog stores the readings collected so far. You will write two of its methods. The declarations of the two methods, with their preconditions and postconditions, are shown below.

public class AirQualityLog
{
    /** The readings in this log, in the order they were recorded.
     *  Guaranteed not to be null, but it may be empty.
     */
    private ArrayList<Reading> readings;

    /** Returns the mean of the pm25 values of all readings in this log that were
     *  recorded at station, or -1.0 if this log contains no reading from station.
     *  Precondition: station is not null.
     *  Postcondition: readings is unchanged.
     */
    public double averageFor(String station)
    {  /* to be implemented in part (a) */  }

    /** Removes from this log every reading whose pm25 value is strictly less than
     *  limit, and returns the number of readings removed.
     *  Postcondition: the readings that were not removed appear in readings in the
     *                 same relative order in which they appeared before the call.
     */
    public int removeBelow(double limit)
    {  /* to be implemented in part (b) */  }

    // There may be instance variables, constructors, and methods that are not shown.
}

Part (a). Write the method averageFor. The method returns the mean of the pm25 values of every reading in readings whose station name is equal to station. If no reading in the log came from that station, and in particular if readings is empty, the method returns -1.0. The log itself must not change. Write the complete method, beginning with the header public double averageFor(String station).

Part (b). Write the method removeBelow. The method removes from readings every reading whose pm25 value is strictly less than limit and returns how many readings it removed. Readings whose value is exactly limit stay. Every reading that is not removed must still be in readings afterwards, in its original relative order. Write the complete method, beginning with the header public int removeBelow(double limit).

In the examples below, log is an AirQualityLog whose readings list holds these six readings, in this order: North/day 1/12.0, South/day 1/22.0, North/day 2/25.0, East/day 2/9.0, North/day 3/18.5, South/day 3/14.0. Each row starts from that original list.

public double averageFor(String station)
{
    double sum = 0.0;
    int count = 0;
    for (int i = 0; i < readings.size(); i++)
    {
        Reading r = readings.get(i);
        if (r.getStation().equals(station))
        {
            sum += r.getPm25();
            count++;
        }
    }
    if (count == 0)
    {
        return -1.0;
    }
    return sum / count;
}

public int removeBelow(double limit)
{
    int removed = 0;
    for (int i = readings.size() - 1; i >= 0; i--)
    {
        if (readings.get(i).getPm25() < limit)
        {
            readings.remove(i);
            removed++;
        }
    }
    return removed;
}

averageFor("North") -> 18.5
averageFor("South") -> 18.0
averageFor("East")  -> 9.0
averageFor("West")  -> -1.0
removeBelow(15.0) -> 3
readings after    -> [South/1/22.0, North/2/25.0, North/3/18.5]
removeBelow(30.0) -> 6
readings after    -> []
removeBelow(5.0)  -> 0
readings after    -> [North/1/12.0, South/1/22.0, North/2/25.0, East/2/9.0, North/3/18.5, South/3/14.0]

FRQ 6 · Data Analysis with ArrayList · 22 minutes · 9 points

Keeping a delivery log sorted and reporting the late orders

A delivery service records each completed order together with the number of minutes the delivery took. The dispatcher wants the log kept in increasing order of delivery time at all times, so that the slowest deliveries are always at the end and no sorting pass is ever needed, and wants to be able to pull the names of the customers whose orders ran long.

The Order class below is given to you. You will not write any part of it; you will only call its accessor methods.

public class Order
{
    /** The name of the customer who placed this order; never null. */
    private String customer;

    /** The delivery time of this order, in minutes; never negative. */
    private int minutes;

    public Order(String c, int m)
    {
        customer = c;
        minutes = m;
    }

    /** @return the name of the customer who placed this order */
    public String getCustomer()
    {
        return customer;
    }

    /** @return the delivery time of this order, in minutes */
    public int getMinutes()
    {
        return minutes;
    }
}

The class DeliveryLog stores the completed orders. Its list is always kept in increasing order of getMinutes(). You will write two of its methods; their declarations, preconditions and postconditions are shown below.

public class DeliveryLog
{
    /** The completed orders, in increasing order of getMinutes().
     *  Guaranteed not to be null, but it may be empty.
     */
    private ArrayList<Order> orders;

    /** Inserts o into orders so that orders remains in increasing order of
     *  getMinutes(), placing o after every order already in the list whose
     *  minutes are equal to o.getMinutes(), and returns the index at which
     *  o was inserted.
     *  Precondition: o is not null; orders is in increasing order of getMinutes().
     *  Postcondition: orders has one more element than before, it is still in
     *                 increasing order of getMinutes(), and the returned index
     *                 is the position of o in orders.
     */
    public int insertInOrder(Order o)
    {  /* to be implemented in part (a) */  }

    /** Returns a new list containing the customer name of every order in this log
     *  whose delivery time is strictly greater than limit, in the order those
     *  orders appear in orders, keeping repeated names.
     *  Postcondition: orders is unchanged; an empty list is returned when no
     *                 order took more than limit minutes.
     */
    public ArrayList<String> lateCustomers(int limit)
    {  /* to be implemented in part (b) */  }

    // There may be instance variables, constructors, and methods that are not shown.
}

Part (a). Write the method insertInOrder. The method puts o into orders at the one position that keeps the list in increasing order of getMinutes(), and it returns the index where o ended up. When the list already contains one or more orders with exactly the same delivery time, o goes after all of them. Inserting into an empty log puts o at index 0 and returns 0; inserting an order slower than every order already in the log appends it to the end. Write the complete method, beginning with the header public int insertInOrder(Order o).

Part (b). Write the method lateCustomers. The method returns a new ArrayList<String> holding the customer name of every order whose delivery time is strictly greater than limit, in the same order those orders appear in orders. A customer who has two late orders appears twice. An order that took exactly limit minutes is not late. If no order qualifies, the method returns an empty list, not null. The log itself must not change. Write the complete method, beginning with the header public ArrayList<String> lateCustomers(int limit).

In the examples below, log is a DeliveryLog whose orders list starts as Ortiz/22, Chen/35, Ortiz/41, and empty is a DeliveryLog whose orders list is empty. Each call on log is made on the list the row above it left behind.

public int insertInOrder(Order o)
{
    int index = 0;
    while (index < orders.size() && orders.get(index).getMinutes() <= o.getMinutes())
    {
        index++;
    }
    orders.add(index, o);
    return index;
}

public ArrayList<String> lateCustomers(int limit)
{
    ArrayList<String> names = new ArrayList<String>();
    for (int i = 0; i < orders.size(); i++)
    {
        Order o = orders.get(i);
        if (o.getMinutes() > limit)
        {
            names.add(o.getCustomer());
        }
    }
    return names;
}

start                       -> [Ortiz/22, Chen/35, Ortiz/41]
insertInOrder(Chen/35)      -> 2
orders now                  -> [Ortiz/22, Chen/35, Chen/35, Ortiz/41]
insertInOrder(Nawaz/50)     -> 4
orders now                  -> [Ortiz/22, Chen/35, Chen/35, Ortiz/41, Nawaz/50]
lateCustomers(30)           -> [Chen, Chen, Ortiz, Nawaz]
lateCustomers(41)           -> [Nawaz]
lateCustomers(90)           -> []
orders unchanged by (b)     -> [Ortiz/22, Chen/35, Chen/35, Ortiz/41, Nawaz/50]
empty insertInOrder(Pike/15)-> 0
empty orders now            -> [Pike/15]

FRQ 7 · 2D Array · 22 minutes · 9 points

Seating chart

A campus lecture hall tracks its seats in a rectangular grid. The class SeatingChart stores that grid in a private two-dimensional array of int called seats, where seats[r][c] is 0 when the seat in row r, column c is empty and 1 when it is taken. Row 0 is the front row and column 0 is the left-hand aisle. The grid is rectangular: every row has the same number of columns, so seats.length is the number of rows and seats[0].length is the number of columns in each row. The constructor is written for you.

The registrar needs two pieces of information. First, when a block of seats is reserved for a visiting group, the office needs to know how many seats inside that block are already taken. Second, when a late student arrives, the usher needs to know which row has the most room. You will write the two methods that answer those questions. Both methods read the grid; neither one changes it.

public class SeatingChart
{
    /** seats[r][c] is 0 when the seat in row r, column c is empty
     *  and 1 when that seat is taken.
     */
    private int[][] seats;

    /** Constructs a seating chart from initial.
     *  Precondition: initial is rectangular and contains only 0 and 1.
     */
    public SeatingChart(int[][] initial)
    {
        seats = initial;
    }

    /** Returns the number of taken seats inside the rectangle whose opposite
     *  corners are (startRow, startCol) and (endRow, endCol), counting both
     *  corners and every seat between them.
     *  Precondition: 0 <= startRow <= endRow < seats.length
     *                0 <= startCol <= endCol < seats[0].length
     *  Postcondition: seats is not changed.
     */
    public int countTaken(int startRow, int startCol, int endRow, int endCol)
    {
        /* to be implemented in part (a) */
    }

    /** Returns the index of the row that holds the most empty seats.
     *  If two or more rows tie, the smallest such index is returned.
     *  Returns -1 if seats has no rows.
     *  Postcondition: seats is not changed.
     */
    public int emptiestRow()
    {
        /* to be implemented in part (b) */
    }

    // There may be instance variables, constructors, and methods that are not shown.
}

The examples below all refer to a SeatingChart named hall built from this 4-by-5 grid. The row and column labels are the indexes, not part of the data.

Part (a). Write the method countTaken. It returns how many taken seats lie inside the rectangle whose opposite corners are row startRow column startCol and row endRow column endCol. Both corners count, and so does every seat between them, so a rectangle from row 1 to row 2 covers rows 1 and 2. Precondition: all four values are legal indexes, startRow is at most endRow, and startCol is at most endCol. Postcondition: seats is unchanged. Complete the method below.

public int countTaken(int startRow, int startCol, int endRow, int endCol)

Part (b). Write the method emptiestRow. It returns the index of the row holding the most empty seats. If two or more rows are tied for the most empty seats, return the smallest of those indexes. If the chart has no rows at all, return -1. There is no precondition on the number of rows, so seats.length may be 0; you may assume that when there is at least one row the grid is rectangular. Postcondition: seats is unchanged. Complete the method below.

public int emptiestRow()

public int countTaken(int startRow, int startCol, int endRow, int endCol)
{
    int count = 0;
    for (int r = startRow; r <= endRow; r++)
    {
        for (int c = startCol; c <= endCol; c++)
        {
            if (seats[r][c] == 1)
            {
                count++;
            }
        }
    }
    return count;
}

public int emptiestRow()
{
    if (seats.length == 0)
    {
        return -1;
    }
    int best = 0;
    int mostEmpty = -1;
    for (int r = 0; r < seats.length; r++)
    {
        int empty = 0;
        for (int c = 0; c < seats[0].length; c++)
        {
            if (seats[r][c] == 0)
            {
                empty++;
            }
        }
        if (empty > mostEmpty)
        {
            mostEmpty = empty;
            best = r;
        }
    }
    return best;
}

countTaken(1, 1, 2, 3) -> 4
countTaken(0, 0, 3, 4) -> 12
countTaken(0, 2, 0, 2) -> 1
countTaken(3, 0, 3, 4) -> 4
emptiestRow()          -> 2
-- empty seats per row --
row 0: 2 empty
row 1: 2 empty
row 2: 3 empty
row 3: 1 empty
tie chart 1 0 / 0 1 / 1 1, emptiestRow() -> 0
empty chart, emptiestRow() -> -1

FRQ 8 · 2D Array · 22 minutes · 9 points

Rainfall grid

A weather station logs its rainfall readings in a rectangular grid. The class RainfallGrid stores that grid in a private two-dimensional array of int called data. Each row is one week and each column is one of the fixed collection days in that week, so data[r][c] is the rainfall recorded in week r on collection day c, measured in whole millimetres and never negative. The grid is rectangular: data.length is the number of weeks and data[0].length is the number of collection days per week. The constructor is written for you.

The station's report needs two summaries. The first is a day-by-day total: how much rain fell on collection day 0 across all the weeks, on day 1 across all the weeks, and so on. That summary is a one-dimensional array with one slot per column, which means the traversal has to run down a column before it moves to the next one. The second summary counts peaks: cells that are strictly wetter than every neighbor directly above, below, left and right of them. A cell in the top row has no neighbor above it, a cell in the left column has none to its left, and a corner cell has only two neighbors: a peak is judged only against the neighbors it actually has.

public class RainfallGrid
{
    /** data[r][c] is the rainfall recorded in week r on collection day c.
     *  Every value is at least 0.
     */
    private int[][] data;

    /** Constructs a rainfall grid from initial.
     *  Precondition: initial is rectangular and contains only values >= 0.
     */
    public RainfallGrid(int[][] initial)
    {
        data = initial;
    }

    /** Returns a new one-dimensional array whose element at index c is the
     *  sum of all the values in column c of data.
     *  Returns an array of length 0 when data has no rows.
     *  Postcondition: data is not changed.
     */
    public int[] columnTotals()
    {
        /* to be implemented in part (a) */
    }

    /** Returns the number of cells of data whose value is strictly greater
     *  than the value of every neighbour that exists directly above, below,
     *  to the left of, and to the right of that cell. Diagonal cells are not
     *  neighbours. A cell on an edge or in a corner simply has fewer
     *  neighbours to beat.
     *  Postcondition: data is not changed.
     */
    public int countPeaks()
    {
        /* to be implemented in part (b) */
    }

    // There may be instance variables, constructors, and methods that are not shown.
}

The examples below refer to a RainfallGrid named season built from this 3-by-4 grid, and to three smaller grids: oneWeek, which holds the single row 5 2 9; flat, which holds the two rows 4 4 and 1 2; and blank, which has no rows at all. The row and column labels are the indexes, not part of the data.