# Building Java Programs, 5th Edition Self-Check Solutions

NOTE: Answers to self-check problems are posted publicly on our web site and are accessible to students. This means that self-check problems generally should not be assigned as graded homework, because the students can easily find solutions for all of them. If you want to assign BJP end-of-chapter problems as homework, please consider using our Exercises or Programming Projects, the solutions to which are not publicly posted (but are available to instructors only by request).

## Chapter 1

1. Computers use binary numbers because it's easier to build electronic devices reliably if they only have to distinguish between two electric states.
1. 6 = 110
2. 44 = 101100
3. 72 = 1001000
4. 131 = 10000011
1. 100 = 4
2. 1011 = 11
3. 101010 = 42
4. 1001110 = 78
1. Make the cookie batter:
• Mix the dry ingredients.
• Cream the butter and sugar.
• Beat in the eggs.
• Stir in the dry ingredients.
2. Bake the cookies:
• Set the oven for the appropriate temperature.
• Set the timer.
• Place the cookies into the oven.
• Allow the cookies to bake.
3. Add frosting and sprinkles:
• Mix the ingredients for the frosting.
• Spread frosting and sprinkles onto the cookies.
2. `MyProgram.java` is a source code file typed by the programmer, and `MyProgram.class` is a compiled executable class file that is run by the computer.
3. The legal identifiers shown are `println`, `AnnualSalary`, `ABC`, `sum_of_data`, `_average`, and `B4`.
4. d. `System.out.println("Hello, world!");`
5. Output of statements:

```"Quotes"
Slashes \//
How '"confounding' "\" it is!
```
6. Output of statements:

```name    age     height
Archie  17      5'9"
Betty   17      5'6"
Jughead 16      6'
```
7. Output of statements:

```Shaq is 7'1
The string "" is an empty message.
\'""
```
8. Output of statements:

```       a       b       c
\\
'
"""
C:
in      he downward spiral
```
9. Output of statements:

```Dear "DoubleSlash" magazine,

Your publication confuses me.  Is it
a \\ slash or a //// slash?

Sincerely,
Susan "Suzy" Smith
```
10. `println` statements to produce desired output:

```System.out.println("\"Several slashes are sometimes seen,\"");
System.out.println("said Sally. \"I've said so.\" See?");
System.out.println("\\ / \\\\ // \\\\\\ ///");
```
11. `println` statements to produce desired output:

```System.out.println("This is a test of your");
System.out.println("knowledge of \"quotes\" used");
System.out.println("in 'string literals.'");
System.out.println();
System.out.println("You're bound to \"get it right\"");
System.out.println("if you read the section on");
System.out.println("''quotes.''");
```
12. `println` statement to produce desired output:

```System.out.println("/ \\ // \\\\ /// \\\\\\");
```
13. Equivalent code without `System.out.print` statements:

```System.out.println("Twas brillig and the ");
System.out.println("  slithy toves did gyre and");
System.out.println("gimble");
System.out.println();
System.out.println("in the wabe.");
```
14. Output of `Commentary` program:

```some lines of code
have // characters on them
which means
lines can also
have /* and */ characters
of comment.
```
15. Mistakes in `MyProgram` program:

1. line 1: The keyword `class` is missing.
2. line 3: A semicolon is missing.
3. line 4: The word `Println` should not be capitalized.
16. Mistakes in `SecretMessage` program:

1. line 2: The keyword `void` is missing.
2. line 2: The word `string` should be capitalized.
3. line 4: A closing `"` mark is missing.
4. line 5: A closing `}` brace is missing.
17. Mistakes in `FamousSpeech` program:

1. line 1: A `{` brace is missing.
2. line 2: The word `args` is missing.
3. line 8: The comment on lines 8-10 accidentally comments out lines 9-10 of the program. Using `//` comments would fix the problem.
4. line 11: A closing right parenthesis `)` is missing.
18. b. `public static void example() {`
19. Output of `Tricky` program:

```This is message1.
This is message2.
This is message1.
Done with message2.
Done with main.
```
20. Output of `Strange` program:

```Inside first method
Inside third method
Inside first method
Inside second method
Inside first method
Inside second method
Inside first method
Inside third method
Inside first method
Inside second method
Inside first method
```
21. Output of `Strange2` program:

```Inside first method
Inside first method
Inside second method
Inside first method
Inside third method
Inside second method
Inside first method
Inside first method
Inside second method
Inside first method
Inside third method
```
22. Output of `Strange3` program:

```Inside second method
Inside first method
Inside first method
Inside second method
Inside first method
Inside third method
Inside first method
Inside second method
Inside first method
```
23. Output of `Confusing` program:

```I am method 1.
I am method 1.
I am method 2.
I am method 3.
I am method 1.
I am method 1.
I am method 2.
I am method 1.
I am method 2.
I am method 3.
I am method 1.
```
24. Output of `Confusing2` program:

```I am method 1.
I am method 1.
I am method 1.
I am method 2.
I am method 3.
I am method 1.
I am method 2.
I am method 1.
I am method 1.
I am method 2.
I am method 3.
```
25. Output of `Confusing3` program:

```I am method 1.
I am method 2.
I am method 1.
I am method 1.
I am method 2.
I am method 3.
I am method 1.
I am method 1.
I am method 2.
```
26. Mistakes in `LotsOfErrors` program:

1. line 1: The class name should be `LotsOfErrors` (no space).
2. line 2: The word `void` should appear after `static`.
3. line 2: `String` should be `String[]`.
4. line 3: `System.println` should be `System.out.println`.
5. line 3: `"Hello, world!)` should be `"Hello, world!")`.
6. line 4: There should be a semicolon after `message()`.
7. line 7: There should be a `()` after message.
8. line 8: `System.out println` should be `System.out.println`.
9. line 8: `cannot";` should be `cannot");`.
10. line 9: The phrase `"errors"` cannot appear inside a `String`. `'errors'` or `\"errors\"` would work.
11. line 11: There should be a closing `}` brace.
27. Mistakes in `Example` program:

1. Syntax error: The program would not compile because its class name (`Demonstration`) would not match its file name (`Example.java`).
2. Different program output: The program would not run because Java would be unable to find the `main` method.
3. Different program output: There would now be a blank line between the two printed messages.
4. Syntax error: The program would not compile because the `main` method would be calling a method (`displayRule`) that no longer existed.
5. No effect: The program would still compile successfully and produce the same output.
6. Different program output: The output would now have no line break between "The first rule" and "of Java Club is," in its output.
28. Reformatted version of `GiveAdvice` program:

```// Suzy Student, Fall 2048
// This program prints a message about proper formatting
// of Java programs.
public class GiveAdvice {
public static void main(String[] args) {
System.out.println("Programs can be easy or");
System.out.println("difficult to read, depending");
System.out.println("upon their format.");
System.out.println();
System.out.println("Everyone, including yourself,");
System.out.println("will be happier if you choose");
System.out.println("to format your programs.");
}
}
```
29. Reformatted version of `Messy` program:

```// Suzy Student, Fall 2048
// This program prints a cautionary message about messy formatting
// of Java programs.
public class Messy {
public static void main(String[] args) {
message();
System.out.println();
message();
}

public static void message() {
System.out.println("I really wish that");
System.out.println("I had formatted my source");
System.out.println("code correctly!");
}
}
```

## Chapter 2

1. Legal `int` literals: `22`, `-1`, and `-6875309`
2. d. `11`
3. Results of `int` expressions:

1. `8`
2. `11`
3. `6`
4. `4`
5. `33`
6. `-16`
7. `6.4`
8. `6`
9. `30`
10. `1`
11. `7`
12. `5`
13. `2`
14. `18`
15. `3`
16. `4`
17. `4`
18. `15`
19. `8`
20. `1`
4. Results of `double` expressions:

1. `9.0`
2. `9.6`
3. `2.2`
4. `6.0`
5. `6.0`
6. `8.0`
7. `1.25`
8. `3.0`
9. `3.0`
10. `3.0`
11. `5.0`
12. `6.4`
13. `37.0`
14. `8.5`
15. `9.6`
16. `4.0`
17. `4.8`
5. Results of `String` expressions:

1. `11`
2. `"2 + 2 34"`
3. `"2 2 + 3 4"`
4. `"7 2 + 2"`
5. `"2 + 2 7"`
6. `"(2 + 2) 7"`
7. `"hello 34 8"`
6. c. `double grade = 4.0;`
7. ```int age;
String gender;
double height;
int weight;
```
8. ```String year;
int numberOfCourses;
double gpa;
```
9. Last digit: `number % 10`
10. Mistakes in `Oops2` program:

1. line 4: There should be a `+` between `is` and `x`.
2. line 4: Variable `x` has not yet been given any value.
3. line 6: Variable `x` is being redeclared. The word `int` should be omitted.
4. line 6: Variable `x` is being given a value of the wrong type (`double`).
5. line 7: The `+ x` should be outside the quotes.
6. line 10: The word `int` should be omitted.
7. line 11: The word `and` should be surrounded by quotes.
• Second-to-last digit: `(number % 100) / 10` or `(number / 10) % 10`
• Third-to-last digit: `(number % 1000) / 100` or `(number / 100) % 10`
11. d. `10`
12. Values of `a`, `b`, and `c` after the code:

```a: 6
b: 9
c: 16
```
13. Values of `first` and `second` after the code:

```first: 19
second: 8
```
The code swaps the values of the variables `first` and `second`.
14. Rewritten shortened version of the code:

```int first = 8, second = 19;
first += second;
second = first - second;
first -= second;
```
15. Values of `i`, `j`, and `k` after the code:

```i: 4
j: 2
k: 1
```
16. Output of code:

```46
36
23
13
```
17. Expression to compute `y` while using `*` only four times:

`double y = x * (x * (x * (x * 12.3 - 9.1) + 19.3) - 4.6) + 34.2;`
18. Version of `ComputePay` program that uses variables to avoid redundant expressions:

```public class ComputePay {
public static void main(String[] args) {
// Calculate my pay at work, based on how many hours I worked each day
int totalHours = 4 + 5 + 8 + 4;
double salary = 8.75;
double pay = totalHours * salary;
double taxRate = 0.20;
double taxesOwed = pay * taxRate;

System.out.println("My total hours worked:");
System.out.println(totalHours);
System.out.println("My hourly salary:");
System.out.println("\$" + salary);
System.out.println("My total pay:");
System.out.println(pay);
System.out.println("My taxes owed:");
System.out.println(taxesOwed);
}
}
```
19. ```// This program computes the total amount owed for a meal,
// assuming 8% tax and a 15% tip.
public class Receipt {
public static void main(String[] args) {
int subtotal = 38 + 40 + 30;
System.out.println("Subtotal:");
System.out.println(subtotal);

double tax = subtotal * .08;
System.out.println("Tax:");
System.out.println(tax);

double tip = subtotal * .15;
System.out.println("Tip:");
System.out.println(tip);

double total = subtotal + tax + tip;
System.out.println("Total:");
System.out.println(total);
}
}
```
20. ```public class Count2 {
public static void main(String[] args) {
for (int i = 1; i <= 4; i++) {
System.out.println("2 times " + i + " = " + (2 * i));
}
}
}
```
1. `2 * count`
2. `15 * count - 11`
3. `-10 * count + 40`
4. `4 * count - 11`
5. `-3 * count + 100`
21. ```for (int i = 1; i <= 6; i++) {
// your code here
System.out.println(18 * i - 22);
}
```
22. Output of `oddStuff` method:

```4
2
```
23. Output of loop:

```24 1
22 2
19 3
15 4
10 5
```
24. Output of loop:

```+---+
\   /
/   \
\   /
/   \
\   /
/   \
+---+
```
25. Output of loop:

```How many lines
How many lines
How many lines
are printed?
```
26. Output of loop:

```T-minus 5, 4, 3, 2, 1, Blastoff!
```
27. Output of loops:

```1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30
4 8 12 16 20 24 28 32 36 40
5 10 15 20 25 30 35 40 45 50
```
28. Output of loops:

```         *
***
*****
*******
*********
***********
*************
***************
*****************
*******************
```
29. Output of loops:

```****!****!****!
****!****!****!
```
30. Output of loops:

```************!
************!
```
31. Output of loops:

```*!*!*!*!
*!*!*!*!
*!*!*!*!
*!*!*!*!
*!*!*!*!
*!*!*!*!
```
32. Mistakes in `BadNews` program:

1. The loop prints every third number, not every odd number. The statement `count = count + 2` on line 8 should be moved into the loop header instead of `count++`.
2. line 12: The variable `count` is no longer defined (its scope is limited to the `for` loop). It should be declared before the loop begins rather than inside the loop's header.
3. line 12: Too large a value is printed for the final odd number; `count` should be printed, not `count + 2`.
4. line 20: It is illegal to try to assign a new value to a constant such as `MAX_ODD`. One way to fix this would be to write two methods: one to print the odds up to 21 and a second to print the odds up to 11. (Admittedly, this solution is redundant. A better solution to this kind of problem involves parameter passing, which will be demonstrated in later chapters.)
33. Output of `Strange` program:

```The result is: 55
```
1. `2 * line + 2 * SIZE`
2. `4 * line + (3 * SIZE)`
3. `-line + (2 * SIZE + 3)`
34. Table for output:

