Building Java Programs, 3rd 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.
  5. 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.
  6. The legal identifiers shown are println, AnnualSalary, ABC, sum_of_data, _average, and B4.
  7. d. System.out.println("Hello, world!");

  8. Output of statements: 

    "Quotes"
Slashes \//
How '"confounding' "\" it is!

  9. Output of statements: 

    name    age     height
Archie  17      5'9"
Betty   17      5'6"
Jughead 16      6'

  10. Output of statements: 

    Shaq is 7'1
The string "" is an empty message.
\'""

  11. Output of statements: 

           a       b       c
\\
'
"""
C:
in      he downward spiral

  12. Output of statements: 

    Dear "DoubleSlash" magazine,

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

Sincerely,
Susan "Suzy" Smith

  13. 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("\\ / \\\\ // \\\\\\ ///");

  14. 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.''");

  15. println statement to produce desired output: 

    System.out.println("/ \\ // \\\\ /// \\\\\\");

  16. 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.");

  17. Output of Commentary program: 

    some lines of code
have // characters on them
which means 
lines can also
have /* and */ characters
of comment.

  18. 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.

  19. 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.

  20. 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.
  21. b. public static void example() {

  22. Output of Tricky program: 

    This is message1.
This is message2.
This is message1.
Done with message2.
Done with main.

  23. 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

  24. 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

  25. 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

  26. 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.

  27. 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.

  28. 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.

  29. 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.

  30. 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.

  31. 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.");
    }
}

  32. 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. 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

  3. 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

  4. 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"
  5. c. double grade = 4.0; 
  6. int age;
String gender;
double height;
int weight;

  7. String year;
int numberOfCourses;
double gpa;
  8. Last digit: number % 10

  9. 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.

  11. Values of a, b, and c after the code: 

    a: 6
b: 9
c: 16

  12. Values of first and second after the code: 

    first: 19
second: 8
    The code swaps the values of the variables first and second.

  13. Rewritten shortened version of the code: 

    int first = 8, second = 19;
first += second;
second = first - second;
first -= second;

  14. Values of i, j, and k after the code: 

    i: 4
j: 2
k: 1

  15. Output of code: 

    46
36
23
13

  16. 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;

  17. 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);
    }
}

  18. 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
  20. for (int i = 1; i <= 6; i++) {
    // your code here
    System.out.println(18 * i - 22);
}

  21. Output of oddStuff method: 

    4
2

  22. Output of loop: 

    24 1
22 2
19 3
15 4
10 5

  23. Output of loop: 

    +---+
\   /
/   \
\   /
/   \
\   /
/   \
+---+

  24. Output of loop: 

    How many lines
How many lines
How many lines
are printed?

  25. Output of loop: 

    T-minus 5, 4, 3, 2, 1, Blastoff!

  26. 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

  27. Output of loops: 

             *
        ***
       *****
      *******
     *********
    ***********
   *************
  ***************
 *****************
*******************

  28. Output of loops: 

    ****!****!****!
****!****!****!

  29. Output of loops: 

    ************!
************!

  30. Output of loops: 

    *!*!*!*!
*!*!*!*!
*!*!*!*!
*!*!*!*!
*!*!*!*!
*!*!*!*!

  31. 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.)

  32. 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

  35. Table for output:

    line\!/
    10140
    22102
    3464
    4626

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.
  24. Scanner console = new Scanner(System.in);
System.out.print("Type an integer: ");
int number = console.nextInt();
System.out.println(number + " times 2 = " + (number * 2));

  25. 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);
    }
}

  26. 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:

    screenshot

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) + ".");

  24. 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.");

  25. The preconditions of printTriangleType method are that the three side lengths constitute a valid triangle. Namely:

  26. The preconditions of the getGrade method are that the grade parameter's value is between 0 and 100.

  27. 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));
}

  28. 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");
    }
    ... 
}

  29. 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++;
}

  3. 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

  4. 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

  5. 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

  6. Code that generates a random integer between 0 and 10 inclusive: 

    Random rand = new Random();
int num = rand.nextInt(11);

  7. 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: 
      /\/\/\/\/\/\/\/\

  9. 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"));

  10. public static int zeroDigits(int number) {
    int count = 0;
    do {
        if (number % 10 == 0) {
            count++;
        }
        number = number / 10;
    } while (number > 0);
    return count;
}

  11. 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);

  12. 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
}

  13. 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);
}

  14. 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
  15. 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;
}

  16. 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;
}

  17. 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;
}

  18. Improved version of startEndSame code using Boolean zen: 

    public static boolean startEndSame(String str) {
    return str.charAt(0) == str.charAt(str.length() - 1);
}

  19. Improved version of hasPennies code using Boolean zen: 

    public static boolean hasPennies(int cents) {
    return cents % 5 != 0;
}

  20. 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

  21. 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;
    }
}

  22. 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)

  23. 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);

  24. 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

  25. 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);
}

  26. 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);
  27. 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
  28. 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
  29. 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"

  11. 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

  12. 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

  13. 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

  14. Output produced if hasNextInt and nextInt are used: 

    0 total

    Output produced if hasNextDouble and nextDouble are used: 

    input: 6.7
1 total

  15. 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());
        }
    }
}

  16. 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());
    }
}

  17. 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("+");
}

  18. A PrintStream object is used to write to an external file. It has methods such as println and print.

  19. 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.");

  20. 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;
}

  21. 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[10]; 
  3. int[] data = new int[5];
data[0] = 27;
data[1] = 51;
data[2] = 33;
data[3] = -1;
data[4] = 101;

  4. Code that stores all odd numbers between -6 and 38 into an array using a loop: 

    int[] odds = new int[22];
for (int i = 0; i < 22; i++) {
    odds[i] = i * 2 - 5;
}

  5. After the code is executed, the numbers array contains the following element values: 

    [0, 4, 11, 0, 44, 0, 0, 2]

  6. After the code is executed, the data array contains the following element values: 

    [3, 3, 0, 0, 6, 9, 0, -18]

  7. 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)) {
    ...

  8. Correct syntax to declare an array of six integer values:

    a. int[] a = {17, -3, 42, 5, 9, 28}; 
  9. int[] data = {7, -1, 13, 24, 6};

  10. public static int max(int[] data) {
    int max = data[0];
    for (int i = 1; i < data.length; i++) {
        if (data[i] > max) {
            max = data[i];
        }
    }
    return max;
}

  11. 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;
}

  12. 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.

  13. 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]);
}

  14. After the code is executed, the list array contains the following element values: 

    [3, 24, 8, -5, 6, 1]

  15. 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("]");
    }
}

  16. To make the count and equals methods process arrays of Strings, 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. 

  17. 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;
}

  18. 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.

  19. Output of ReferenceMystery1 program: 

    2 [0, 0, 1, 0]
1 [0, 0, 1, 0]
3 [0, 0, 1, 1]
2 [0, 0, 1, 1]

  20. Output of ReferenceMystery2 program: 

    2 [0, 1]
1 [0, 1]
1 [1, 2]
0 [1, 2]

  21. public static void swapPairs(int[] list) {
    for (int i = 0; i < list.length - 1; i += 2) {
        swap(list, i, i + 1);
    }
}

  22. After the code is executed, the numbers array contains the following element values: 

    [20, 30, 40, 50, 60, 70, 80, 90, 100, 100]

  23. After the code is executed, the numbers array contains the following element values: 

    [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]

  24. After the mystery method is executed, the arrays contain the following element values:

  25. After the mystery2 method is executed, the arrays contain the following element values:

  26. After the mystery3 method is executed, the array contains the following element values: 

    [7, 3, 1, 0, 8, 18, 5, -1, 5]

  27. Results of calls to mystery4 method:

    1. 0
    2. 9
    3. 6
    4. 8
    5. 2

  28. Final array contents after calls to mystery5 method:

    1. [8]
    2. [14, 8]
    3. [7, 2, 3, 3, 1, 4]
    4. [10, 9, 9, 6, 6]
    5. [12, 12, 11, 11, 9, 8]
  29. 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;
}

  30. 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;
}

  31. 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]]

  32. Loop to initialize the third row of data to store the numbers 1 through 7: 

    for (int i = 0; i < 7; i++) {
    data[2][i] = i + 1;
}

  33. Code that constructs a two-dimensional array of integers with 5 rows and 10 columns, filled with a multiplication table: 

    int[][] table = new int[5][10];
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 10; j++) {
        table[i][j] = i * j;
    }
}

  34. Loop to copy the contents of second column into fifth column: 

    for (int i = 0; i < 6; i++) {
    matrix[i][4] = matrix[i][1];
}

  35. 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]]

  36. int[][] jagged = new int[5][];
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++;
    }
}

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 Strings 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

  22. 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);
}

  23. 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 HashSets 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 Points.

  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 doubles 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.

  20. 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.

  21. 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

  22. 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

  23. 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
    }
}

  24. 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]

  25. 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]

  26. 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]
[7], [2], [8], [4,   1], [11], [9], [5], [3,   10]
               [4], [1],                 [3], [10]
          [8], [1,   4],            [5], [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]
[7], [1,   6], [12], [-3,   8],  [4], [21,   2], [30], [-1,   9]
     [1], [6],       [-3], [8],       [21], [2],       [-1], [9]
[7], [1,   6], [12], [-3,   8],  [4], [2,   21], [30], [-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]

  29. 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.

  30. 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]
[29], [17], [3], [94], [46], [8], [-4], [12]
[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]
[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]
[33], [14], [3], [95], [47], [9], [-42], [13]
[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. [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[0];
    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[0];
    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

    7. 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. 

    8. 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);
    }
}

    9. 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);
    }
}

    10. 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. 

    11. 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);
    }
}

    12. 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;
    }
}

    13. 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);
    }
}

    14. A binary search tree is one that is ordered such that smaller nodes appear to the left and larger nodes appear to the right.

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

    16. 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.

    17. 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

    18. 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

    19. 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

    20. 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

    21. 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.

    22. 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.

    23. 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).

    24. 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. 

    25. 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);
    }
}

    26. 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.

    27. 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.

    10. hashCode method for a Date class (the constant multipliers for each component are somewhat arbitrary): 

      public int hashCode() {
    return 1331 * year + 37 * month + day;
}

    11. 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();
}

    12. 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

    13. The following statement about min-heaps is true:

      b. The smallest value is the root.

    14. 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.

    16. 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.

    17. The min-heap after 21 is added: 

                    12
          /        \
      29             21
    /    \          /  \
  30      39       72  91
 /  \    /  \     /
55  64  40  99   84

    18. The min-heap after 7 is added: 

                     7
          /        \
      29             12
    /    \          /  \
  30      39       21  91
 /  \    /  \     /  \
55  64  40  99   84  72

    19. The resulting binary min-heap after all adds is the following: 

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

    20. 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

    21. The resulting binary min-heap after all adds is the following: 

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

    22. 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

    23. 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, ...]

    24. Heap represented by the given array: 

                  29
         /      \
      41          30
     /  \        /  \
   55    68    37    41
  /
80

    25. 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, ...]

    26. 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, ...]
    This document, all self-check problems, and their solutions are Copyright © Pearson 2013. All rights reserved.