line`\``!``/`
10220
22182
34144
46106
5868
610210
• expression for `\` and `/`: `2 * line - 2`
• expression for `!`: `-4 * line + 26`
35. Table for output:

line`\``!``/`
10140
22102
3464
4626
• expression for `\` and `/`: `2 * line - 2`
• expression for `!`: `-4 * line + 18`
• generalized for constant: `-4 * line + (4 * SIZE + 2)`

## Chapter 3

1. e. `public static void example(int x, int y) {`
2. `MysteryNums` output:

```15 42
10 25
```
3. Mistakes in `Oops3` program:

1. line 5: cannot use variable `y` without declaring and initializing it
2. line 5: cannot declare the type of `y` in the method call
3. line 6: cannot call `printer` without the correct number of parameters (2, in this case)
4. line 7: cannot call `printer` by passing the correct type of parameters (`double`, in this case)
5. line 8: cannot refer to the variable `z`: it is in scope inside `printer`, not `main`
6. line 11: must provide a type for `x`
7. line 11: must provide a variable name for the second parameter
8. line 12: must refer to the parameters using the exact same spelling
9. line 13: cannot refer to variables in `main` that were not passed into `printer` as a parameter
4. Output of `Odds` program:

```1 3 5
1 3 5 7 9 11 13 15
1 3 5 7 9 11 13 15 17 19 21 23 25
```
5. Output of `Weird` program:

```1 2 3 4 5
1 2 3 4 5 6 7
1 2 3 4
number = 8
```
6. Output of `MysteryNumbers` program:

```three times two = 6
1 times three = 28
1 times 1 = 42
three times 1 = 2
1 times eight = 20
```
7. Output of `MysteryWho` program:

```whom and who like it
it and him like whom
whom and him like him
stu and boo like who
her and him like who
```
8. Output of `MysteryTouch` program:

```touch your eye to your head
touch your head to your eye
touch your shoulders to your elbow
touch your eyes and ears to your eyes and ears
touch your toes to your Toes
touch your shoulders to your knees toes
```
9. Output of `MysterySoda` program:

```say coke not pepsi or pop
say soda not soda or pepsi
say pepsi not koolaid or pop
say say not pepsi or pepsi
```
10. ```public static void printStrings(String s, int n) {
for (int i = 1; i <= n; i++) {
System.out.print(s);
}
System.out.println();
}
```
11. `System.out.println` is an overloaded method.
12. The `Temperature` program changes the value of its `tempc` parameter on line 11, but this doesn't affect the variable `tempc` in `main`. The (incorrect) output is:
```Body temp in C is: 0.0
```
13. results of `Math` expressions:

1. `1.6`
2. `2`
3. `36.0`
4. `64.0`
5. `10.0`
6. `116.0`
7. `7`
8. `5`
9. `-5`
10. `8.0`
11. `11.0`
12. `102.0`
13. `17.0`
14. `20.0`
15. `13.0`
16. `14.0`
14. Output of `MysteryReturn` program:

```3 0
1 2 4
4 3
5 2 4
8 1
5 9 4
```
15. ```double grade = 2.7;
Math.round(grade);                               // grade = 2.7
grade = Math.round(grade);                       // grade = 3.0

double min = Math.min(grade, Math.floor(2.9));   //   min = 2.0

double x = Math.pow(2, 4);                       //     x = 16.0
x = Math.sqrt(64);                               //     x = 8.0

int count = 25;
Math.sqrt(count);                                // count = 25
count = (int) Math.sqrt(count);                  // count = 5

int a = Math.abs(Math.min(-1, -3));              //     a = 3
```
16. ```public static int min(int n1, int n2, int n3) {
return Math.min(n1, Math.min(n2, n3));
}
```
17. ```public static int countQuarters(int cents) {
return cents % 100 / 25;
}
```
18. ```Kirk
My name is James
James Kirk
Kirk, Kames T.
T. is for Tiberius
```
19. results of `String` expressions:

1. `13`
2. `'a'`
3. `'G'`
4. `2`
5. `"GANDALF THE GRAY"`
6. `-1`
7. `"o Baggins"`
8. `"dalf the GR"`
9. `"Goondoolf the GRAY"`
10. `"Gandalf the GRAY"`
11. `"strange1"`
20. results of `String` expressions:

1. `6`
2. `19`
3. `"q.e.d."`
4. `"ARCTURAN MEGADONKEY"`
5. `"E."`
6. `"egad"`
7. `4`
8. `1`
9. `13`
10. `-1`
11. `"Arcturan Megadonkeys"`
12. `"b"`
13. `"Cyber"`
14. `"mega Corp"`
21. ```String quote = "Four score and seven years ago";
String expr1 = quote.substring(5, 10).toUpperCase();  // "SCORE"
String expr2 = quote.toLowerCase().substring(0, 4) + quote.substring(20, 26);  // "four years"
```
22. ```Hello there. 1+2 is 3 and 1.5 squared is 2.25!
```
There are 10 tokens:
1. `Hello` : (`String`)
2. `there.` : (`String`)
3. `1+2` : (`String`)
4. `is` : (`String`)
5. `3` : (`int`, `double`, `String`)
6. `and` : (`String`)
7. `1.5` : (`double`, `String`)
8. `squared` : (`String`)
9. `is` : (`String`)
10. `2.25!` : (`String`)
1. `34.50` : The code will run successfully and the variable money will store the value `34.5`.
2. `6` : The code will run successfully and the variable money will store the value `6.0`.
3. `\$25.00` : The code will crash with an exception.
4. `million` : The code will crash with an exception.
5. `100*5` : The code will crash with an exception.
6. `600x000` : The code will crash with an exception.
7. `none` : The code will crash with an exception.
8. `645` : The code will run successfully and the variable money will store the value `645.0`.
23. ```Scanner console = new Scanner(System.in);
System.out.print("Type an integer: ");
int number = console.nextInt();
System.out.println(number + " times 2 = " + (number * 2));
```
24. ```import java.util.*;
public class SumNumbers {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
System.out.print("low? ");
int low = console.nextInt();
System.out.print("high? ");
int high = console.nextInt();
int sum = 0;
for (int i = low; i <= high; i++) {
sum += i;
}
System.out.println("sum = " + sum);
}
}
```
25. ```Scanner console = new Scanner(System.in);
System.out.print("What is your phrase? ");
String phrase = console.nextLine();
System.out.print("How many times should I repeat it? ");
int times = console.nextInt();
for (int i = 1; i <= times; i++) {
System.out.println(phrase);
}
```

## Supplement 3G

1. Correct syntax to draw a rectangle:

b. `g.drawRect(10, 20, 50, 30);`
2. Mistakes in the code:

1. On the second line, the call to `drawLine` should be made on the `Graphics` object `g`, not on the `DrawingPanel` itself.
2. On the second line, the order of the parameters is incorrect.

The following is the corrected code:

```DrawingPanel panel = new DrawingPanel(200, 200);
Graphics g = panel.getGraphics();
g.drawLine(50, 86, 20, 35);
```
3. The black rectangle is being drawn second, so it's covering up the white inner circle. The following code fixes the problem:

```DrawingPanel panel = new DrawingPanel(200, 100);
Graphics g = panel.getGraphics();
g.setColor(Color.BLACK);
g.fillRect(10, 10, 50, 50);
g.setColor(Color.WHITE);
g.fillOval(10, 10, 50, 50);
```
4. The problem is that the parameters for the drawRect and drawLine methods have different meanings. In `drawRect`, the parameters are (x, y, width, height); in `drawLine`, they are (x1, y1, x2, y2). To fix the problem, the third and fourth parameters passed to `drawRect` should be changed to 40 and 20 so that the rectangle's bottom-left corner will be at (50, 40). The following code fixes the problem:

```DrawingPanel panel = new DrawingPanel(200, 100);
Graphics g = panel.getGraphics();
g.drawRect(10, 20, 40, 20);
g.drawLine(10, 20, 50, 40);
```
5. The `Draw7` program draws a series of progressively smaller black circles, each with its right and bottom edges touching the right and bottom corners of the window. Its output looks like this: ## Chapter 4

1. English statements translated into logical tests:

1. `z % 2 == 1`
2. `z <= Math.sqrt(y)`
3. `y > 0`
4. `x % 2 != y % 2`
5. `y % z == 0`
6. `z != 0`
7. `Math.abs(y) > Math.abs(z)`
8. `(x >= 0) == (z < 0)`
9. `y % 10 == y`
10. `z >= 0`
11. `x % 2 == 0`
12. `Math.abs(x - y) < Math.abs(z - y)`
2. Results of relational expressions:

1. `true`
2. `false`
3. `true`
4. `false`
5. `true`
6. `false`
7. `false`
8. `true`
9. `true`
3. Correct syntax for `if` statement:

e. `if (x == y) {`
4. Mistakes in `Oops4` program:

1. line 5: `if` statement should use `()` parentheses, not `{}` brackets
2. line 5: `=` should be `==`
3. line 5: `smaller` is out of scope here
4. line 10: `void` should be `int`
5. line 13: `=>` should be `>=` (or better yet, no `if` test is needed)
6. line 16: should not write variable's type of `int` when returning it
7. line 16: `int smaller` is out of scope here (declare outside `if` or return directly)
5. Output of `ifElseMystery1` calls:

Call Output
a. `ifElseMystery1(3, 20);` `13 21`
b. `ifElseMystery1(4, 5);` `5 6`
c. `ifElseMystery1(5, 5);` `6 5`
d. `ifElseMystery1(6, 10);` `7 11`
6. Output of `ifElseMystery2` calls:

Call Output
a. `ifElseMystery2(10, 2);` `10 6`
b. `ifElseMystery2(3, 8);` `9 9`
c. `ifElseMystery2(4, 4);` `3 4`
d. `ifElseMystery2(10, 30);` `29 30`
7. Code to read an integer from the user, then print `even` if that number is an even number or `odd` otherwise:

```Scanner console = new Scanner(System.in);
System.out.print("Type a number: ");
int number = console.nextInt();
if (number % 2 == 0) {
System.out.println("even");
} else {
System.out.println("odd");
}
```
8. The code incorrectly prints that even numbers not divisible by 3 are odd. This is because the `else` statement matches the most closely nested `if` statement (`number % 3 == 0`), not the outer `if` statement. The following change corrects the problem. Note the braces around the outer `if` statement:

```if (number % 2 == 0) {
if (number % 3 == 0) {
System.out.println("Divisible by 6.");
}
} else {
System.out.println("Odd.");
}
```
9. The code won't ever print "Mine, too!" because it mistakenly uses the `==` operator to compare two strings. It should use the `equals` method to compare them:

```if (name.equals("blue")) { ...
```
10. Refactored code to reduce redundancy:

```a = 2;
if (x < 30) {
x++;
}
System.out.println("Java is awesome! " + x);
```
11. Refactored code to reduce redundancy:

```Scanner console = new Scanner(System.in);
System.out.print("Is your money multiplied 1 or 2 times? ");
int times = console.nextInt();
System.out.print("And how much are you contributing? ");
int donation = console.nextInt();
sum += times * donation;
total += donation;

if (times == 1) {
count1++;
} else if (times == 2) {
count2++;
}
```

If the user could type any number, the code might need additional `if` statements to increment the proper count variable. If the user could type anything, even a non-integer, the code might need to use the `hasNextInt` method of the `Scanner` to ensure valid input before proceeding.

12. Refactored code to reduce redundancy:

```// Prompts for two people's money and reports how many \$20 bills are needed.
import java.util.*;
public class Bills {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int numBills1 = getBills(console, "John");
int numBills2 = getBills(console, "Jane");
System.out.println("John needs " + numBills1 + " bills");
System.out.println("Jane needs " + numBills2 + " bills");
}

public static int getBills(Scanner console, String name) {
System.out.print("How much will " + name + " be spending? ");
double amount = console.nextDouble();
System.out.println();
int numBills = (int) (amount / 20.0);
if (numBills * 20.0 < amount) {
numBills++;
}
return numBills;
}
}
```
13. Code to read red/green/blue color:

```Scanner console = new Scanner(System.in);
System.out.print("What color do you want? ");
String choice = console.nextLine();
if (choice.equalsIgnoreCase("r")) {
System.out.println("You have chosen Red.");
} else if (choice.equalsIgnoreCase("g")) {
System.out.println("You have chosen Green.");
} else if (choice.equalsIgnoreCase("b")) {
System.out.println("You have chosen Blue.");
} else {
System.out.println("Unknown color: " + choice);
}
```
14. Code to read playing card information:

```Scanner console = new Scanner(System.in);
System.out.print("Enter a card: ");
String rank = console.next();
String suit = console.next();
if (rank.equals("2")) {
rank = "Two";
} else if (rank.equals("3")) {
rank = "Three";
} else if (rank.equals("4")) {
rank = "Four";
} else if (rank.equals("5")) {
rank = "Five";
} else if (rank.equals("6")) {
rank = "Six";
} else if (rank.equals("7")) {
rank = "Seven";
} else if (rank.equals("8")) {
rank = "Eight";
} else if (rank.equals("9")) {
rank = "Nine";
} else if (rank.equals("10")) {
rank = "Ten";
} else if (rank.equals("J")) {
rank = "Jack";
} else if (rank.equals("Q")) {
rank = "Queen";
} else if (rank.equals("K")) {
rank = "King";
} else { // rank.equals("A")
rank = "Ace";
}

if (suit.equals("C")) {
suit = "Clubs";
} else if (suit.equals("D")) {
suit = "Diamonds";
} else if (suit.equals("H")) {
suit = "Hearts";
} else { // suit.equals("S")
suit = "Spades";
}

System.out.println(rank + " of " + suit);
```
15. The problem with the given `sumTo` method is that the `sum` variable needs to be declared outside the `for` loop. The following code fixes the problem:

```public static int sumTo(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
```
16. The `countFactors` method shown will not compile. It should count the factors using a a cumulative sum; it should not return inside the loop when it finds each factor. Instead, it should declare a counter outside the loop that is incremented as each factor is seen. The following code fixes the problem:

```public static int countFactors(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
count++;
}
}
return count;
}
```
17. Code to produce a cumulative product by multiplying together many numbers that are read from the console:

```Scanner console = new Scanner(System.in);
System.out.print("How many numbers? ");
int count = console.nextInt();
int product = 1;
for (int i = 1; i <= count; i++) {
System.out.print("Next number --> ");
int num = console.nextInt();
product *= num;
}
System.out.println("Product = " + product);
```
18. The expression equals `6.800000000000001` rather than the expected `6.8` because the limited precision of the `double` type led to a roundoff error.

19. The expression `gpa * 3` equals `9.600000000000001` rather than the expected `9.6` because of a roundoff error. A fix would be to test that the value is close to `9.6` rather than exactly equal to it, as shown in the following code:

```double gpa = 3.2;
double diff = Math.abs(gpa * 3 - 9.6);
if (diff < 0.1) {
System.out.println("You earned enough credits.");
}
```
20. Output of `CharMystery` program:

```efg
nopqrs

qr
```
21. Statement that tests to see whether a string begins with a capital letter:

```if (Character.isUpperCase(theString.charAt(0))) {
...
}
```
22. The `toLowerCase` method cannot be called on a `char` value, which is what the `charAt` method returns. A better solution would be to call the `Character.toLowerCase` method on the characters of the string, as shown in the following code:

```int count = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.toLowerCase(s.charAt(i)) == 'e') {
count++;
}
}
```

Another solution would be to lowercase the entire string once before the loop:

```s = s.toLowerCase();
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'e') {
count++;
}
}
```
23. The following expression would produce the desired result:

```String name = "Marla Singer";
int space = name.indexOf(" ");
String lastName = name.substring(space + 1);
String firstInitial = name.substring(0, 1);
String lastNameFirstInitial = lastName + ", " + firstInitial + ".";
System.out.println(lastNameFirstInitial);
```
24. Alternatively, you could use this shorter version:

```String name = "Marla Singer";
System.out.println(name.substring(name.indexOf(" ") + 1) + ", " + name.charAt(0) + ".");
```
25. Code to examine a string and determine how many of its letters come from the second half of the alphabet (`'n'` or later):

```// assuming that the String is stored in the variable str
int count = 0;
for (int i = 0; i < str.length(); i++) {
if (Character.toLowerCase(str.charAt(i)) >= 'n') {
count++;
}
}
System.out.println(count + " letters come after n.");
```
26. The preconditions of `printTriangleType` method are that the three side lengths constitute a valid triangle. Namely:

• All three side lengths passed are >= 0.
• No side's length exceeds the sum of any two other sides.
27. The preconditions of the `getGrade` method are that the grade parameter's value is between 0 and 100.

28. The `medianOf3` code fails when `n3` is the smallest of the three numbers; for example, when the parameters' values are (4, 7, 2), the code should return 4 but instead returns 2. The method could be correctly written as:

```public static int medianOf3(int n1, int n2, int n3) {
if (n1 < n2 && n1 < n3) {
if (n2 < n3) {
return n2;
} else {
return n3;
}
} else if (n2 < n1 && n2 < n3) {
if (n1 < n3) {
return n1;
} else {
return n3;
}
} else { // (n3 < n1 && n3 < n2)
if (n1 < n2) {
return n1;
} else {
return n2;
}
}
}
```

or the following shorter version:

```public static int medianOf3(int n1, int n2, int n3) {
return Math.max(Math.max(Math.min(n1, n2), Math.min(n2, n3)), Math.min(n1, n3));
}
```
29. The `quadratic` method would fail if the coefficient `a` is 0 Invalid values are when a = 0 (because it makes the denominator of the equation equal 0), or if the determinant (b2 - 4ac) is negative (because then it has no real square root). The following version of the code checks for these cases and throws exceptions:

```// Throws an exception if a, b, c are invalid
public static void quadratic(int a, int b, int c) {
double determinant = b * b - 4 * a * c;
if (a == 0) {
throw new IllegalArgumentException( "Invalid a value of 0");
}
if (determinant < 0) {
throw new IllegalArgumentException( "Invalid determinant");
}
...
}
```
30. The code fails when more than one number is odd, because it uses `else if` rather than `if`. The tests should not be nested because they are not mutually exclusive; more than one number could be odd. The following code fixes the problem:

```public static void printNumOdd(int n1, int n2, int n3) {
int count = 0;
if (n1 % 2 != 0) {
count++;
}
if (n2 % 2 != 0) {
count++;
}
if (n3 % 2 != 0) {
count++;
}
System.out.println(count + " of the 3 numbers are odd.");
}
```

The following version without `if` statements also works:

```public static void printNumOdd(int n1, int n2, int n3) {
int count = n1 % 2 + n2 % 2 + n3 % 2;
System.out.println(count + " of the 3 numbers are odd.");
}
```

## Chapter 5

1. Executes body 10 times. Output is:
`1 11 21 31 41 51 61 71 81 91`
2. Executes body 0 times. No output.
3. Loops infinitely. Output is:
```250
250
250
...
```
4. Executes body 3 times. Output is:
`2 4 16`
5. Executes body 5 times. Output is:
`bbbbbabbbbb`
6. Executes body 7 times. Output is:
```10
5
2
1
0
0
0
```
1. ```int n = 1;
while (n <= max) {
System.out.println(n);
n++;
}
```
2. ```int total = 25;
int number = 1;
while (number <= (total / 2)) {
total = total - number;
System.out.println(total + " " + number);
number++;
}
```
3. ```int i = 1;
while (i <= 2) {
int j = 1;
while (j <= 3) {
int k = 1;
while (k <= 4) {
System.out.print("*");
k++;
}
System.out.print("!");
j++;
}
System.out.println();
i++;
}
```
4. ```int number = 4;
int count = 1;
while (count <= number) {
System.out.println(number);
number = number / 2;
count++;
}
```
1. Output of `mystery` calls:

Call Output
a. `mystery(1);` `1 0`
b. `mystery(6);` `4 2`
c. `mystery(19);` `16 4`
d. `mystery(39);` `32 5`
e. `mystery(74);` `64 6`
2. Output of `mystery` calls:

Call Output
a. `mystery(19);` `19 0`
b. `mystery(42);` `21 1`
c. `mystery(48);` `3 4`
d. `mystery(40);` `5 3`
e. `mystery(64);` `1 6`
3. Range of random values generated:

1. 0 through 99 inclusive
2. 50 through 69 inclusive
3. 0 through 69 inclusive
4. -20 through 79 inclusive
5. 0, 4, 8, 12, 16, 20, 24, 28, 32, or 36
4. Code that generates a random integer between 0 and 10 inclusive:

```Random rand = new Random();
int num = rand.nextInt(11);
```
5. Code that generates a random odd integer between 50 and 99 inclusive.

```Random rand = new Random();
int num = rand.nextInt(25) * 2 + 51;
```
1. Executes body 10 times. Output is:
`1 11 21 31 41 51 61 71 81 91 `
2. Loops infinitely. Output is:
```count down: 10
count down: 9
count down: 8
count down: 7
count down: 6
count down: 5
count down: 4
count down: 3
count down: 2
count down: 1
count down: 0
count down: -1
...
```
3. Loops infinitely. Output is:
```250
250
250
...
```
4. Executes body 2 times. Output is:
```100
50
```
5. Executes body 3 times. Output is:
`2 4 16 `
6. Executes body 5 times. Output is:
`bbbbbabbbbb`
7. Executes body 7 times. Output is:
```10
5
2
1
0
0
0
```
8. Executes body 3 times. Output is:
```/\/\/\/\/\/\/\/\
```
6. `do/while` loop that repeatedly prints a certain message until the user tells the program to stop:

```Scanner console = new Scanner(System.in);
String response;
do {
System.out.println("She sells seashells by the seashore.");
System.out.print("Do you want to hear it again? ");
response = console.nextLine();
} while (response.equals("y"));
```
7. ```public static int zeroDigits(int number) {
int count = 0;
do {
if (number % 10 == 0) {
count++;
}
number = number / 10;
} while (number > 0);
return count;
}
```
8. `do/while` loop that repeatedly prints random numbers between 0 and 1000 until a number above 900 is printed:

```Scanner console = new Scanner(System.in);
Random rand = new Random();
int num;
do {
num = rand.nextInt(1000);
System.out.println("Random number: " + num);
} while (num < 900);
```
9. The `printLetters` code has a fencepost problem; it will print a dash after the last letter. The following code corrects the problem:

```public static void printLetters(String text) {
if (text.length() > 0) {
System.out.print(text.charAt(0));
for (int i = 1; i < text.length(); i++) {
System.out.print("-" + text.charAt(i));
}
}
System.out.println();   // to end the line of output
}
```
10. Sentinel loop that repeatedly prompts the user to enter a number and, once the number `-1` is typed, displays the maximum and minimum numbers that the user entered:

```int SENTINEL = -1;
System.out.print("Type a number (or " + SENTINEL + " to stop): ");
Scanner console = new Scanner(System.in);
int input = console.nextInt();
int min = input;
int max = input;
while (input != SENTINEL) {
if (input < min) {
min = input;
} else if (input > max) {
max = input;
}

System.out.print("Type a number (or " + SENTINEL + " to stop): ");
input = console.nextInt();
}

if (min != SENTINEL) {
System.out.println("Maximum was " + max);
System.out.println("Minimum was " + min);
}
```
11. Results of `boolean` expressions:

1. `true`
2. `true`
3. `false`
4. `true`
5. `true`
6. `false`
7. `false`
8. `true`
9. `true`
10. `true`
11. `true`
12. `false`
12. ```public static boolean isVowel(char c) {
c = Character.toLowerCase(c);   // case-insensitive
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
```
or:
```public static boolean isVowel(char c) {
return "aeiouAEIOU".indexOf(c) >= 0;
}
```
13. In this `isPrime` code the `boolean` flag isn't being used properly, because if the code finds a factor of the number, `prime` will be set to `false`, but on the next pass through the loop, if the next number isn't a factor, `prime` will be reset to `true` again. The following code fixes the problem:

```public static boolean isPrime(int n) {
boolean prime = true;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
prime = false;
}
}
return prime;
}
```
14. In this `contains` code the `boolean` flag isn't being used properly, because if the code finds the character, `found` will be set to `true`, but on the next pass through the loop, if the next character isn't `ch`, then `found` will be reset to `false` again. The following code fixes the problem:

```public static boolean contains(String str, char ch) {
boolean found = false;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ch) {
found = true;
}
}
return found;
}
```
15. Improved version of `startEndSame` code using Boolean zen:

```public static boolean startEndSame(String str) {
return str.charAt(0) == str.charAt(str.length() - 1);
}
```
16. Improved version of `hasPennies` code using Boolean zen:

```public static boolean hasPennies(int cents) {
return cents % 5 != 0;
}
```
17. Output of `mystery` calls:

Call Value Returned
a. `mystery(3, 3)` `3`
b. `mystery(5, 3)` `1`
c. `mystery(2, 6)` `2`
d. `mystery(12, 18)` `6`
e. `mystery(30, 75)` `15`
18. The Zune code will get stuck in an infinite loop when the current date is the end of a leap year. On December 31 of a leap year, the `days` value will be 366, so code enters the `if (isLeapYear)` statement but does not enter the `if (days > 366)` statement. So the loop does not subtract any days and never terminates. It can be fixed by adding a `break` statement to the loop:

```int days = getTotalDaysSince1980();
year = 1980;
while (days > 365) {   // subtract out years
if (isLeapYear(year)) {
if (days > 366) {
days -= 366;
year += 1;
} else {     // new code here
break;   // new code here
}            // new code here
} else {
days -= 365;
year += 1;
}
}
```
19. d. `(2 != 3) || (-1 >= 5) || !isPrime(n)`
20. Negations of `boolean` expressions:

1. `!b`
2. `(x <= y) || (y <= z)`
3. `(x != y) && (x > z)`
4. `(x % 2 == 0) || !b`
5. `(x / 2 != 13) && !b && (z * 3 != 96)`
6. `(z >= x) || (z <= y && x < y)`
21. The age/GPA reading code should reprompt for a valid integer for the user's age and a valid real number for the user's GPA. If the user types a token of the wrong type, the line of input should be consumed and the user should be reprompted. The following code implements the corrected behavior:

```Scanner console = new Scanner(System.in);
System.out.print("Type your age: ");
while (!console.hasNextInt()) {
console.next(); // throw away offending token
System.out.print("Type your age: ");
}
int age = console.nextInt();

print("Type your GPA: ");
while (!console.hasNextDouble()) {
console.next(); // throw away offending token
System.out.print("Type your GPA: ");
}
double gpa = console.nextDouble();
System.out.println("age = " + age + ", GPA = " + gpa);
```
22. The code will have the following behavior when each value is typed:

1. ```Type something for me! Jane
Your name is Jane
```
2. ```Type something for me! 56
Your IQ is 56
```
3. ```Type something for me! 56.2
Your name is 56.2
```
23. Code that prompts the user for a number and then prints a different message depending on whether the number was an integer or a real number:

```Scanner console = new Scanner(System.in);
System.out.print("Type a number: ");
if (console.hasNextInt()) {
int value = console.nextInt();
System.out.println("You typed the integer " + value);
} else if (console.hasNextDouble()) {
double value = console.nextDouble();
System.out.println("You typed the real number " + value);
}
```
24. Write code that prompts for three integers, averages them, and prints the average; robust against invalid input:

```String prompt = "Please enter a number: ";
Scanner console = new Scanner(System.in);
int num1 = getInt(console, prompt);
int num2 = getInt(console, prompt);
int num3 = getInt(console, prompt);
double average = (num1 + num2 + num3) / 3.0;
System.out.println("Average: " + average);
```
25. Point B
Point `y < x` `y == 0` `count > 0`
Point A SOMETIMES SOMETIMES NEVER
ALWAYS SOMETIMES SOMETIMES
Point C ALWAYS ALWAYS ALWAYS
Point D SOMETIMES SOMETIMES SOMETIMES
Point E NEVER SOMETIMES SOMETIMES
26. Point B
Point `n > b` `a > 1` `b > a`
Point A SOMETIMES SOMETIMES SOMETIMES
ALWAYS SOMETIMES SOMETIMES
Point C SOMETIMES ALWAYS ALWAYS
Point D SOMETIMES ALWAYS NEVER
Point E NEVER SOMETIMES SOMETIMES
27. Point `next == 0` `prev == 0` `next == prev`
Point A SOMETIMES ALWAYS SOMETIMES
Point B NEVER SOMETIMES SOMETIMES
Point C NEVER NEVER ALWAYS
Point D SOMETIMES NEVER SOMETIMES
Point E ALWAYS SOMETIMES SOMETIMES

## Chapter 6

1. A file is a named collection of information stored on a computer. We can read a file with a `Scanner` using the following syntax:

```Scanner input = new Scanner(new File("input.txt"));
```
2. The `Scanner` should read a `new File` with the name `test.dat`. The correct line of code is:

```Scanner input = new Scanner(new File("test.dat"));
```
3. Correct syntax to declare a Scanner to read the file example.txt in the current directory:

b. `Scanner input = new Scanner(new File("example.txt"));`
4. ```Scanner input = new Scanner(new File("input.txt"));
```
5. The `Scanner` tokenizes the line into:

c. `"welcome...to", "the", "matrix."`
6. The `Scanner` tokenizes the lines into:

b. `"in", "fourteen-hundred", "92", "columbus", "sailed", "the", "ocean", "blue", ":)"`
7. There are 17 tokens in the input. The "string" tokens can be read with the `next` method. The "integer" tokens can be read with `nextInt`. The "real number" tokens can be read with `nextDouble`. The tokens are:

1. `Hello` (string)
2. `there,how` (string)
3. `are` (string)
4. `you?` (string)
5. `I` (string)
6. `am` (string)
7. `"very` (string)
8. `well",` (string)
9. `thank` (string)
10. `you.` (string)
11. `12` (integer, real number, string)
12. `34` (integer, real number, string)
13. `5.67` (real number, string)
14. `(8` (string)
15. `+` (string)
16. `9)` (string)
17. `"10`" (string)
8. The file name string should use `/` or `\\` instead of `\`. The `\` is used to create escape sequences, and `\\` represents a literal backslash. The correct string is:

```Scanner input = new Scanner(new File("C:/temp/new files/test.dat"));
```
1. `"numbers.dat"` or `"C:/Documents and Settings/amanda/My Documents/programs/numbers.dat"`
2. `"data/homework6/input.dat"` or `"C:/Documents and Settings/amanda/My Documents/programs/data/homework6/input.dat"`
3. There is only one legal way to refer to this file: by its absolute path, `"C:/Documents and Settings/amanda/My Documents/homework/data.txt"`
1. `"names.txt"` or `"/home/amanda/Documents/hw6/names.txt"`
2. `"data/numbers.txt"` or `"/home/amanda/Documents/hw6/data/numbers.txt"`
3. There is only one legal way to refer to this file: by its absolute path, `"/home/amanda/download/saved.html"`
9. Mistakes in `Oops6` program:

1. line 2: `main` method must say throws `FileNotFoundException` when constructing a file `Scanner`
2. line 3: must create a `new File` when declaring the `Scanner`
3. line 9: should not declare another `Scanner` for the file
4. line 13: `nextLine` should be `hasNextLine`
5. line 14: `line` should be `nextLine`
6. line 16: need a second line `Scanner` to read the tokens of each line
7. line 16: `hasNext` should be `next()`
8. line 19: need to add 3 `println` statements to print line/word stats
10. The following output would be produced:

```input: 6.7        This file has
input:         several input lines.
input:
input:   10 20         30   40
input:
input: test
6 total
```
11. Output produced if `hasNext` and `next` are used:

```input: 6.7
input: This
input: file
input: has
input: several
input: input
input: lines.
input: 10
input: 20
input: 30
input: 40
input: test
12 total
```
12. Output produced if `hasNextInt` and `nextInt` are used:

```0 total
```

Output produced if `hasNextDouble` and `nextDouble` are used:

```input: 6.7
1 total
```
13. a.
```the quick brown
fox   jumps

over
the lazy    dog
```
b.
```the
quick
brown
fox
jumps
over
the
lazy
dog
```
14. Program that prints itself as output:

```import java.io.*;
import java.util.*;

public class PrintMyself {
public static void main(String[] args) throws FileNotFoundException {
Scanner input = new Scanner(new File("PrintMyself.java"));
while (input.hasNextLine()) {
System.out.println(input.nextLine());
}
}
}
```
15. Code that prompts the user for a file name and prints the contents of that file to the console as output:

```public static void printEntireFile() throws FileNotFoundException {
Scanner console = new Scanner(System.in);
System.out.print("Type a file name: ");
String filename = console.nextLine();
Scanner input = new Scanner(new File(filename));
while (input.hasNextLine()) {
System.out.println(input.nextLine());
}
}
```
16. Program that takes as input lines of text and produces as output the same text inside a box:

```// precondition: no line in input is longer than width
public static void printBox(Scanner input, int width) {
printTopBottom(width);
while (input.hasNextLine()) {
String line = input.nextLine();
System.out.print("| " + line);
for (int i = line.length(); i < width; i++) {
System.out.print(" ");
}
System.out.println(" |");
}
printTopBottom(width);
}

public static void printTopBottom(int width) {
System.out.print("+");
for (int i = 0; i < width + 2; i++) {
System.out.print("-");
}
System.out.println("+");
}
```
17. A `PrintStream` object is used to write to an external file. It has methods such as `println` and `print`.

18. Code to print the following four lines of text into a file named `message.txt`:

```PrintStream out = new PrintStream(new File("message.txt"));
out.println("Testing,");
out.println("1, 2, 3.");
out.println();
out.println("This is my output file.");
```
19. Code that repeatedly prompts the user for a file name until the user types the name of a file that exists on the system.

```public static String getFileName() {
Scanner console = new Scanner(System.in);
String filename = "";
do {
System.out.print("Type a file name: ");
filename = console.nextLine();
} while (!(new File(filename).exists()));
return filename;
}
```
20. Code that uses `getFileName` before calling `printEntireFile`:

```// reprompts until file name is valid
public static void printEntireFile2() throws FileNotFoundException {
String filename = getFileName();
Scanner input = new Scanner(new File(filename));
while (input.hasNextLine()) {
System.out.println(input.nextLine());
}
}
```

## Chapter 7

1. Syntax to declare an array of ten integers:

e. `int[] a = new int;`
• First element: `numbers`
• Last element: `numbers` or `numbers[numbers.length - 1]`
2. ```int[] data = new int;
data = 27;
data = 51;
data = 33;
data = -1;
data = 101;
```
3. Code that stores all odd numbers between -6 and 38 into an array using a loop:

```int[] odds = new int;
for (int i = 0; i < 22; i++) {
odds[i] = i * 2 - 5;
}
```
4. After the code is executed, the `numbers` array contains the following element values:

```[0, 4, 11, 0, 44, 0, 0, 2]
```
5. After the code is executed, the `data` array contains the following element values:

```[3, 3, 0, 0, 6, 9, 0, -18]
```
6. The code to print the arrays and to compare them doesn't work properly. Arrays can't be printed directly by `println`, nor can they be compared directly using relational operators such as `==`. These operations can be done correctly by looping over the elements of each array and printing/comparing them one at a time, or by calling methods of the `Arrays` class:

```// print the array elements
System.out.println(Arrays.toString(first));
System.out.println(Arrays.toString(second));

// see if the elements are the same
if (Arrays.equals(first, second)) {
...
```
7. Correct syntax to declare an array of six integer values:

a. `int[] a = {17, -3, 42, 5, 9, 28};`
8. ```int[] data = {7, -1, 13, 24, 6};
```
9. ```public static int max(int[] data) {
int max = data;
for (int i = 1; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
}
}
return max;
}
```
10. ```public static double average(int[] a) {
double mean = 0.0;
for (int i = 0; i < a.length; i++) {
mean += a[i];
}
return mean / a.length;
}
```
11. An array traversal is a sequential processing of each of an array's elements. Problems that can be solved in this manner include printing an array, comparing two arrays for equality, and searching an array for a given value.

12. Code that uses a `for` loop to print each element of an array named `data`:

```for (int i = 0; i < data.length; i++) {
System.out.println("element [" + i + "] is " + data[i]);
}
```
13. After the code is executed, the `list` array contains the following element values:

```[3, 24, 8, -5, 6, 1]
```
14. ```public static void printBackwards(int[] list) {
if (list.length == 0) {
System.out.println("[]");
} else {
System.out.print("[" + list[list.length - 1]);
for (int i = list.length - 2; i >= 0; i--) {
System.out.print(", " + list[i]);
}
System.out.println("]");
}
}
```
15. To make the `count` and `equals` methods process arrays of `String`s, you must change `int[]` to `String[]` and replace all other occurrences of the word int with String. You must also change any comparisons using `==` to comparisons using the `equals` method.

16. ```public static boolean allLess(int[] list1, int[] list2) {
if (list1.length != list2.length) {
return false;
}
for (int i = 0; i < list1.length; i++) {
if (list1[i] >= list2[i]) {
return false;
}
}
return true;
}
```
17. The method to swap array elements works because, unlike integers, arrays are objects and use reference semantics. This means that changes to an array parameter's elements will be seen in the original array by the caller.

18. Output of `ReferenceMystery1` program:

```2 [0, 0, 1, 0]
1 [0, 0, 1, 0]
3 [0, 0, 1, 1]
2 [0, 0, 1, 1]
```
19. Output of `ReferenceMystery2` program:

```2 [0, 1]
1 [0, 1]
1 [1, 2]
0 [1, 2]
```
20. ```public static void swapPairs(int[] list) {
for (int i = 0; i < list.length - 1; i += 2) {
swap(list, i, i + 1);
}
}
```
21. After the code is executed, the `numbers` array contains the following element values:

```[20, 30, 40, 50, 60, 70, 80, 90, 100, 100]
```
22. After the code is executed, the `numbers` array contains the following element values:

```[10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
```
23. After the `mystery` method is executed, the arrays contain the following element values:

• `a1`: `[26, 19, 14, 11, 10]`
• `a2`: `[1, 4, 9, 16, 25]`
24. After the `mystery2` method is executed, the arrays contain the following element values:

• `a1`: `[1, 3, -3, 13, -4, -24, -6, -14]`
• `a2`: `[1, 1, 2, 3, 5, 8, 13, 21]`
25. After the `mystery3` method is executed, the array contains the following element values:

```[7, 3, 1, 0, 8, 18, 5, -1, 5]
```
26. Results of calls to `mystery4` method:

1. `0`
2. `9`
3. `6`
4. `8`
5. `2`
27. Final array contents after calls to `mystery5` method:

1. ``
2. `[14, 8]`
3. `[7, 2, 3, 3, 1, 4]`
4. `[10, 9, 9, 6, 6]`
5. `[12, 12, 11, 11, 9, 8]`
28. ```public static double averageLength(String[] strings) {
int sum = 0;
for (int i = 0; i < strings.length; i++) {
sum += strings[i].length();
}
return (double) sum / strings.length;
}
```
29. ```public static boolean isPalindrome(String[] array) {
for (int i = 0; i < array.length / 2; i++) {
if (!array[i].equals(array[array.length - 1 - i])) {
return false;
}
}
return true;
}
```
30. After the code is executed, the `numbers` array contains the following element values:

```[[0, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5]]
```
31. Loop to initialize the third row of data to store the numbers 1 through 7:

```for (int i = 0; i < 7; i++) {
data[i] = i + 1;
}
```
32. Code that constructs a two-dimensional array of integers with 5 rows and 10 columns, filled with a multiplication table:

```int[][] table = new int;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 10; j++) {
table[i][j] = i * j;
}
}
```
33. Loop to copy the contents of second column into fifth column:

```for (int i = 0; i < 6; i++) {
matrix[i] = matrix[i];
}
```
34. After the `mystery2d` method is executed, the `numbers` array contains the following element values:

```[[4, 5, 6, 6], [5, 6, 7, 7], [6, 7, 8, 8]]
```
35. ```int[][] jagged = new int[];
int value = 1;
for (int i = 0; i < 5; i++) {
jagged[i] = new int[i + 1];
for (int j = 0; j < i + 1; j++) {
jagged[i][j] = value;
value++;
}
}
```
36. If the 2D array is named `pixels`, the `DrawingPanel`'s height is stored as `pixels.length` and its width is stored as `pixels.length` .
37. ```public static void toRedChannel(DrawingPanel panel) {
Color[][] pixels = panel.getPixels();
for (int row = 0; row < pixels.length; row++) {
for (int col = 0; col < pixels.length; col++) {
// your code goes here
pixel = DrawingPanel.getRed(pixels[row][col]);
}
}
panel.setPixels(pixels);
}
```
38. The panel will display a diagonal gradient of black to white, like the following image: ## Chapter 8

1. Procedural programming treats a program as a sequence of actions or commands to perform. Object-oriented programming looks at a program as a group of interacting entities named objects that each keep track of related data and behavior.

2. An object is an entity that encapsulates data and behavior that operates on the data. A class is the blueprint for a type of object, specifying what data and behavior the object will have and how to construct it.

3. The state of a `String` object is its sequence of characters (which are actually stored internally as an array of `char` values). A `String` object's behavior includes its methods, such as `length`, `substring`, `toUpperCase`, and `indexOf`.

4. Output of `ReferenceMystery3` program:

```14 14
7 9 14 2
18 18
7 9 14 18
```
5. The state of a `Calculator` object might include the number that has just been computed, as well as another number that is currently being input. A more complex `Calculator` object might also include a memory feature that stores an additional value. The behavior of a `Calculator` object might include methods to add, subtract, multiply, divide, and perhaps carryout other math operations (such as exponentiation, logarithms, and trigonometric functions like sine and cosine).

6. A field is a variable that exists inside of an object. A parameter is a variable inside a method whose value is passed in from outside. Fields have different syntax because they are usually declared with the `private` keyword and not in a method's header. A field's scope is throughout the class, while a parameter's scope is limited to the method.

7. `Name` class that represents a person's name:

```// A Name object represents a name such as "John Q. Public".
public class Name {
String firstName;
char middleInitial;
String lastName;
}
```
8. An accessor provides the client access to some data in the object, while a mutator lets the client change the object's state in some way. Accessors' names often begin with "get" or "is", while mutators' names often begin with "set".

9. Correct syntax for calling `computeInterest` method on a `BankAccount` object:

d. `double result = acct.computeInterest(42);`
10. ```// Returns the distance from this point to the given other point.
public double distance(Point other) {
int dx = x - other.x;
int dy = y - other.y;
return Math.sqrt(dx * dx + dy * dy);
}
```
11. `Name` class with two methods:

```// A Name object represents a name such as "John Q. Public".
public class Name {
String firstName;
char middleInitial;
String lastName;

// The name in normal order such as "John Q. Public".
public String getNormalOrder() {
return firstName + " " + middleInitial + ". " + lastName;
}

// The name in reverse order such as "Public, John Q.".
public String getReverseOrder() {
return lastName + ", " + firstName + " " + middleInitial + ".";
}
}
```
12. To make the objects of your class printable, define a `toString` method in it.

13. The `println` statement is equivalent to the following:

c. `System.out.println(p1.toString());`
14. `toString` method for `Point` class:

```// Returns a String representation of this point, such as "java.awt.Point[x=7,y=2]".
public String toString() {
return "java.awt.Point[x=" + x + ", y=" + y + "]";
}
```
15. `toString` method for `Name` class:

```// Returns a String representation of this Name, such as "John Q. Public".
public String toString() {
return firstName + " " + middleInitial + ". " + lastName;
}
```
or:
```// Returns a String representation of this Name, such as "John Q. Public".
public String toString() {
return getNormalOrder();
}
```
16. Finished version of client code:

```// construct two Point objects, one at (8, 2) and one at (4, 3)
Point p1 = new Point(8, 2);
Point p2 = new Point(4, 3);

// display the two Point objects' state
System.out.println("p1 is " + p1);
System.out.println("p2 is " + p2);

// display p1 distance from origin
System.out.println("p1's distance from origin is " + p1.distanceFromOrigin());

// translate p1 to (9, 4)
// translate p2 to (3, 13)
p1.translate(1, 2);
p2.translate(-1, 10);

// display the two Point objects' state again
System.out.println("p1 is now " + p1);
System.out.println("p2 is now " + p2);
```
17. A constructor is a special method that creates an object and initializes its state. It's the method that is called when you use the `new` keyword. A constructor is declared without a return type.

18. Two errors with the `Point` constructor:

1. The constructor shouldn't have the `void` keyword in its header, because constructors have no return type. The header should be:
```public Point(int x, int y) {
```
2. The fields `x` and `y` shouldn't have their types redeclared in front of them. This bug causes shadowing of the fields. Here are the corrected lines:
```x = initialX;
y = initialY;
```
19. Constructor for `Name` class:

```// A Name object represents a name such as "John Q. Public".
public class Name {
String firstName;
char middleInitial;
String lastName;

// Initializes a new Name with the given values.
public Name(String initialFirst, char initialMiddle, String initialLast) {
firstName = initialFirst;
middleInitial = initialMiddle;
lastName = initialLast;
}

// The name in normal order such as "John Q. Public".
public String getNormalOrder() {
return firstName + " " + middleInitial + ". " + lastName;
}

// The name in reverse order such as "Public, John Q.".
public String getReverseOrder() {
return lastName + ", " + firstName + " " + middleInitial + ".";
}
}
```
20. The keyword `this` refers to the object on which a method or constructor has been called (sometimes called the "implicit parameter"). It is used to access or set the object's field values, to call the object's methods, or to call one constructor from another.

21. Constructor for `Point` class that copies another point:

```// Constructs a Point object with the same x and y
// coordinates as the given Point.
public Point(Point p) {
this.x = p.x;
this.y = p.y;
}
```
or:
```// Constructs a Point object with the same x and y
// coordinates as the given Point.
public Point(Point p) {
this(p.x, p.y);   // call the (int, int) constructor
}
```
22. Abstraction is the ability to focus on a problem at a high level without worrying about the minor details. Objects provide abstraction by giving us more powerful pieces of data that have sophisticated behavior without having to manage and manipulate the data directly.

23. Items declared `public` may be seen and used from any class. Items declared `private` may be seen and used only from within their own classes. Objects' fields should be declared `private` to provide encapsulation, so that external code can't make unwanted direct modifications to the fields' values.

24. To access private fields, create accessor methods that return their values. For example, add a `getName` method to access the `name` field of an object.

25. Adding `setX` and `setY` methods to the `Point` class:

```// Sets this Point's x coordinate to the given value.
public void setX(int newX) {
x = newX;
}

// Sets this Point's y coordinate to the given value.
public void setY(int newY) {
y = newY;
}
```
26. Encapsulated version of `Name` class:

```// A Name object represents a name such as "John Q. Public".
public class Name {
private String firstName;
private char middleInitial;
private String lastName;

// Initializes a new Name with the given values.
public Name(String initialFirst, char initialMiddle, String initialLast) {
firstName = initialFirst;
middleInitial = initialMiddle;
lastName = initialLast;
}

// Returns the person's first name.
public String getFirstName() {
return firstName;
}

// Returns the person's middle initial.
public char getMiddleInitial() {
return middleInitial;
}

// Returns the person's last name.
public String getLastName() {
return lastName;
}

// The name in normal order such as "John Q. Public".
public String getNormalOrder() {
return firstName + " " + middleInitial + ". " + lastName;
}

// The name in reverse order such as "Public, John Q.".
public String getReverseOrder() {
return lastName + ", " + firstName + " " + middleInitial + ".";
}
}
```
27. Mutator methods for `Name` class:

```// Sets the first name to the given value.
public void setFirstName(String firstName) {
this.firstName = firstName;
}

// Sets the last name to the given value.
public void setLastName(String lastName) {
this.lastName = lastName;
}

// Sets the middle initial to the given value.
public void setMiddleInitial(char middleInitial) {
this.middleInitial = middleInitial;
}
```
28. Encapsulation allows you to change a class's internal implementation without changing its external view to clients. When a class is encapsulated clients cannot directly access its fields, so changing those fields will not disturb client behavior as long as the external view (method behavior) is consistent.

29. Cohesion is the concept of how well a class's contents go together. You can tell that a class is cohesive when each of its fields stores important state related to the object and each method interacts with that state in some way to produce useful behavior.

30. We did not place console I/O code into our `Stock` class because doing so would force clients to use those exact I/O messages. By keeping I/O code out of `Stock`, we kept it independent from its clients.

31. Accessor methods for `Stock` class:

```// Returns this Stock's symbol value.
public String getSymbol() {
return symbol;
}

// Returns this Stock's total number of shares purchased.
public int getTotalShares() {
return totalShares;
}

// Returns this Stock's total cost for all shares.
public double getTotalCost() {
return totalCost;
}
```

## Chapter 9

1. Code reuse is the practice of writing a single piece of code and using it many times in different programs and contexts. Inheritance is useful for code reuse because it allows you to write a class that captures common useful code and then extend that class to add more features and behavior to it.

2. Overloading a method involves creating two methods in the same class that have the same name but different parameters. Overriding a method involves creating a new version of an inherited method in a subclass, with identical parameters but new behavior to replace the old.

3. Correct syntax to indicate that class `A` is a subclass of `B`:

a. `public class A extends B {`
4. The following statements are marked as legal or illegal:

1. `Vehicle v = new Car();   // legal`
2. `Vehicle v = new SUV();   // legal`
3. `Car c = new SUV();       // legal`
4. `SUV s = new SUV();       // legal`
5. `SUV s = new Car();       // illegal`
6. `Car c = new Vehicle();   // illegal`
5. The `this` keyword refers to the current object, while the `super` keyword refers to the current class's superclass. Use the `super` keyword when calling a method or constructor from the superclass that you've overridden, and use the `this` keyword when accessing your object's own fields, constructors, and methods.

6. `UndergraduateStudent` can call the `setAge` method but cannot directly access the `name` or `age` fields from `Student`.

7. ```public UndergraduateStudent(String name) {
super(name, 18);
year = 0;
}
```
8. ```public void setAge(int age) {
super.setAge(age);
year++;
}
```
9. Output from the `Car`/`Truck` statements:

```vroom
car 1
car 2
vroom
truck 1
car 2
```
10. Output from the `Car`/`Truck` statements, version 2:

```vroomvroom
truck 1
car 1
```
11. Output from `A`/`B`/`C`/`D` polymorphism code:

```B 2
A
A 1

D 2
C
C 1

A 2
A
A 1

A 2
C
C 1

```
12. Output from `Flute`/`Blue`/`Shoe`/`Moo` polymorphism code:

```flute
shoe 1
flute 2

flute
blue 1
flute 2

moo
moo 1
moo 2

moo
blue 1
moo 2

```
13. Output from `Flute`/`Blue`/`Shoe`/`Moo` polymorphism code, version 2:

```moo 2
blue 1
moo

moo 2
moo 1
moo

flute 2
shoe 1
flute

flute 2
blue 1
flute

```
14. Output from `Mammal`/`SeaCreature`/`Whale`/`Squid` polymorphism code:

```squid
creature 1
tentacles

BIG!
spout
creature 2

ocean-dwelling
creature 1
creature 2

ocean-dwelling
warm-blooded
creature 2

```
15. Output from `Mammal`/`SeaCreature`/`Whale`/`Squid` polymorphism code, version 2:

```creature 2
ocean-dwelling
creature 1

tentacles
squid
creature 1

creature 2
ocean-dwelling
warm-blooded

creature 2
BIG!
spout

```
16. Output from `Bay`/`Pond`/`Ocean`/`Lake` polymorphism code:

```Bay 1  Pond 2
Ocean 2
Lake 3  Ocean 2

Pond 1
Pond 2
Pond 3

Pond 1
Pond 2
Lake 3  Pond 2

Bay 1  Pond 2
Bay 2
Lake 3  Bay 2

```
17. None of the statements produce errors. Output from `Bay`/`Pond`/`Ocean`/`Lake` polymorphism code, version 2:

```Bay 1  Pond 2
Bay 1  Pond 2
Ocean 2
Ocean 2
Lake 3  Ocean 2
```
18. An is-a relationship is a subclass relationship such as those created by inheritance. A has-a relationship is when one object contains a reference to another as a field.

19. Having `Square` extend `Rectangle` is a poor design because a `Square` cannot substitute for a `Rectangle`. If the client thinks the `Square` is a `Rectangle` and calls `setWidth` or `setHeight` on it, unexpected results will occur. The client will expect the width and height to be different after the call, but they may not be.

20. Having each of the 52 playing cards in its own class is not a good design because it will result in a clutter of code files without significant differences between them. A better design would have one `Card` class with fields for rank and suit.

21. We made `DividendStock` a separate subclass from `Stock` for two major reasons. First, not all stocks pay dividends, so it does not make sense for every `Stock` object to have a `dividends` field and a `payDividend` method. Second, the `Stock` code already worked correctly, so we did not want to tamper with it needlessly. Making `DividendStock` a separate class constituted an additive and noninvasive change.

22. Extending a class causes your class to inherit all methods and data from that class. Implementing an interface forces you to write your own code to implement all the methods in that interface.

23. The code for class `C` must contain implementations of the methods `m1` and `m2` to compile correctly, because `C` claims to implement the `I` interface.

24. What's wrong is that interfaces can't declare fields or write bodies for methods. The following is a correct `Colored` interface:

```import java.awt.*;

// Represents items that have a color that can be retrieved.
public interface Colored {
public Color getColor();
}
```
25. Extension of `Point` class that implements the `Colored` interface:

```// Represents a point with a color. import java.awt.*;
public class ColoredPoint extends Point implements Colored {
private Color color;

// Constructs a new colored point with the given
// coordinates and color.
public ColoredPoint(int x, int y, Color color) {
super(x, y);
this.color = color;
}

// Returns this point's color.
public Color getColor() {
return color;
}
}
```
26. Version of `Shape` interface with `getSideCount` method:

```// A general interface for shape classes.
public interface Shape {
public double getArea();
public double getPerimeter();
public int getSideCount();
}
```

The following are the implementations of the method in the `Circle`, `Rectangle`, and `Triangle` classes:

```// Returns the number of sides a circle has (0).
public int getSideCount() {
return 0;
}

// Returns the number of sides a rectangle has (4).
public int getSideCount() {
return 4;
}

// Returns the number of sides a triangle has (3).
public int getSideCount() {
return 3;
}
```
27. An abstract class is a class intended to be used only as a superclass for inheritance. It's like a normal class in that it can have fields, methods, constructors, and so on. It's different from a normal class in that it can have abstract methods, which are like methods of an interface because only their headers are given, not their bodies. It's also different from a normal class because it can't be instantiated (used to create objects).

28. You can be sure that the `OrderedByLength` class contains a `getElement` method and that it implements the `arrange` method, because if it extends `Ordered` without being `abstract` itself, it must have that method in order to compile.

29. One good design would be to have an abstract superclass named `Movie` with data such as name, director, and date. There would be subclasses of `Movie` to represent particular movie types, such as `Drama`, `Comedy`, and `Documentary`. Each subclass would store its specific data and behavior.

## Chapter 10

1. An `ArrayList` is a structure that stores a collection of objects inside itself as elements. Each element is associated with an integer index starting from 0. You should use an `ArrayList` instead of an array if you don't know how many elements you'll need in advance, or if you plan to add items to or remove items from the middle of your dataset.

2. Correct syntax to construct an `ArrayList` to store integers:

e. `ArrayList<Integer> list = new ArrayList<Integer>();`
3. Code to declare an `ArrayList` containing `["It", "was", "a", "stormy", "night"]`:

```ArrayList<String> list = new ArrayList<String>();
list.add("It");
list.add("was");
list.add("a");
list.add("stormy");
list.add("night");
```

The list's type is `ArrayList<String>` and its size is 5.

4. Code to insert two additional elements, `"dark"` and `"and"`, at the proper places:

```list.add(3, "dark");
list.add(4, "and");
```
5. Code to change the second element's value to `"IS"`:

```list.set(1, "IS");
```
6. Code to remove from the list any strings that contain the letter `"a"`:

```for (int i = 0; i < list.size(); i++) {
if (list.get(i).indexOf("a") >= 0) {
list.remove(i);
i--;   // so the new element i will be checked
}
}
```
7. Code to declare an `ArrayList` holding the first 10 multiples of 2:

```ArrayList<Integer> numbers = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
numbers.add(2 * i);
}
```
8. ```public static int maxLength(ArrayList<String> list) {
int max = 0;
for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
if (s.length() > max) {
max = s.length();
}
}
return max;
}
```
9. Code to print out whether or not a list of `String`s contains the value `"IS"`, without using a loop:

```System.out.println(list.contains("IS"));
```
10. Code to print out the index at which the list contains the value `"stormy"` and the index at which it contains `"dark"`:

```System.out.println(list.indexOf("stormy"));
System.out.println(list.indexOf("dark"));
```
11. A for-each loop that prints the uppercase version of each `String` in the list on its own line:

```for (String s : list) {
System.out.println(s.toUpperCase());
}
```
12. The code throws a `ConcurrentModificationException` because it is illegal to modify the elements of an `ArrayList` while for-each looping over it.

13. The code doesn't compile because primitives cannot be specified as type parameters for generic types. The solution is to use the "wrapper" type `Integer` instead of `int`. Change the line declaring the `ArrayList` to the following:

```ArrayList<Integer> numbers = new ArrayList<Integer>();
```
14. A wrapper class is one whose main purpose is to act as a bridge between primitive values and objects. An `Integer` is an object that holds an `int` value. Wrappers are useful in that they allow primitive values to be stored into collections.

15. Output produced when the `mystery1` method is passed each list:

1. `[1, 2, 6, 8]`
2. `[10, 30, 40, 20, 60, 50]`
3. `[-4, 1, 25, 4, 16, 9, 64, 36, 49]`
16. Output produced when the `mystery2` method is passed each list:

1. `[20, 10, 20, 30, 30, 20]`
2. `[8, 7, 8, 2, 9, 7, 4, 4, 2, 8]`
3. `[33, 28, 33, -1, 3, 28, 17, 9, 33, 17, -1, 33]`
17. Output produced when the `mystery3` method is passed each list:

1. `[72, 20]`
2. `[1, 20, 18, 15, 11, 6]`
3. `[10, 90, 70, 40]`
18. Output produced when the `mystery4` method is passed each list:

1. `[31, 21, 11]`
2. `[5, 8, 10, 3, 9]`
3. `[34, 10, 18, 29, 4, 0]`
19. To arrange an `ArrayList` into sorted order, call the `Collections.sort` method on it. For example, if your `ArrayList` is stored in a variable named `list`, you would call:

```Collections.sort(list);
```

For this to work, the type of the objects stored in the list must be `Comparable`.

20. A natural ordering is an order for objects of a class where "lesser" objects come before "greater" ones, as determined by a procedure called the class's comparison function. To give your own class a natural ordering, declare it to implement the `Comparable` interface and define a comparison function for it by writing an appropriate `compareTo` method.

1. `n1.compareTo(n2) > 0 `
2. `n3.compareTo(n1) == 0`
3. `n2.compareTo(n1) < 0`
4. `s1.compareTo(s2) < 0`
5. `s3.compareTo(s1) > 0`
6. `s2.compareTo(s2) == 0`
21. Code that reads two names from the console and prints the one that comes first in alphabetical order:

```Scanner console = new Scanner(System.in);
System.out.print("Type a name: ");
String name1 = console.nextLine();
System.out.print("Type a name: ");
String name2 = console.nextLine();
if (name1.compareTo(name2) < 0) {
System.out.println(name1 + " goes before " + name2);
} else if (name1.compareTo(name2) > 0) {
System.out.println(name1 + " goes after " + name2);
} else { // equal
System.out.println(name1 + " is the same as " + name2);
}
```
22. Code to read a line of input from the user and print the words of that line in sorted order:

```Scanner console = new Scanner(System.in);
System.out.print("Type a message to sort: ");
String message = console.nextLine();
ArrayList<String> words = new ArrayList<String>();
Scanner lineScan = new Scanner(message);
while (lineScan.hasNext()) {
words.add(lineScan.next());
}

System.out.print("Your message sorted: ");
Collections.sort(words);
for (String word : words) {
System.out.print(word + " ");
}
System.out.println();   // to end the line of output
```

## Chapter 11

1. You should use a `LinkedList` when you plan to add or remove many values at the front or back of the list, or when you plan to make many filtering passes over the list in which you remove certain elements.

2. The code shown would perform better with an `ArrayList`, because it calls the `get` method many times using indexes in the middle and end of the list. This is a slow operation for a `LinkedList`.

3. An iterator is an object that represents a position within a list and enables you to view or make changes to the elements at that position. Iterators are often used with linked lists because they retain the position in the list, so you don't have to call expensive list methods like `get`, `add`, or `remove` many times on the middle or end of the list.

4. ```public static int countDuplicates(LinkedList<Integer> list) {
int count = 0;
Iterator<Integer> i = list.iterator();
int prev = i.next();
while (i.hasNext()) {
int next = i.next();
if (prev == next) {
count++;
}
prev = next;
}
return count;
}
```
5. ```public static void insertInOrder(LinkedList<String> list, String value) {
int index = 0;
Iterator<String> i = list.iterator();
String next = i.next();

// advance until the proper index
while (i.hasNext() && next.compareTo(value) < 0) {
next = i.next();
index++;
}

list.add(index, value);
}
```
6. ```public static void removeAll(LinkedList<Integer> list, int value) {
Iterator<Integer> i = list.iterator();
while (i.hasNext()) {
if (i.next() == value) {
i.remove();
}
}
}
```
7. ```public static void wrapHalf(LinkedList<Integer> list) {
int halfSize = (list.size() + 1) / 2;
for (int i = 0; i < halfSize; i++) {
// wrap around one element
int element = list.remove(list.size() - 1);
list.add(0, element);
}
}
```
8. An abstract data type defines the type of data a collection can hold and the operations it can perform on that data. Linked lists implement the `List` abstract data type.

9. ```public static int countDuplicates(List<Integer> list) {
int count = 0;
Iterator<Integer> i = list.iterator();
int prev = i.next();
while (i.hasNext()) {
int next = i.next();
if (prev == next) {
count++;
}
prev = next;
}
return count;
}
```
10. You should use a `Set` rather than a `List` if you wanted to avoid duplicates or wanted to be able to search the collection quickly.

11. You should use a `TreeSet` when you want to keep the data in sorted natural order. You should use `HashSet`s with non-`Comparable` types or when order doesn't matter, to get the fastest searching time.

12. You can examine every element of a `Set` using an iterator or a for-each loop.

13. After the code executes, the set contains the following elements (in some order):

```[32, 90, 9, 182, 29, 12]
```
14. To do a union, use the `addAll` method to add one set's contents to the other. To do an intersection, use the `retainAll` method to remove elements not common to both sets.

15. Output produced when the `mystery` method is passed each list:
1. `[amanda, helene, jessica]`
2. `[riley]`
3. `[alex, charlie, phil, roy, tyler]`
16. Code to declare a `Map` that associates people's names with their ages:

```Map<String, Integer> ageMap = new TreeMap<String, Integer>();
ageMap.put("Stuart", 85);
ageMap.put("Marty", 12);
ageMap.put("Amanda", 25);
```
17. You can examine every key of a `Map` by calling the `keySet` method and then iterating or for-eaching over the `keySet`. You can examine every value of a `Map` by calling the `values` method and then iterating or for-eaching over that collection of values, or by looking up each associated value using the keys from the `keySet`.

18. Keys and values contained in the map after the code executes:

```{79=Seventy-nine, 8=Ocho, 132=OneThreeTwo, 50=Fifty, 98=Ninety-eight, 86=Eighty-six}
```
19. Output produced when the `mystery` method is passed each map:
1. `{cinq=five, deux=two, four=quatre, one=un, three=trois}`
2. `{board=skate, car=drive, computer=play}`
3. `{begin=end, boy=girl, ebert=siskel, first=last, heads=tails}`
4. `{cotton=rain, light=tree, seed=tree, tree=violin}`
20. Output produced when the `mystery` method is passed each map:
1. `{brick, plaster}`
2. `{blue, green, yellow}`
3. `{fruit}`
4. `{animal, cat, dog, ipl}`
21. Result returned when the `mystery` method is passed each pair of maps:
1. `{bar=earth, baz=wind, foo=air, mumble=fire}`
2. `{five=quatro, one=dos, three=tres}`
3. `{b=years, c=seven, e=ago, g=seven}`
22. The following method implements the new behavior in the `WordCount` program:

```public static void reverseMap(Map<String, Integer> wordCountMap) {
Map<Integer, String> reverseMap = new TreeMap<Integer, String>();

// reverse the original map
for (String word : wordCountMap.keySet()) {
int count = wordCountMap.get(word);
if (count > OCCURRENCES) {
reverseMap.put(count, word);
}
}

// print the words sorted by count
for (int count : reverseMap.keySet()) {
String word = reverseMap.get(count);
}
}
```

## Chapter 12

1. Recursion is a technique where an algorithm is expressed in terms of itself. A recursive method differs from a regular method in that it contains one or more calls to itself within its body.

2. A base case is a situation where a recursive method does not need to make a recursive call to solve the problem. A recursive case is a situation where the recursive method does call itself. Recursive methods need both cases because the recursive case is called repeatedly until the base case is reached, stopping the chain of recursive calls.

3. Output produced by the `mystery1` method by each call:

1. `1`
2. `1, 2`
3. `1, 3`
4. `1, 2, 4`
5. `1, 2, 4, 8, 16`
6. `1, 3, 7, 15, 30`
7. `1, 3, 6, 12, 25, 50, 100`
4. Output produced by the `mystery2` method by each call:

1. `113`
2. `140, 70`
3. `168, 84, 42`
4. `120, 60, 30`
5. `160, 80, 40, 20, 10`
5. Output produced by the `mystery3` method by each call:

1. `*`
2. `[*]`
3. `([*])`
4. `([([*])])`
5. `[([([*])])]`
6. Output produced by the `mysteryXY` method by each call:

1. `4`
2. `8, 4, 8`
3. `16, 8, 16`
4. `12, 8, 4, 8, 12`
5. `12, 9, 6, 3, 6, 9, 12`
7. Recursive version of `doubleReverse` method:

```public static void doubleReverse(String s) {
if (s.length() > 0) {
char last = s.charAt(s.length() - 1);
System.out.print(last);
System.out.print(last);
doubleReverse(s.substring(0, s.length() - 1));
}
}
```
8. A call stack is the structure of information about all methods that have currently been called by your program. Recursion produces a tall call stack in which each recursive call is represented.

9. The new code shown would print the lines in their original order, not reversed.

10. The new code shown would cause infinite recursion, because each recursive call just makes another recursive call and doesn't progress toward the base case.

11. The version of the `pow` method shown does not have any base case, so the recursive calls will never stop. It can be fixed by adding a check for `y == 0` that does not make a recursive call.

12. The second version of the `pow` method is more efficient than the first because it requires fewer recursive calls. Both versions are recursive.

13. Value returned by the `mystery4` method for each call:

1. `6`
2. `4`
3. `7`
4. `0`
5. `1`
14. Value returned by the `mystery5` method for each call:

1. `57`
2. `1029`
3. `-74`
4. `2438`
5. `132483`
15. Value returned by the `mystery6` method for each call:

1. `7`
2. `6`
3. `4`
4. `10`
5. `5`
16. Recursive version of `factorial` method:

```public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
```
17. The base case `if` statement has a bug: It should test for numbers less than 10, not greater. The following is the correct line:

```if (n < 10) {
```
18. When the parameters needed for recursion don't match those that make sense for the client to pass, use a public method with the signature desired by the client and a private helper method with the signature needed for the recursion.

19. The following version of the `fibonacci` code has improved efficiency:

```public static int fibonacci(int n) {
if (n <= 2) {
return 1;
} else {
return fibonacci(n, 3, 1, 1);
}
}

private static int fibonacci(int n, int i, int prev, int curr) {
if (n == i) {
return prev + curr;
} else {
return fibonacci(n, i + 1, curr, prev + curr);
}
}
```
20. A fractal is an image that is recursively constructed to contain smaller versions of itself. Recursive methods are useful when drawing fractal images because they can elegantly express the recursive nature of the images.

21. Code to create and draw a regular hexagon:

```public static void drawHexagon(Graphics g, Point position, int size) {
Polygon poly = new Polygon();
poly.addPoint(position.x, position.y + size / 2);
poly.addPoint(position.x + size / 3, position.y);
poly.addPoint(position.x + 2 * size / 3, position.y);
poly.addPoint(position.x + size, position.y + size / 2);
poly.addPoint(position.x + 2 * size / 3, position.y + size);
poly.addPoint(position.x + size / 3, position.y + size);
g.drawPolygon(poly);
}
```
22. Recursion is an effective way to implement a backtracking algorithm because the memory of decisions and points to go back to are represented by the recursive call stack. The pattern of "choose, explore, un-choose is elegantly represented by recursive calls for each individual choice.

23. A decision tree is a description of the set of choices that can be made by a recursive backtracking method at any point in the algorithm.

24. Decision tree that would have resulted for Figure 12.9 for paths to (1, 2) if the backtracking solution had explored NE first instead of last in the recursive `explore` method:

```start (0, 0)
|
+--- NE (1, 1)
|    |
|    +--- NE NE (2, 2)
|    |
|    +--- NE N (1, 2) - output
|    |
|    +--- NE E (2, 1)
|
+--- N (0, 1)
|    |
|    +--- N NE (1, 2) - output
|    |
|    +--- N N (0, 2)
|    |    |
|    |    +--- N N NE (1, 3)
|    |    |
|    |    +--- N N N (0, 3)
|    |    |
|    |    +--- N N E (1, 2) - output
|    |
|    +--- N E (1, 1)
|         |
|         +--- N E NE (2, 2)
|         |
|         +--- N E N (1, 2) - output
|         |
|         +--- N E E (2, 1)
|
+--- E (1, 0)
|
+--- E NE (2, 1)
|
+--- E N (1, 1)
|    |
|    +--- E N NE (2, 2)
|    |
|    +--- E N N (1, 2) - output
|    |
|    +--- E N E (2, 1)
|
+--- E E (2, 0)
```
25. If the solution had explored NE first instead of last, the solutions would have been printed in this order:

```moves: NE N
moves: N NE
moves: N N E
moves: N E N
moves: E N N
```
26. There are 64 entries at the second level of the full tree. There are 512 entries at the third level of the full tree.

27. If our 8 Queens algorithm tried every possible square on the board for placing each queen, there would be (64*63*62*61*60*59*58*57) = 178,462,987,637,760 entries are there at the 8th and final level of the full tree. Our algorithm avoids such a huge number of choices by only placing one queen in each column of the board.

28. The 8 Queens `explore` method stops once it finds one solution to the problem. This is because the code has the following lines around its recursive call:

```if (explore(b, col + 1)) {
return true;
}
```

The code could be modified so that it would find and output every solution to the problem by changing that code to the following:

```explore(b, col + 1);
```

And changing the base case to the following:

```if (col > b.size()) {
System.out.println("One solution is as follows:");
b.print();
return true;
}
```

## Chapter 13

1. You can perform a sequential search over the array using a loop, or you can sort the array using `Arrays.sort` and then perform a binary search over it using `Arrays.binarySearch`.

2. Closest value to the number of elements that the binary search algorithm will need to examineon an array of one million integers:

e. less than 1% (10,000 or fewer)
3. A sequential search must be used on an array of `Point` objects because they do not implement `Comparable`.

4. `Arrays.binarySearch` and `Collections.binarySearch` can be used successfully if the array or collection contains elements that are sorted, according to either their natural ordering or the ordering of a `Comparator`.

5. `Collections.sort` on a list of strings would arrange them in alphabetical order, case-sensitive. To change the order, you could pass a `Comparator` that defines a different order.

6. `Collections.sort` would not work on a list of `Point` objects by default because they do not implement the `Comparable` interface. To make it work, you could pass a `Comparator` that defines an ordering for `Point`s.

7. The `AccountComparator` shown has a few errors:

1. line 2: It should implement Comparator rather than just `Comparator`.
2. line 3: The method should be named `compare`, not `compareTo`. It should also accept two `BankAccount` parameters, not just one.
3. lines 5,7: The code should refer to the two parameters passed in, not `this`.
4. line 7: You cannot return the subtraction of two `double`s from a `compare` method. The result must be of type `int`, and it must still work even if the accounts differ only by a few cents.
Here is a corrected version of the code:

```import java.util.*;
public class AccountComparator extends Comparator<BankAccount> {
public int compare(BankAccount account1, BankAccount account2) {
if (!account1.getName().equals(account2.getName())) {
return account1.getName().compareTo(account2.getName());
} else if (account1.getBalance() < account2.getBalance()) {
return -1;
} else if (account1.getBalance() > account2.getBalance()) {
return 1;
} else {
return 0;
}
}
}
```
8. We could easily reverse the order of our `LengthComparator` by using the built-in method `Collections.reverseOrder`, which accepts a `Comparator` and returns a new one with the opposite order of the one passed in.

9. O(log N)

10. O(N)

11. O(N2)

12. O(N2)

13. O(N)

14. Complexity classes of the given algorithms in terms of N:

1. O(N)
2. O(N2)
3. O(N)
4. O(N)
5. O(log B)
6. O(N3)
7. O(N)
8. O(N)
15. Complexity classes of the given statements:

1. O(N log N)
2. O(N2)
3. O(N2 log N)
4. O(N)
5. O(1)
6. O(N)
7. O(N!)
16. The runtime complexity of both sequential searches is O(N).

17. Binary search requires a sorted dataset because it uses the ordering to jump to the next index. If the elements are out of order, the search isn't guaranteed to find the target element.

18. A binary search of 60 elements examines at most 6 elements, because log2 60 (when rounded up) equals 6.

1. The algorithm will examine index 4 and will return 4.
2. The algorithm will examine indexes 4 and 6 and will return 6.
3. The algorithm will examine indexes 4, 6, and 7 and will return 7.
4. The algorithm will examine indexes 4, 2, 1, and 0 and will return 0.
19. The algorithm will examine indexes 4, 6, and 5 and will return -1. The algorithm doesn't work properly because the input array isn't sorted.

20. The binary search algorithm will examine the following indexes and return the following values for each search:

1. 42: examines 7, 11, 9; returns 9
2. 11: examines 7, 3, 4; returns -5
3. 74: examines 7, 11, 13, 14; returns 14
4. 30: examines 7, 3, 5, 6; returns -8
21. The binary search algorithm will examine the following indexes and return the following values for each search:

1. -5: examines 6, 2, 4, 3; returns -4
2. 0: examines 6; returns 6
3. 11: examines 6, 10, 8, 9; returns -10
4. -100: examines 6, 2, 0; returns -1
22. The parameter array type should be changed to `double`. Also, a new `swap` method will be needed that accepts a `double[]` as the first parameter. Here's the new code:

```public static void selectionSort(double[] a) {
for (int i = 0; i < a.length - 1; i++) {
// find index of smallest element int smallest = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[smallest]) {
smallest = j;
}
}

swap(a, i, smallest);   // swap smallest to front
}
}
```
23. After a single pass of the selection sort algorithm (a single swap), the state of the array is:

d. `[-4, 17, 3, 94, 46, 8, 29, 12]`
24. All steps of selection sort algorithm:

1. ```[29, 17, 3, 94, 46, 8, -4, 12]
[-4, 17, 3, 94, 46, 8, 29, 12]
[-4, 3, 17, 94, 46, 8, 29, 12]
[-4, 3, 8, 94, 46, 17, 29, 12]
[-4, 3, 8, 12, 46, 17, 29, 94]
[-4, 3, 8, 12, 17, 46, 29, 94]
[-4, 3, 8, 12, 17, 29, 46, 94]
```
2. ```[33, 14, 3, 95, 47, 9, -42, 13]
[-42, 14, 3, 95, 47, 9, 33, 13]
[-42, 3, 14, 95, 47, 9, 33, 13]
[-42, 3, 9, 95, 47, 14, 33, 13]
[-42, 3, 9, 13, 47, 14, 33, 95]
[-42, 3, 9, 13, 14, 47, 33, 95]
[-42, 3, 9, 13, 14, 33, 47, 95]
```
3. ```[7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9]
[-3, 1, 6, 12, 7, 8, 4, 21, 2, 30, -1, 9]
[-3, -1, 6, 12, 7, 8, 4, 21, 2, 30, 1, 9]
[-3, -1, 1, 12, 7, 8, 4, 21, 2, 30, 6, 9]
[-3, -1, 1, 2, 7, 8, 4, 21, 12, 30, 6, 9]
[-3, -1, 1, 2, 4, 8, 7, 21, 12, 30, 6, 9]
[-3, -1, 1, 2, 4, 6, 7, 21, 12, 30, 8, 9]
[-3, -1, 1, 2, 4, 6, 7, 21, 12, 30, 8, 9]
[-3, -1, 1, 2, 4, 6, 7, 8, 12, 30, 21, 9]
[-3, -1, 1, 2, 4, 6, 7, 8, 9, 30, 21, 12]
[-3, -1, 1, 2, 4, 6, 7, 8, 9, 12, 21, 30]
```
4. ```[6, 7, 4, 8, 11, 1, 10, 3, 5, 9]
[1, 7, 4, 8, 11, 6, 10, 3, 5, 9]
[1, 3, 4, 8, 11, 6, 10, 7, 5, 9]
[1, 3, 4, 8, 11, 6, 10, 7, 5, 9]
[1, 3, 4, 5, 11, 6, 10, 7, 8, 9]
[1, 3, 4, 5, 6, 11, 10, 7, 8, 9]
[1, 3, 4, 5, 6, 7, 10, 11, 8, 9]
[1, 3, 4, 5, 6, 7, 8, 11, 10, 9]
[1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
```
25. A merge sort of 32 elements will generate 63 total calls to `mergeSort` and will perform the `merge` operation 31 times.

1. State of the elements after five passes of the outermost loop of selection sort have occurred:

```[1, 2, 3, 4, 5, 11, 9, 7, 8, 10]
```
2. Trace of merge sort algorithm:

```[7,   2,   8,   4,   1,   11,   9,   5,   3,   10]
[7,   2,   8,   4,   1], [11,   9,   5,   3,   10]
[7,   2], [8,   4,   1], [11,   9], [5,   3,   10]
, , , [4,   1], , , , [3,   10]
, ,                 , 
, [1,   4],            , [3,   10]
[2,   7], [1,   4,   8], [9,   11], [3,   5,   10]
[1,   2,   4,   7,   8], [3,    5,   9,  10,   11]
[1,   2,   3,   4,   5,   7,    8,   9,  10,   11]
```
1. State of the elements after five passes of the outermost loop of selection sort have occurred:

```[-3, -1, 1, 2, 4, 8, 7, 21, 12, 30, 6, 9]
```
2. Trace of merge sort algorithm:

```[7,   1,   6,   12,   -3,   8,    4,   21,   2,   30,   -1,   9]
[7,   1,   6,   12,   -3,   8],  [4,   21,   2,   30,   -1,   9]
[7,   1,   6], [12,   -3,   8],  [4,   21,   2], [30,   -1,   9]
, [1,   6], , [-3,   8],  , [21,   2], , [-1,   9]
, ,       [-3], ,       , ,       [-1], 
, [1,   6], , [-3,   8],  , [2,   21], , [-1,   9]
[1,   6,   7], [-3,    8,  12],  [2,   4,   21], [-1,    9,  30]
[-3,  1,   6,    7,    8,  12], [-1,   2,    4,    9,   21,  30]
[-3, -1,   1,    2,    4,   6,    7,   8,    9,   12,   21,  30]
```
26. The following statement about sorting and big-Oh is true:

b. Merge sort achieves an O(N log N) runtime by dividing the array in half at each step and then recursively sorting and merging the halves back together.
27. Traces of merge sort algorithm:

1. ```[29, 17, 3, 94, 46, 8, -4, 12]
[29, 17, 3, 94], [46, 8, -4, 12]
[29, 17], [3, 94], [46, 8], [-4, 12]
, , , , , , [-4], 
[17, 29], [3, 94], [8, 46], [-4, 12]
[3, 17, 29, 94], [-4, 8, 12, 46]
[-4, 3, 8, 12, 17, 29, 46, 94]
```
2. ```[6, 5, 3, 7, 1, 8, 4, 2]
[6, 5, 3, 7], [1, 8, 4, 2]
[6, 5], [3, 7], [1, 8], [4, 2]
, , , , , , , 
[5, 6], [3, 7], [1, 8], [2, 4]
[3, 5, 6, 7], [1, 2, 4, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
```
3. ```[33, 14, 3, 95, 47, 9, -42, 13]
[33, 14, 3, 95], [47, 9, -42, 13]
[33, 14], [3, 95], [47, 9], [-42, 13]
, , , , , , [-42], 
[14, 33], [3, 95], [9, 47], [-42, 13]
[14, 33], [3, 95], [9, 47], [-42, 13]
[3, 14, 33, 95], [-42, 9, 13, 47]
[-42, 3, 9, 13, 14, 33, 47, 95]
```

## Chapter 14

1. Statement that is true about stacks and queues:

c. A queue's remove method removes and returns the element at the front of the queue.
2. A real-world example of data that could be modeled using a stack is the plates in a cafeteria, or the undo/redo feature of a software application. A real-world example of a queue is the waiting line at a fast-food restaurant.

3. When you push onto a stack, the new element is added to the top. When you pop from a stack, the top element is removed and returned.

4. When you add to a queue, the new element is added to the back. When you remove from a queue, the front element is removed and returned.

5. The value 3 will be returned from the stack.

6. The value 1 will be returned from the queue.

7. The problem with the code is that `Queue` is an interface, so it cannot be instantiated. Instead, construct a `LinkedList` object:

```Queue<Integer> q = new LinkedList<Integer>();
```
8. ```Stack<String> stack = new Stack<String>();
stack.push("hello");
stack.push("hi");
stack.push("goodbye");
stack.push("howdy");
System.out.println(stack);
```
9. ```Stack<Integer> stack = new Stack<Integer>();
for (int i = 100; i >= 0; i -= 2) {
stack.push(i);
}
System.out.println(stack);
```
10. ```Queue<String> queue = new LinkedList<String>();
queue.add("alpha");
queue.add("beta");
queue.add("gamma");
queue.add("delta");
System.out.println(queue);
```
11. To access elements in the middle of a stack or queue, you must remove/pop out elements until you reach the one you're looking for. In many cases, it's important to save the removed elements somewhere so that you can put them back into the stack or queue when you are done.

12. Stacks and queues are still useful despite their limited functionality because they are simple and easy to use, and because their operations are all efficient to execute. Many common operations are also naturally represented as a stack or queue.

13. The code produces the following output:

```[you, are, how]
```
14. ```10
7
5
false
2
3
8
3
```
15. The code produces the following output:

```2
10
10
4
6
6
3
```
16. Output produced by the `mystery1` method by each call:

1. `[1, 1, 6, 6, 2, 2]`
2. `[9, 9, 15, 15, 4, 4, -3, -3, 42, 42]`
3. `[40, 40, 50, 50, 60, 60, 10, 10, 20, 20, 30, 30]`
17. Output produced by the `mystery2` method by each call:

1. `[1, 3, 5] [2, 4, 6]`
2. `[-3, 15, 9, 71] [42, 4]`
3. ` [30, 20, 10, 60, 50, 40, 0]`
18. Output produced by the `mystery3` method by each call:

1. `[-1, -3, -5]`
2. `[-42, -4, -71]`
3. `[-10, -60, -50]`
19. The problem with the code is that the size of the queue is changing while the loop goes over it. Another problem with the code is that it destroys the contents of the queue being examined. The following version of the code fixes both problems:

```int sum = 0;
Queue<Integer> backup = new LinkedList<Integer>();
int largest = q.remove();
int size = q.size();
for (int i = 0; i < size; i++) {
int n = q.remove();
largest = Math.max(largest, n);
backup.add(n);
}
while (!backup.isEmpty()) {
q.add(backup.remove());
}
```
20. The problem with the code is that it calls the `remove` method twice on each element, which double-removes it and therefore skips elements. Another problem with the code is that it destroys the contents of the stack being examined. The following version of the code fixes both problems:

```int sum = 0;
Queue<Integer> backup = new LinkedList<Integer>();
while (!q.isEmpty()) {
int n = q.remove();
if (n > 0) {
sum += n;
}
backup.add(n);
}
while (!backup.isEmpty()) {
q.add(backup.remove());
}
```
21. The problem with the code is that it puts the odd elements back at the top of the stack each time, so it will never make progress down the stack toward the bottom. If the stack contains any odd elements, the code will get stuck in an infinite loop. The following version of the code fixes the problem:

```Stack<Integer> backup = new Stack<Integer>();
while (!s.isEmpty()) {
int n = s.pop();
if (n % 2 != 0) {
backup.push(n);
}
}
while (!backup.isEmpty()) {
s.push(backup.pop());
}
```
22. ```public static void print(Queue<Integer> queue) {
for (int i = 0; i < queue.size(); i++) {
int n = queue.remove();
System.out.println(n);
queue.add(n);
}
}
```
23. ```public static void printLongest(Stack<String> stack) {
Stack<String> backup = new Stack<String>();
String longest = stack.pop();
backup.push(longest);
while (!stack.isEmpty()) {
String s = stack.pop();
if (s.length() > longest.length()) {
longest = s;
}
backup.push(s);
}
while (!backup.isEmpty()) {   // restore stack
stack.push(backup.pop());
}
System.out.println(longest);
}
```

## Chapter 15

1. An array list's size is the number of elements that have been added to it. Its capacity is the length of its internal array. The size is always less than or equal to the capacity.

2. The ArrayIntList class keeps at least two fields: an array of elements and a size. The array is necessary because it is where we store the data inside the collection. The size is necessary because some of the elements at the end of the array may not be meaningful values. If we removed the size field, we would not know how many elements were meaningful.

3. If the fields were static, all lists would share the same array and size. Any modification to one list would also be seen in all other lists. The client's output would be the following:

```[1, 82, 97, 7, -8]
[1, 82, 97, 7, -8]
```
4. In this section's version of the list class, if the client tries to add too many values, the code crashes with an out of bounds exception.

5. We use a `toString` method because this is the standard way of printing objects in Java. It is also more versatile than a `print` method because it can print the text representation of the list to any target, such as a file or GUI.

6. Having accessor methods such as `size` is better than making the fields public because it preserves the encapsulation of the object. As discussed in Chapter 8, this improves the cleanliness of the abstraction of the object and would allow us to change the implementation later if so desired.

7. It is most expensive to insert or remove at the beginning of the list, because all elements must be shifted to the right by one index.

8. ```public int min() {
if (size == 0) {
throw new IllegalStateException();
}
int minValue = elementData;
for (int i = 1; i < size; i++) {
minValue = Math.min(minValue, elementData[i]);
}
return minValue;
}

public int max() {
if (size == 0) {
throw new IllegalStateException();
}
int maxValue = elementData;
for (int i = 1; i < size; i++) {
maxValue = Math.max(maxValue, elementData[i]);
}
return maxValue;
}
```
9. The preconditions are that the client will not try to construct a list with a negative capacity, and that the client will never pass an index that is negative or outside the size of the list.

10. The `checkIndex` method tests whether a given index is between 0 and the size of the list, and if not, throws an exception. If the client passes an invalid index by mistake, the method will halt the program's execution.

11. The `checkCapacity` method tests whether the array's size will exceed the length of the internal array (capacity), and if so, throws an exception. If the client adds too many elements to the list, the method will halt the program's execution.

12. With our preconditions, we may now assume that `size <= capacity` at all times. We can also assume all index parameters passed to various methods are valid once they get through the `checkIndex` test.

13. These methods are provided as a convenience to the client, to give the list object a more simple and pleasant external interface to use.

14. The list doubles in size when it exceeds its capacity. This is done instead of resizing by a constant amount so that the overall cost of adding elements to the end of a list will be amortized to be O(1), constant time.

15. An iterator provides a standard way of examining the elements of a collection.

16. The iterator keeps track of the list to examine, the current index in the list, and whether it is safe to remove an element from the list using the iterator.

17. The iterator knows there are more elements to examine if its current index is below the size of the list. If there is no such element but the client calls next, an exception is thrown.

18. The precondition of `remove` is that the method `next` has been called and that `next` was called more recently than any other call to `remove`. The precondition is enforced by a `boolean` flag in the iterator whose value is changed on every call to `next` or `remove`. If the precondition is violated, an exception is thrown.

19. ```public int sum() {
int total = 0;
for (int i = 0; i < size; i++) {
total += elementData[i];
}
return total;
}
```
20. ```public double average() {
if (isEmpty()) {
return 0.0;
} else {
return (double) sum() / size;
}
}
```
21. Java does not allow the construction of arrays of generic types. To work around this, we instead create an array of `Object[]` and cast it to type `E[]`.

22. Instead of 0, we fill all of our empty cells of type `E` with `null`.

23. We must modify `indexOf` to compare objects using `equals` rather than `==` because `==` compares only references and not the state of the objects.

24. An annotation is a special directive to the compiler with additional information about a class, method, or other structure. Annotations help us when writing our generic list because we can instruct the compiler not to warn us about potentially unsafe casting operations.

25. It is important to set the removed/cleared elements to `null` so that Java's garbage collector can potentially reclaim their memory.

26. When the iterator is an inner class, it can directly access the fields of the enclosing list object. This makes it easier for the iterator to do its work without keeping track of as much state.

## Chapter 16

1. The difference between a linked list and an array list is that while an array list stores all of its elements in a single large array, a linked list stores each element inside its own container object called a node. The nodes are connected (linked) to each other by references. The two kinds of lists are similar in that they both implement the same external operations to clients, such as methods for adding, removing, accessing, and locating elements.

2. A node is a small object that stores a single element of a linked list. The list object stores reference(s) to a small number of nodes, perhaps only the front of the list. The front contains a chain of references that connect to the other elements of the list.

3. The `next` field of the last node of a list, as well as any unspecified `next` field, stores `null`.

4. When the client tries to go past the end of a linked list, there will be a null pointer exception.

5. ```           +----+----+    +----+----+
list ----> |  1 |  +----> |  3 |  / |
+----+----+    +----+----+
```
6. ```           +----+----+    +----+----+    +----+----+
list ----> |  1 |  +----> |  3 |  +----> |  2 |  / |
+----+----+    +----+----+    +----+----+
```
7. ```           +----+----+    +----+----+
list ----> |  4 |  +----> |  3 |  / |
+----+----+    +----+----+
```
8. ```           +----+----+    +----+----+
list ----> |  1 |  +----> |  2 |  / |
+----+----+    +----+----+
```
9. ```list.next.next = new ListNode(3, null);   // 2 -> 3
```
10. ```list = new ListNode(3, list);   // 3 -> 1  and  list -> 3
```
11. ```temp.next.next = list.next;   // 4 -> 2
list.next = temp;             // 1 -> 3
```
12. ```ListNode list2 = list;          // list2 -> 1
list = list.next;               // list -> 2
list2.next = list2.next.next;   // 1 -> 3
list.next = null;               // 2 /
```
13. ```ListNode temp = list;    // temp -> 5
list = list.next;        // list -> 4
temp.next = list.next;   // 5 -> 3
list.next = temp;        // 4 -> 5
```
14. ```ListNode temp = list.next.next;   // temp -> 3
temp.next = list.next;            // 3 -> 4
list.next.next = list;            // 4 -> 5
list.next.next.next = null;       // 5 /
list = temp;                      // list -> 3
```
15. ```list.next.next.next = temp;        // 3 -> 4
temp.next.next = list.next.next;   // 5 -> 3
list.next.next = null;             // 2 /
ListNode temp2 = temp.next;        // temp2 -> 5
temp.next = list.next;             // 4 -> 2
list = temp2;                      // list -> 5
```
16. ```list2.next.next.next = list;   // 4 -> 1
list.next = list2;             // 1 -> 2
list = list2.next.next;        // list -> 4
list2 = list2.next;            // list2 -> 3
list2.next = null;             // 3 /
list.next.next.next = null;    // 2 /
```
17. ```ListNode list2 = list.next.next;        // list2 -> 3
list.next.next.next.next = list.next;   // 4 -> 2
ListNode temp = list;                   // temp -> 1
list = list.next.next.next;             // list -> 4
list2.next = temp;                      // 3 -> 1
list.next.next = null;                  // 2 /
list2.next.next = null;                 // 1 /
```
18. The two ways to change an object of our linked list class are to change its front reference or to change the next or data field of an existing node.

19. Inserting and removing is most expensive at the end of the list, because the code must loop through all of the next references to reach the end. This is the opposite of the array list, which inserts/removes most slowly at the start because of the shifting of elements that is required.

20. The loop should stop and index `i - 1`, the index before the one to add or remove. This is so that you can adjust the preceding node's next reference.

21. Resizing is not necessary for a linked list, since more nodes can be dynamically allocated. The only limit on the number of elements is the amount of memory available to the Java virtual machine.

22. ```ListNode current = list;
while (current != null) {
current.data = 42;
current = current.next;
}
```
23. ```ListNode current = list;
while (current.next != null) {
current = current.next;
}
current.data = 42;
```
24. ```ListNode current = list;
while (current.next != null) {
current = current.next;
}
current.next = new ListNode(42);
```
25. ```public int min() {
if (front == null) {
throw new IllegalStateException();
} else {
int minValue = front.data;
ListNode current = front.next;
while (current != null) {
minValue = Math.min(minValue, current.data);
current = current.next;
}
return minValue;
}
}

public int max() {
if (front == null) {
throw new IllegalStateException();
} else {
int maxValue = front.data;
ListNode current = front.next;
while (current != null) {
maxValue = Math.max(maxValue, current.data);
current = current.next;
}
return maxValue;
}
}
```
26. The four cases examined by the `addSorted` method are: the typical case in the "middle" of the list; inserting at the back of the list; inserting at the front; and the empty list case.

27. The "inchworm approach" is when an algorithm keeps track of two linked node references, one for the previous node and one for the current node. They are moved forward together over the list until a particular position is reached. At that point, the previous reference is modified as appropriate. One advantage of this approach is that you do not need to write complex chains of dereferences such as `current.next.data`.

28. ```public int sum() {
int total = 0;
ListNode current = front;
while (current != null) {
total += current.data;
current = current.next;
}
return total;
}

public double average() {
if (front == null) {
return 0.0;
} else {
int total = 0;
int count = 0;
ListNode current = front;
while (current != null) {
total += current.data;
current = current.next;
count++;
}
return (double) total / count;
}
}
```
29. The main advantage of the `IntList` interface is that client code can take advantage of polymorphism. A client program can deal with an `IntList` reference and the actual object at runtime can be an instance of either kind of list.

30. ```public void firstLast(IntList list) {
if (!list.isEmpty()) {
int element = list.get(0);
list.remove(0);
list.add(element);
}
}
```
31. When changing the linked list to store elements of type `E`, the list class, its nested classes, and several methods must be changed to use the new generic type. We must change any comparisons between objects to use `equals` instead of `==`. In our code, we also use dummy header nodes and add a `back` reference to increase the efficiency when adding to the end of the list.

32. Iterators are important with linked lists because it is inefficient to traverse a linked list by calling the `get` method once for each index. Such an algorithm must repeatedly traverse the entire list to each index passed. The iterator instead remembers its position between calls to `next`.

33. The linked list iterator keeps a reference to its current node and a `boolean` for whether it is safe to remove an element. The iterator knows there are more elements by looking at the `next` reference of its current node.

## Chapter 17

1. A tree has only one root. A tree could have more leaves than branches (for example, a perfect tree of height 3) or could have more branches than leaves (for example, a tree whose root has two child nodes, each of which has one child, each of which has one child).

2. Twice as many leaves as branches:

```      +---+
| 1 |
+---+
/     \
/       \
+---+       +---+
| 2 |       | 3 |
+---+       +---+
```

Same number of leaves as branches:

```            +---+
| 1 |
+---+
/     \
/       \
+---+       +---+
| 2 |       | 3 |
+---+       +---+
/           /     \
/           /       \
+---+        +---+     +---+
| 4 |        | 5 |     | 6 |
+---+        +---+     +---+
```
1. 3 levels
2. 3 branches: Nodes 3, 5, and 2
3. 3 leaves: Nodes 1, 4, and 6
4. The node containing 3 is the root.
5. Node 5 is the sibling of Node 2. Nodes 4 and 6 are the children of Node 2.
• preorder: 3 5 1 2 4 6
• inorder: 1 5 3 4 2 6
• postorder: 1 5 4 6 2 3
• preorder: 19 47 23 -2 55 63 94 28
• inorder: 23 47 55 -2 19 63 94 28
• postorder: 23 55 -2 47 28 94 63 19
• preorder: 2 1 7 4 3 5 6 9 8
• inorder: 2 3 4 5 7 1 6 8 9
• postorder: 3 5 4 7 8 9 6 1 2
3. If we removed the `root != null` test from the `printPreorder` method, the method would eventually crash when trying to dereference `root` to examine its data or to make a recursive call.

4. ```public void printPostorder() {
System.out.print("postorder:");
printPostorder(overallRoot);
System.out.println();
}

private void printPostorder(IntTreeNode root) {
if (root != null) {
printPostorder(root.left);
printPostorder(root.right);
System.out.print(" " + root.data);
}
}
```
5. ```public void printMirror() {
System.out.print("mirror:");
printMirror(overallRoot);
System.out.println();
}

private void printMirror(IntTreeNode root) {
if (root != null) {
printMirror(root.right);
System.out.print(" " + root.data);
printMirror(root.left);
}
}
```
6. Many tree methods use a public/private pair because the algorithms are best implemented recursively, but each recursive call must examine a progressively smaller portion of the tree. Therefore the header of the private method generally accepts a tree node as an additional parameter.

7. ```public int size() {
return size(overallRoot);
}

private int size(IntTreeNode root) {
if (root == null) {
return 0;
} else {
return 1 + size(root.left) + size(root.right);
}
}
```
8. ```public int min() {
if (overallRoot == null) {
throw new IllegalStateException("empty tree");
}
return min(overallRoot);
}

private int min(IntTreeNode root) {
if (root.left == null && root.right == null) {
return root.data;
} else {
int minValue = root.data;
if (root.left != null) {
minValue = Math.min(minValue, min(root.left));
}
if (root.right != null) {
minValue = Math.min(minValue, min(root.right));
}
return minValue;
}
}
```
```// max is written in the same fashion as min, but with 'max'
// in place of 'min' everywhere in the code.
public int max() {
if (overallRoot == null) {
throw new IllegalStateException("empty tree");
}
return max(overallRoot);
}

private int max(IntTreeNode root) {
if (root.left == null && root.right == null) {
return root.data;
} else {
int maxValue = root.data;
if (root.left != null) {
maxValue = Math.max(maxValue, max(root.left));
}
if (root.right != null) {
maxValue = Math.max(maxValue, max(root.right));
}
return maxValue;
}
}
```
9. ```public int countBranches() {
return countBranches(overallRoot);
}

private int countBranches(IntTreeNode root) {
if (root == null ||
(root.left == null && root.right == null)) {
return 0;
} else {
return 1 + countBranches(root.left) +
countBranches(root.right);
}
}
```
10. A binary search tree is one that is ordered such that smaller nodes appear to the left and larger nodes appear to the right.

11. Valid binary search trees: (b), if duplicates are allowed; (c); and (e).

12. An in-order traversal of a BST will examine the elements in their sorted order. For example, in-order traversal of a BST of integers will visit the integers in increasing numerical order.

13. Resulting tree:

```                          +--------+
|  Leia  |
+--------+
/               \
/                         \
+--------+                               +--------+
|  Boba  |                               |  R2D2  |
+--------+                               +--------+
\                                /
\                              /
+--------+                    +--------+
| Darth  |                    |  Luke  |
+--------+                    +--------+
/       \
/         \
+--------+   +--------+
| Chewy  |   |  Han   |
+--------+   +--------+
\
\
+--------+
| Jabba  |
+--------+
```
• Pre-order: Leia, Boba, Darth, Chewy, Han, Jabba, R2D2, Luke
• In-order: Boba, Chewy, Darth, Han, Jabba, Leia, Luke, R2D2
• Post-order: Chewy, Jabba, Han, Darth, Boba, Luke, R2D2, Leia
14. Resulting tree:

```                      +-----+
| Meg |
+-----+
/         \
/             \
+-----+             +--------+
| Joe |             | Stewie |
+-----+             +--------+
/      \               /
/        \             /
+-------+      +------+      +-------+
| Brian |      | Lois |      | Peter |
+-------+      +------+      +-------+
\                           \
\                           \
+-----------+                  +----------+
| Cleveland |                  | Quagmire |
+-----------+                  +----------+
```
• Pre-order: Meg, Joe, Brian, Cleveland, Lois, Stewie, Peter, Quagmire
• In-order: Brian, Cleveland, Joe, Lois, Meg, Peter, Quagmire, Stewie
• Post-order: Cleveland, Brian, Lois, Joe, Quagmire, Peter, Stewie, Meg
15. Resulting tree:

```                  +------------+
|    Kirk    |
+------------+
/                  \
/                        \
/                              \
+------------+                      +------------+
|   Chekov   |                      |   Spock    |
+------------+                      +------------+
\                        /          \
\                      /            \
\                    /              \
+------------+         +------------+   +------------+
|  Khaaaan!  |         |   Scotty   |   |   Uhuru    |
+------------+         +------------+   +------------+
/                 /
/                 /
/                 /
+------------+   +------------+
|   McCoy    |   |    Sulu    |
+------------+   +------------+
```
• Pre-order: Kirk, Chekov, Khaaaan!, Spock, Scotty, McCoy, Uhuru, Sulu
• In-order: Chekov, Khaaaan!, Kirk, McCoy, Scotty, Spock, Sulu, Uhuru
• Post-order: Khaaaan!, Chekov, McCoy, Scotty, Sulu, Uhuru, Spock, Kirk
16. Resulting tree:

```                  +------------+
|    Lisa    |
+------------+
/                  \
/                        \
/                              \
+------------+                      +------------+
|    Bart    |                      |   Marge    |
+------------+                      +------------+
\                    /              \
\                  /                \
\                /                  \
+------------+    +------------+    +------------+
|    Homer   |    |   Maggie   |    |  Smithers  |
+------------+    +------------+    +------------+
/                                      /
/                                      /
/                                      /
+------------+                          +------------+
|  Flanders  |                          |  Milhouse  |
+------------+                          +------------+
```
• Pre-order: Lisa, Bart, Homer, Flanders, Marge, Maggie, Smithers, Milhouse
• In-order: Bart, Flanders, Homer, Lisa, Maggie, Marge, Milhouse, Smithers
• Post-order: Flanders, Homer, Bart, Maggie, Milhouse, Smithers, Marge, Lisa
17. The `add` method needs to return the newly added node to enable the `x = change(x)` pattern. If no reference to the new node is returned, it is not possible to attach that new node to the rest of the tree. Such attachment is crucial to the working of the algorithm.

18. The `x = change(x)` pattern is an algorithmic strategy where a recursive method (such as a binary tree method) will accept a node's initial state as a parameter and will then return the node's new state as its result. This returned result will be stored by the client back into its original place of reference. This allows recursive methods to return modified versions of trees using elegant code that follows the "zen" of recursion.

19. The `contains` method is efficient on BSTs and needs to go at most one direction in each recursive call. Each call advances one level in the tree, so the total number of calls / advancements is the height of the tree, or N. This is logarithmic with respect to the total number of nodes in the tree (its size).

20. This second version of `contains` is much less efficient than the one written in the chapter. It goes both to the left and to the right recursively to find the value, but this does not take advantage of the sortedness of the tree. It will have linear O(N) runtime rather than the much faster O(log N) desired runtime of our original method.

21. ```public int min() {
if (overallRoot == null) {
throw new IllegalStateException("empty tree");
}
return min(overallRoot);
}

private int min(IntTreeNode root) {
if (root.left == null) {
return root.data;
} else {
return min(root.left);
}
}

public int max() {
if (overallRoot == null) {
throw new IllegalStateException("empty tree");
}
return max(overallRoot);
}

private int max(IntTreeNode root) {
if (root.right == null) {
return root.data;
} else {
return max(root.right);
}
}
```
22. When converting the tree to store type `E`, we must add a type parameter to the class header. This parameter must be `Comparable`. When examining whether a given element is too small or large (whether to go left or right recursively) in methods such as `add` or `contains`, we must call `compareTo` instead of using the `<` and `>` operators that do not work with objects.

23. To add a tree iterator, each node would need to have a reference to the "next" node after it, so that the nodes could be traversed in a left-to-right order. Another solution would be for nodes to have references to their parents so that the iterator could go back up the tree as necessary when traversing through the elements.

## Chapter 18

1. Hashing is a process of mapping element values to integer indexes and storing the elements at those indexes in an array. Hashing is a good way of implementing a set because it provides theoretically O(1) runtime for adding, removing, and searching a set.

2. The following statement about hash tables is true:

d. A hash function maps element values to integer indexes in the hash table.
3. A hash table being "full" depends on what strategy is used to resolve collisions. If probing is used, the table is literally full when it has no empty buckets for storing elements, but often it is considered to be too full when its load factor (the ratio of its size to its array capacity) reaches some maximum like 0.75 or 0.66. A hash table that uses separate chaining is never literally full because elements can be added indefinitely to each bucket's linked list, but it still resizes once the load factor reaches some threshold.

4. The code shown is incorrect because it just copies over every element from the hash table into the same index in the new larger array. This may lead to elements being at the wrong index, because the proper index is based on the element's hash code modded by the array length. For example, the value 37 would be at index 7 in an array of size 10, but in a larger array of size 20 it should be at index 17.

5. After adding the elements, the hash table's state is the following:

```   0   1   2   3   4   5   6   7   8   9
[ 80,  0,  2, 42,  0, 35, 15, 95, 66,  0]
```
6. After adding the elements, the hash table's state is the following:

```   0   1   2   3   4   5   6   7   8   9
[  |,  /,  |,  /,  /,  |,  |,  /,  /,  /]
80      42          95  66
|           |
2          15
|
35
```
7. After adding the elements, the hash table's state is the following:

```   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19
[  0,  0, 32,  0, 24,  5, 44, 47,  0,  0,  0,  0,  0,  X,  0,  X,  0, 17,  0,  0]
size = 6
capacity = 20
load factor = 0.3
```
8. After adding the elements, the hash table's state is the following:

```   0   1   2   3   4   5   6   7   8   9  10
[  0,  0,  0,  0, 70, 82, 50, 39, 15, 29, 18]
size = 7
capacity = 11
load factor = 0.636
```
1. This is a legal `hashCode` implementation, according to the contract. It distributes hash codes somewhat well, but it has certain groups of points that will collide with each other unnecessarily (for example, every point with an x-coordinate or y-coordinate of 0 will have the same hash code).
2. This is a legal `hashCode` implementation, according to the contract. But it distributes hash codes extremely poorly; literally it could not be worse in that respect, because every point has the same hash code. It's important to note that it is still a technically correct implementation, though it works very poorly in terms of hash table performance.
3. This is not a legal `hashCode` implementation, according to the contract. It does not consistently return the same hash code for the same point object state.
9. `hashCode` method for a `Date` class (the constant multipliers for each component are somewhat arbitrary):

```public int hashCode() {
return 1331 * year + 37 * month + day;
}
```
10. `hashCode` method for a `Student` class (the constant multipliers for each component are somewhat arbitrary):

```public int hashCode() {
return 373 * name.hashCode() +
1341 * studentID +
31 * Double.valueOf(weight).hashCode();
}
```
11. After adding the key/value pairs, the hash table's state is the following:

```   0   1   2   3   4   5     6        7      8   9  10  11  12    13       14        15      16  17  18  19
[  /,  /,  /,  /,  X,  /, 6=Tina, 7=Meghan,  /,  /,  /,  /,  /, 33=Kona, 34=Tyler, 15=Daisy,  /,  X,  /,  /]

size = 5
capacity = 20
load factor = 0.4
```
12. The following statement about min-heaps is true:

b. The smallest value is the root.
13. If a binary heap has 26 nodes, its height is 5. If it has 73 nodes, its height is 7. We know for sure because every heap is a complete tree, so its shape and height are predictable given its size. The height of a heap of size N will always be equal to ceil(log2 N).

1. Invalid; the value 9 cannot be below 12.
2. Invalid; not a complete binary tree.
3. Valid.

14. For our heap implementation, an element at index 8 of the array has its children at indexes 16 and 17. Its parent is at index 4. An element at index 23 has its children at indexes 46 and 47, and its parent at index 11.

15. The min-heap after 21 is added:

```              12
/        \
29             21
/    \          /  \
30      39       72  91
/  \    /  \     /
55  64  40  99   84
```
16. The min-heap after 7 is added:

```               7
/        \
29             12
/    \          /  \
30      39       21  91
/  \    /  \     /  \
55  64  40  99   84  72
```
17. The resulting binary min-heap after all adds is the following:

```        2
/   \
3       4
/ \     / \
6   7   5   8
/
9
```
18. The resulting binary min-heap after each of the three removals is the following. After first removal:

```        3
/   \
6       4
/ \     / \
9   7   5   8
```

After second removal:

```        4
/   \
6       5
/ \     /
9   7   8
```

After third removal:

```        5
/   \
6       8
/ \
9   7
```
19. The resulting binary min-heap after all adds is the following:

```            1
/     \
3           7
/   \        / \
8     11    15   12
/ \
14   9
```
20. The resulting binary min-heap after each of the three removals is the following. After first removal:

```            3
/     \
8           7
/   \        / \
9     11    15   12
/
14
```

After second removal:

```            7
/     \
8           12
/   \        / \
9     11    15   14
```

After third removal:

```            8
/     \
9           12
/   \        /
14     11    15
```
21. The array does not begin with its root at 1. (The array also contains some incorrect element values, but that's an error on the part of the authors. Oh well.) The proper array state is the following:

```  0   1   2   3   4   5   6   7   8   9  10  11  12
[ /, 12, 29, 70, 30, 39, 84, 91, 55, 64, 40, 99, ...]
```
22. Heap represented by the given array:

```            29
/      \
41          30
/  \        /  \
55    68    37    41
/
80
```
23. Array representation of the heap from Self-Check #19:

```  0  1  2  3  4  5  6  7  8  9
[ /, 2, 3, 4, 6, 7, 5, 8, 9, ...]
```
24. Array representation of the heap from Self-Check #21:

```   0   1   2   3   4   5   6   7   8   9  10
[  /,  1,  3,  7,  8, 11, 15, 12, 14,  9, ...]
```

## Chapter 19

1. Because functional programming focuses so much on individual functions, the community of programmers who use functional programming regularly have concluded that side effects should be avoided when possible.

2. Calling `System.out.println` is considered a side effect because it produces a noticeable outcome, namely printing output to the console. So you can detect whether a given function was called or not by looking for output. This doesn't mean that printing output is a bad thing, merely that it is a side effect.

3. The function's side effect is that it modifies the array that was passed in. It could be changed to remove side effects by having it return the new array state rather than changing the existing array.

```// Returns a new array whose values are twice as large as
// the values of all elements in the given array.
public static int[] doubleAll(int[] a) {
int[] result = new int[a.length];
for (int i = 0; i < a.length; i++) {
result[i] = 2 * a[i];
}
return result;
}
```
4. Rewritten version of the program with no side effects:

```public class SideEffect2 {
public static int f(int x, int n) {
x = x * 2;
return x + n;
}

public static void main(String[] args) {
int x = 5;
int result = f(x, 5) + f(x, 5);
System.out.println(result);
}
}
```
5. To support subtraction problems, we must call `giveProblems` and pass a lambda function that does subtraction, such as:

```giveProblems(console, 3, "-", (x, y) -> x * y);
```
6. ```(x) -> x * x
```
7. ```(a, b) -> (a > b ? a : b)
```
8. ```(first, last) -> (last + ", " + first)
```
9. A stream is not the same as an array. Both can be thought of as containing a collection of elements. But streams do not support mutating data, and you can only access an element at a time, not random access like in an array.

10. The variable `result` stores 4.

11. ```int sum = Arrays.stream(a)
.map(n -> -n)
.sum();
```
12. ```int evens = (int) Arrays.stream(a)
.filter(n -> n % 2 == 0)
.count();
```
13. The variable `result` stores 44.

14. The code does not compile because it returns an optional result. You must call `getAsDouble` to retrieve the actual double value:

```double avg = DoubleStream.of(3.1, -4.5, 8.9, -6.2, 1.0)
.map(n -> Math.abs(n))
.average()
.getAsDouble();
```
15. A bound variable is inside the lambda, typically one of its parameters. A free variable is a variable referred to in the lambda's code that is declared outside the lambda and enclosed into its closure.

16. The free variables are `a` and `b`, and the bound variables are `c` and `d`.

17. The code is not allowed to modify the free variable `a`. The code could be modified as follows:

```int a = 10;
int b = 20;
int sum = IntStream.of(1, 2, 3, 4, 5)
.map(n -> n + b - (a + 1))
.sum();
```
18. The code produces the following output:

```10
28
33
28
49
56
49
```
19. ```// this version will not print duplicate values
Arrays.stream(a)
.map(Math::abs)
.distinct()
.forEach(System.out::println);
```
20. ```// retain the positive integers only
int[] positives = Arrays.stream(a)
.filter(n -> n > 0)
.toArray();
```
21. ```// print all four-letter words in the list:
list.stream()
.filter(s -> s.length() == 4)
.forEach(System.out::println);
```
22. ```// print all lines from notes.txt that are at least 40 chars long
Files.lines(Paths.get("notes.txt"))
.filter(line -> line.length() >= 40)
.forEach(System.out::println);
```
23. The code has four problems: (1) The `Files.lines` method accepts a path, not a string; (2) The `map` call should be `mapToInt`; (3) The `max` call needs to be followed by a call to `getAsInt` because it returns an optional integer result; and (4) The overall method must have `throws IOException` in its header. The corrected code is:

```// Returns the length of the longest line in the given file.
// Assumes that the file contains at least one line.
public static int longestLineLength(String filename) throws IOException {
return Files.lines(Paths.get(filename))
.mapToInt(String::length)
.max()
.getAsInt();
}
```