review-bj-6

ch01

ch01/r01

A well-designed computer program is easy to use without any special knowledge.  For example, most people can learn to navigate webpages with only a few minutes of practice.  On the other hand, programming a computer requires special knowledge about what the computer can fundamentally do and how you would communicate with it through a programming language.

ch01/r02

Typically program code is stored on a hard disk, CD/DVD disc, or in some other central location across a network.   User data is often more likely to be stored on a local hard disk, although it can also be stored on a network or even a CD/DVD for backup storage.

ch01/r03

The monitor, speakers, and printer serve as the primary devices to give information to the user. The keyboard and mouse are the primary devices that take user input.

ch01/r04

It's very likely your cell phone is a programmable computer.  If you can take pictures, send email/text messages, and/or surf the web with your phone, it is a programmable computer.  If your cell phone can only send and receive phone calls, it is probably a single-function device.

ch01/r05

One advantage of Java over machine code is that Java statements are independent of the machine (computer) they are being executed on; machine code statements differ from one type of machine to the next.  Another advantage of Java is that it is much more readable and understandable (by humans) than machine code.

ch01/r06

a)Solutions here will vary based on user and IDE preference.  On a UNIX-based system using the Eclipse IDE you may see a path like 

/home/nancy/JFE/src

While on a Microsoft Windows machine you might find a directory like:

C:\Users\nancy\Documents\JFE\src

b)Again, solutions can vary.  On Unix using Eclipse you might see: 

/home/nancy/JFE/bin

A Microsoft Windows machine might be:

C:\Users\nancy\Documents\JFE\bin

c)The answer to this question is dependent on the type of operating system and version of Java.  On a Unix based system using Java 1.6 you might find rt.jar here: 

/usr/lib/jvm/java-6-sun-1.6.0.13/jre/lib/rt.jar

While on a Microsoft Windows platform you might find it here:

C:\Program Files\Java\jdk1.6.0_10\jre
ch01/r07

The program prints the following:

39 + 3
42

Java interprets the statement "39 + 3" as a string and thus prints out the literal characters 39 + 3. Java interprets the second statement 39 + 3 as an operation between two numbers, so it first calculates the value 39 + 3 = 42 then prints out the result 42.

ch01/r08
HelloWorld

Because there are no spaces after the System.out.print("Hello"); the next line prints World directly after Hello is printed.

ch01/r09

Java interprets the comma in the println method to mean that two strings are passed to println.  It’s likely the programmer meant to do this:

System.out.print("Hello, World!");
ch01/r10

Compile-time errors:

public class HelloPrinter
{
   public static void main(String[] args)
   {
      System.outprint("Hello, World");
/*             ^^ missing '.' */
   }
}
public class HelloPrinter
{
   public static void main(String[] args)
   {
      System.out.print("Hello, World);
/*                                 ^^ missing '"' */
   }
}
public class HelloPrinter
{
   public static void main(String[] args)
   {
      System.out.print("Hello, World")
/*                                   ^^ missing ";" */
   }
}

Run-time error:

public class HelloPrinter
{
   public static void main(String[] args)
   {
      System.out.print("Hello, Wrold");
   }
ch01/r11

Syntax errors are discovered by compiling your Java program; the Java compiler will report them directly.  Logic errors are discovered by testing your program by running it and verifying the correct output; if the output is incorrect, you have a logic error.

ch01/r12
Start with the customer knowing how often they visit the cafeteria and the average price they pay for a meal.

Ask the cafeteria for cost of the discount card, the number of meals to be eaten to achieve the free meal, 
and the period of time in which all meals must be consumed.

If cost of the card is greater than the average cost of a customer meal
   Deal is set to “no good”
Else
   If qty of meals to be eaten is greater than qty of customers meals in the time period then
      Deal is set to “no good”
   Else
      Deal is set to “good”
ch01/r13
Start with a year of value 0, a month of value 0, and a balance of $10,000
Repeat the following while the balance is greater than 0
   Multiply the balance by 1.005.
   Subtract 500 from the balance.
   Add one to month.
   If the month is 12
      Set month to 0.
      Add one to year.
Year has the answer.
ch01/r14
If the starting balance is large enough and the interest rate large enough such that the first month's calculation of interest exceeds the monthly expenses, then you will never deplete your account and the algorithm will never terminate.
 
Modified algorithm:
Ask the user for balance, interest rate, and monthly expenses.
If balance x interest is greater than monthly expenses
   Tell the user you're in good financial shape and quit.
Otherwise, start with a year of value 0, a month of value 0 and a balance of $10,000
Repeat the following while the balance is greater than 0
   Multiply the balance by (1 + (interest rate times .01 divided by 12)).
   Subtract monthly expenses from the balance.
   Add one to month
   If the month is 12
      Set month to 0.
      Add one to year.
Year has the answer.
ch01/r15
Calculate the overall surface area of the house without windows and doors.
 
surfaceArea = (2 x width x height) + (2 x length x height)
  - (number of windows x windowWidth x windowHeight)
  - (number of doors x doorWidth x doorHeight)
ch01/r16

The computer cannot accurately predict what the price of gas will be on a daily basis (or know what day you will go to the gas station) and how many actual miles you will drive each year.

ch01/r17

Every day at 5 P.M. please do the following:

1)Insert the USB memory stick into the computer.

2)Create a new directory on the USB memory stick entitled "BACKUP-DATE" where "DATE" is replaced with the current date.

3)Copy the files from the "My Documents" folder on the computer to the folder you just created on the USB stick.

4)Double check to make sure the new directory contains the files you copied. If the folder is empty, something is wrong. It's possible you backed up to the wrong directory. Try it again and be careful which directory you copy into.

5)Once you verified the copy is complete, remove the USB stick and store it someplace safe.

6)Thank you!

ch01/r18
Get the orange juice from the refrigerator
Get the eggs from the refrigerator
Get the bacon from the refrigerator
Make the pancake batter
For each person eating breakfast:
    Crack an egg on the griddle
    Pour two pancakes on the griddle
    Place two slices of bacon on the griddle
    Pour a glass of orange juice
    Dish up a plate of cooked food
Call the family to breakfast
ch01/r19
close enough = 0.001
a = value from user to be square rooted
first guess = a / 2
second guess = (first guess + (a / first guess)) / 2
repeat 
    first guess = second guess
    second guess = (first guess + (a / first guess)) / 2
until (first guess - second guess) <= close enough

second guess holds the square root of a

ch02

ch02/r01

An object is an instance (an entity) that defined by a class. A class provides a definition which includes characteristics (data) and behavior (methods).

ch02/r02

Examples of String objects:
"Hello World"
"Schrödinger is the name of my cat."
"I LOVE programming"

Example of PrintStream object:
System.out

Sample Methods in the String class that are not in PrintStream class:
length()
toUpperCase()

Sample Method in the PrintStream class that is not in String class:
println()

ch02/r03

The public interface consists of all the methods we can apply to any of its objects.  Essentially, it is the set of methods to interact with the class. The implementation is how the methods accomplish their tasks. The public interface is accessible to all; the implementation should be private.

ch02/r04
double price = 5.50;
String description = “Dress Socks”;
ch02/r05

The value of mystery is equal to 0 after the statements are executed. In the first statement (line 1), mystery is initialized to a value of 1. In the assignment statement on line 2, mystery is set to -1. Finally, mystery is set to 0 in line 3.

ch02/r06

The variable mystery is being declared twice, first in line 1 and then again in line 2. A variable can only be initialized once. (If you remove the reserved word int on line 3, the statements will work just fine, and will set mystery to -3.)

ch02/r07

In the Java programming language, the = operator denotes an action, to replace the value of a variable. This usage differs from the traditional use of the = symbol as a statement about equality.

ch02/r08
title = ”Big Java”;
char letter = title.chatAt(0); // letter would be ’B’
int titleLength = title.length(); // titleLength would be 8
ch02/r09
String message = "Hello";
message = message.toUpperCase();
ch02/r10
String message = "Hello";
message = message.replace("H", "h");
ch02/r11
String message = "Hello, World!";
message = message.replace(",", "");
message = message.replace("!", "");
ch02/r12

An object contains state information. An object variable contains an object reference, that is, the location of an object.

ch02/r13
new Rectangle(5, 10, 20, 30); // Object 
Rectangle box; // Object variable
ch02/r14
new Rectangle(75, 75, 50, 50)
"Hello, Dave!"
ch02/r15
Rectangle square = new Rectangle(75, 75, 50, 50);
String greeting = "Hello, Dave!";
ch02/r16
Rectangle square = new Rectangle(10, 20, 40, 40);
square = new Rectangle(10, 20, 40, 40);
ch02/r17
Rectangle square1 = new Rectangle(20, 20, 40, 40);
Rectangle square2 = square1;  // the same object
ch02/r18

a. newRectangle is missing

b. Rectangle(5, 10, 15, 20) does not refer to an object. The corrected version should be:

double width = (new Rectangle(5, 10, 15, 20)).getWidth();

c. r has not been initialized; it does not refer to any object.

d. The method translate takes two integer arguments, not a string argument.

ch02/r19

Possible answers are:

Accessor: getWidth(), getHeight()

Mutator: translate(int, int), add(int, int)

ch02/r20

Class

Return type

Method name

Types of arguments

String

String

concat

String

String

String

trim

none

Rectangle

String

toString

none

Rectangle

Rectangle

union

Rectangle

Random

float

nextFloat

none

ch02/r21

An object contains state information. An object reference is the location of that object in memory.

ch02/r22

Console applications provide text-only interfaces and cannot display any drawings/figures (except ASCII art). Graphical applications are more user friendly and can display drawings inside frames (windows).

ch02/r23

The Swing toolkit calls the paintComponent method whenever the component needs to be repainted. For example, it is called when the window is shown for the first time, when it is resized, or when it is shown again after it was hidden.

ch02/r24

The designers of Java did not want to inconvenience those programmers who had produced programs that used simple graphics from the Graphics class after they developed the newer, more powerful Graphics2D class, so they did not change the parameter of the paintComponent method to Graphics2D.

ch02/r25

The purpose of a graphics context is to store the programmer choices for colors, fonts, and so on, and to draw and fill shapes.

ch02/r26

The paintCompoment method of the component class produces a drawing, while the main method of the viewer class constructs a frame and a component, adds the component to the frame, and makes the frame visible.

ch02/r27

You specify a text color simply by calling the setColor method of the graphics context before calling the drawString method.

ch03

ch03/r01

The public interface of the Counter in Section 3.1 consists of the click, getValue, and reset methods.  The public interface specifies the functionality supported by the class but does not disclose any details of how the functionality is implemented.  In contrast, the implementation of a class is the code that accomplishes the tasks to support the class’s functionality.

ch03/r02

Encapsulation is the process of hiding implementation details while publishing an interface for programmers to use. If you hide the implementation details, you can diagnose errors and make changes and improvements to the implementation of a class without disrupting the work of programmers who use the class.

ch03/r03

The private reserved word prevents a programmer using the class from manipulating instance variables except through the methods of that class. A programmer must use the public interface—the public methods that access or modify the instance variables—to change them.  As such, the instance variables are hidden from methods outside of the class.

ch03/r04
private String grade;

or a numeric value that corresponds to the letter grade to simplify gpa calculations

private double grade;
ch03/r05

Represent the time as one entire string value, example “8:35 a.m.”

private String value;

or as individual components

private int hour;
private int minute;
private String meridian;
ch03/r06

The programmers using the Time class do not have to do anything.  The code that uses the Time class is written based on the public interface and, as such, it need not change unless the public interface changes. That is the purpose of encapsulation and using a public interface.

ch03/r07

No, there should not be a setValue method.  The Counter class, as the original example indicates, models a device that can be used to count people.  The tally increases by one for each person counted.  The required functionality does not dictate the need to begin a tally at a value other than zero.

If there is a need to begin a count at a value other than zero, then a constructor should be added to support such functionality.  A mutator such as setValue should only be added if there is a need to support functionality to reset an existing counter to a value other than zero.

ch03/r08

(a) If BankAccount(double initialBalance) did not exist, we could use the default constructor to create a BankAccount and then use the deposit method to increase the balance.

BankAccount account = new BankAccount();
account.deposit(1500);

is equivalent to

BankAccount account = new BankAccount(1500);
 

(b) (The previously provided answer does not address the question asked.)

If the BankAccount() constructor is removed from the BankAccount class, then creating an object of the BankAccount class would require using the BankAccount(double initialBalance) constructor.  This constructor allows the specification of an initialBalance which can be 0.

BankAccount account = new BankAccount(0);

is equivalent to (with the no-argument constructor available)

BankAccount account = new BankAccount();
ch03/r09

A reset method effectively empties the account without any accountability. It would be best to create a new object if you want to delete an account and start with a new one. Otherwise, use the withdraw method to reduce the balance down to zero, which is how a real bank account should work.

ch03/r10

The account will have a negative balance. There are no checks to detect or stop this from happening.

ch03/r11

The this reference is used to refer to the implicit parameter of a method. It can be used to clarify the code, to explicitly access instance variables and methods in the object referenced by the implicit parameter, and to call another constructor of the same class.

ch03/r12

Mutator Methods
recordPurchase
receivePayment

Accessor Method
giveChange

ch03/r13

The method transfers an amount from the account passed as the implicit parameter to the account that is given as an explicit parameter.

Here is a sample call:

BankAccount harrysChecking = new BankAccount();
BankAccount momsSavings = new BankAccount(10000);
momsSavings.mystery(harrysChecking, 1000);
ch03/r14
public class TimeDepositAccount
{
   private double balance;
   private double interestRate;
   // Constructor
   public TimeDepositAccount(
         double initialBalance, double interestRate)
   {
     this.balance = initialBalance;
     this.interestRate = interestRate;
   }
   // Methods
   public void withdrawAll()
   {
      balance = 0.0; 
   }
   public double getBalance()
   {
      return balance;
   }
 
   public void addInterest()
   {
       balance = balance + balance * interestRate;
   }
}
ch03/r15

Instance variables are initialized when the object is created. In this case, area would be initialized to zero and wouldn't get calculated with the correct value until getArea is called. If another method were added to this class that used area, it would incorrectly use the value zero if getArea had not been called first to calculate the correct value.  As is, area is used in only a single method, getArea, and does not hold a value that must exist across method calls.  This suggests that area is a candidate for being turned into a variable local to getArea

public class Square
{
   private int sideLength;
 
   public Square(int length) 
   { 
      sideLength = length; 
   }
 
   public int getArea () 
   {
      int area; // local variable
 
      area = sideLength * sideLength;
      return area;
   }
}
ch03/r16

If the method grow is called, the value of the instance variable area will no longer be correct. You should make area a local variable in the getArea method and remove the calculation from the constructor.

public class Square
{
   private int sideLength;
 
   public Square(int length) 
   { 
      sideLength = length; 
   }
 
   public int getArea () 
   {
      int area; // local variable
 
      area = sideLength * sideLength;
      return area;
   }
 
   public void grow () 
   {
      sideLength = 2 * sideLength;
   }
}
ch03/r17
/**
   A class to test the Counter class.
*/
public class CounterTester
{
   /**
      Tests the methods of the Counter class.
      @param args not used
   */
   public static void main(String[] args)
   {
      Counter tally = new Counter();
      int result = tally.getValue();
      System.out.println(result);
      System.out.println("Expected 0");
 
      tally.count();
      tally.count();
      tally.count();
      result = tally.getValue();
      System.out.println(result);
      System.out.println("Expected 3");
 
      tally.reset();
      result = tally.getValue();
      System.out.println(result);
      System.out.println("Expected 0");
 
   }
}
ch03/r18
/**
   A class to test the Car class.
*/
public class CarTester
{
   /**
      Tests the methods of the Car class.
      @param args not used
   */
   public static void main(String[] args)
   {
      Car myHybrid = new Car(50);   // 50 miles per gallon
      myHybrid.addGas(20);   // Fill tank with 20 gallons
      myHybrid.drive(100);   // Drive 100 miles, use 2 gallons
      myHybrid.addGas(10);   // Add 10 gallons to tank
      myHybrid.drive(200);   // Drive 200 miles, use 4 gallons
      double gasLeft = myHybrid.getGasInTank();// Gas remaining in tank
      System.out.println(gasLeft);
      System.out.println("Expected 24");
   }
}
ch03/r19

Card Front:

BankAccount harrysChecking
BankAccount
BankAccount(initialBalance)
deposit(amount)
withdraw(amount)
getBalance

Card Back:

balance

0
2000
1500
ch03/r20

Card Front:

CashRegister register

CashRegister
recordPurchase(amount)
receivePayment(amount)
giveChange

Card Back:

purchase payment
0 0
29.50 0
38.75 0
38.75 50
0 0
ch03/r21

Card Front:

Menu mainMenu

addOption(option)
display

Card Back:

 optionCount  menuText
  0             “” 
  1             “1) Open new account\n”
  2             “1) Open new account\n2) Log into existing account\n”
  3             “1) Open new account\n2) Log into existing account\n3) Help\n”
  4             “1) Open new account\n2) Log into existing account\n3) Help\n4) Quit\n”
ch03/r22

First, we need to add a new instance variable to keep track of the number of transactions each month.  We will add the following instance variable to the class:

int numTransactions;

This variable should be incremented by one inside the withdraw and deposit methods.  The following line of code could be added to the end of these methods:

numTransactions++;

And, of course, we should initialize this variable to zero inside both constructors.

Finally, we need to add a new instance method that will calculate and deduct the fee ($1 for each transaction over 5) and reset the numTransactions variable to zero (to start the new month).

public void calculateTransFee()
{
   if (numTransactions > 5)
   {
      balance = balance – (numTransactions – 5);
   }
 
   numTransactions = 0;
}

And for the new object trace, let’s assume the following method calls are made over two months

BankAccount harrysAccount(1000);
harrysAccount.deposit(50);
harrysAccount.deposit(500);
harrysAccount.deposit(250);
harrysAccount.withdraw(100);
harrysAccount.deposit(70);
harrysAccount.deposit(80);
harrysAccount.calculateTransFee();
harrysAccount.deposit(150);
harrysAccount.deposit(500);
harrysAccount.deposit(250);
harrysAccount.withdraw(100);
harrysAccount.deposit(70);
harrysAccount.deposit(90);
harrysAccount.deposit(190);
harrysAccount.calculateTransFee );

Here are the updated object cards showing the results of these method calls:

You can see that thenumTransactionsvariable resets whenever the fee is calculated, and then a fee is subtracted from the balance (one dollar for every transaction over 5).

ch03/r23

You need four classes: House, Car, SceneComponent, and SceneViewer.

ch03/r24

The methods have the same implicit parameter as the paintComponent method. We could have written the calls as this.getHeight() and this.getWidth(). They are accessor methods so they don't need an explicit parameter; the instance variables of the object are all they need to do their work.

ch03/r25

Add width and height fields to the Car class, initialize them in the Car constructor, and use them in the draw method to determine the dimensions of the body, tires, and windshield

ch04

ch04/r01

This is somewhat ambiguous.  Are the variables local variables, or class variables?  I assume class variables:

public static final int DAYS_IN_WEEK = 7;
public int daysToSemesterEnd;
public static final double CENTIMETERS_IN_INCH = 2.54;
public double tallestHeight;
ch04/r02

The value of mystery is equal to 0 after the statements are executed. In the first statement (line 1), mystery is initialized to a value of 1. In the assignment statement on line 2, mystery is set to -1. Finally, mystery is set to 0 in line 3.

ch04/r03

The variable mystery is being declared twice, first in line 1 and then again in line 2. A variable can only be initialized once. (If you remove the reserved word int on line 3, the statements will work just fine, and will set mystery to -3.)

ch04/r04

a)  dm = m ((√(1 + v)/c) / (√(1 – v)/c)) – 1

b)  volume = π r2h

c)  volume = (4 π r3h)/ 3

d)  z = √(x2 + y2)

ch04/r05

a)  double s = s0 +(v0 * t) + (.5 * g * Math.pow(t,2));

b) double g = 4 * Math.PI * Math.PI* (Math.pow(a,3)/(p * p  * (m1 + m2)));

c) double fv = pv * Math.pow((1 + (intRate / 100)), yrs);

d) double c = Math.sqrt((a * a) + (b * b) - (2.0 * a * b * Math.cos(gamma)));

ch04/r06
a b Math.pow(a, b) Math.max(a, b) a/b a%b Math.floorMod(a, b)
2 3 8 3 0 2 2
3 2 9 3 1 1 1
2 -3 0.125 2 0 2 -1
3 -2 0.111 3 -1 1 -1
-3 2 9 2 -1 -1 1
-3 -2 0.111 -2 1 -1 -1
ch04/r07

A wrong result will occur when turning left and the absolute value of the turn is greater than the current direction. There will be an error when (-1 * turn) > direction

To solve this without using Math.floorMod(), you could implement the following:

if ((-1 * turn) > direction)
{
   direction = 360 + (turn + direction)
}  
  
ch04/r08

a) 6.25

b) 6

c) 12.5

d) -3

e) 1.4142135623730951

ch04/r09

a) 8

b) 1

c) 17

d) 17.5

e) 17

f) 18

ch04/r10

a) 10

b) e

c) llo

d) HelloWorld

e) WorldHello

ch04/r11

1)There is an extraneous semicolon after main().

2) The message in the first print statement is not surrounded by quotation marks like a string should be.

3) The variables x and y are not declared.

4) The variable in is not declared.

5) The method readDouble doesn’t exist (nextDouble does).

6) If readDouble were a method, it should be followed by ().

7) In the last line the method println is incorrectly spelled printline.

ch04/r12

1) The scanner should have been constructed without quotations as Scanner in = new Scanner(System.in);

2) The correct Scanner method for reading integers is nextInt();

3)  The second integer should have been read as y = in.nextInt();

(The problem requests 3 answers but there are 4 mistakes)

ch04/r13

The given output is printed in a raw format up to the range of a double data type. Users can use format specifiers (printfwith%) to format the output as they require.

ch04/r14

The type of 2 is int.  The type of 2.0 is a double; specifically the Java programming language recognizes it as the real number 2.0. The type of ’2’ is a char.  On the other hand, Java treats "2" and "2.0" as strings.

ch04/r15

a)This statement computes the value of y. Given the initial value of x as 2, the result for y is 4.

b)This statement concatenates the strings "2" together. The result for t is "22".

ch04/r16
Read input into a variable called word.
Print first character in word followed by a space.
Print character at length -1 in word followed by a space.
Print substring between 1st and last character (length -1) in word.
ch04/r17
Read first name into variable called first.
Read middle name into variable called middle.
Read last name into variable called last.

Print first character in first.
Print first character in middle.
Print first character in last.
ch04/r18
// Input is stored in variable called num
exponent = integer part of log10 of num
first digit = integer part of num / 10^exponent
last digit = num % 10
Print first digit.
Print last digit.
ch04/r19
change due = 100 x bill value – item price in pennies
quarters = change due / 25 (without remainder)
change due = change due % 25
dimes = change due / 10 (without remainder)
amount due = change due % 10
nickels = change due / 5 (without remainder)
// Change is now in quarters, dimes, and nickels
ch04/r20

As long as you used the theodolite to sight in the top exactly at the midpoint of a side, then no other information is needed. You may use your right triangle trigonometry to calculate the height on the side of the pyramid. From there you can calculate the surface area of the pyramid.

ch04/r21
public class ConeSurfaceArea
{
   public static void main(String[] args)
   {
      // set circumference and angle of elevation (in degrees)
      double circumference = 6.29; 
      double angle = 45;
      
      // find radius using C = 2(pi)r
      double radius = circumference / (2 * Math.PI);

      // find height using right triangle trig
      double height = radius * Math.tan(angle);
      
      // calculate surface area using SA = (pi)r * (r + sqrt(height^2 + radius^2)
      double surfaceArea = Math.PI * radius * (radius + Math.sqrt(Math.pow(height,2) + Math.pow(radius,2)));

      System.out.println(surfaceArea);
   }
}
ch04/r22

First, compute the total volume by hand using the formula in Self Check 25. Let’s assume the following values for the three sections:

.Conic Section 1 (top of bottle) has first radius (r11) 0.5 inches, second radius (r21) 0.75 inches, and height (h1) 1.5 inches.

Conic Section 2 (middle) has first radius (r12) 0.75 inches, second radius (r22) 1.5 inches, and height (h2) 0.5 inches. 

Conic Section 3 (bottom of bottle) has first radius (r13) 1.5 inches, second radius (r23) 0.75 inches, and height (h3) 6.0 inches. 

So, the total volume of the bottle, Vt, will equal the volume of conic section 1 (V1) plus the volume of conic section 2 (V2) plus the volume of the conic section 3 (V3):

Vt = V1 + V2 + V3

We calculate the three volumes to be (rounded to two decimal places):

V1 = 1.87 cubic inches
V2 = 2.06 cubic inches
V3 = 24.74 cubic inches

So, the total volume for the cocktail shaker in our example is:

Vt = V1 + V2 + V3 = 28.67 cubic inches

The algorithm we use is very similar to the calculation we did above:

volume 1 =  π x (r112 + r11 x r21 + r212) x h1 / 3
volume 2 =  π x (r122 + r12 x r22 + r222) x h2 / 3
volume 3 =  π x (r132 + r13 x r23 + r232) x h3 / 3
total volume = volume 1 + volume 2 + volume 3
ch04/r23

Because we are given the diameter of the circle, d, and not the height of the circular sector, h, we need to develop an algorithm to find h based on the value of d.

If you look at the figure on the right, you see that a right triangle can be made bounded by the chord, the diameter of the circle, and the radius of the circle drawn through h.

 Because we know the length of the radius (half the diameter), we can set up an equation to find the value of h:

h = 0.5d - x

where x is one side of the right triangle. We can solve for x by using trigonometry on the right triangle, and then use that value to solve for the value of h, which we need to compute the area of the circular sector (the oddly-shaped piece of pie). In the right triangle, the side labeled x is considered to be the “opposite” side. We know that the hypotenuse of the right triangle is half the diameter, or 0.5d, and the “adjacent” side of the right triangle is half the chord length, or 0.5c.

Therefore, we can use the following formulas for a right triangle to determine what we need for the problem:

sin θ = opposite/hypotenuse cos θ = adjacent/hypotenuse

Here is the general algorithm (see figure for definition of the variables):

Ask the user to enter the diameter of the circle, store the value in d.
Ask the user to enter the length of the chord, store the value in c.

Compute the angle θ with formula θ = cos-1(0.5c / 0.5d).

Compute the length of x with the formula x = sin θ * 0.5d.
Determine h using the formula h = 0.5d – x.
Calculate the area of the pie piece, A, using the formula.
A = 2.0 / 3 * c * h + pow(h, 3) / (2 * c).

We can use this algorithm to solve for the specific example of a pie with diameter 12 inches and a chord length of 10 inches:

We know that d = 12, c = 10.

Therefore, θ = cos-1(0.5c/0.5d) = cos-1(5/6) = 33.56 degrees

x = sin θ * 0.5d = sin 33.56 * 6 = 3.32 inches

h = 0.5d – x = 6 – 3.32 = 2.68 inches

A = 2/3 * c * h + h3/(2*c) = 2/3 * 10 * 2.68 + 2.683 / (2 * 10) = 18.83 square inches

ch04/r24

Starting position is 3 x 4 = 12 and length of substring is 3.

SunMonTueWedThuFriSat
0  3  6  9  12 15 18

We can see this will extract the substring Thu.

ch04/r25

Character at position i (2)

Gateway
0123456

Character at position j (4)

Gateway
0123456

first:

Gateway
0123456

middle:

Gateway
0123456

last:

Gateway
0123456

Generate a new string: first + character at j + middle + character at i + last

Gawetay
0123456
ch04/r26

You can read characters from a string with the charAt method. For the first character, pass a position of 0 to charAt. For the last character pass the position that is equal to the length of the string -1 to charAt.

Strings in Java are immutable, so they cannot be directly changed. Thus, to “remove” the first character from a string, we can take a substring of the original string that contains the entire thing minus the first character. If our string is called s, then this works: s.substring(1, s.length());. The last character can be obtained by extracting the substring that contains the entire string minus the last character, like this: s.substring(0, s.length()-1);.

ch04/r27

a) Exact

b) Exact

c) Overflow

d) Overflow

ch04/r28

This program:

public class R222
{
   public static void main(String[] args)
   {
      System.out.println(3 * 1000 * 1000 * 1000);
      System.out.println(3.0 * 1000 * 1000 * 1000);
   }
}

Prints out the following:

-1294967296
3.0E9

The reason the first number is negative is because we have exceeded the limited range of an int and the number overflowed to a negative value. The second number’s result is correct but displayed in scientific notation because it is a floating-point type from the 3.0 in the calculation.

ch05

ch05/r01

a) n = 1, k = 2, r = 1

b) n = 1, k = 2, r = 2

c) n = 1, k = 1, r = 2

d) n = 1, k = 6, r = 3

ch05/r02

In the first block, the conditions are evaluated sequentially, so s could be incremented twice. In the second block, the conditional statements are mutually exclusive, so, s cannot be incremented more than once.

ch05/r03

a)There are two errors in this code. First, there are no parentheses around the x > 0 part of the if statement. Secondly, there is an extraneous then which is not part of the Java syntax, instead we should wrap the body of the if statement in curly braces. A correct form would be:

if (x > 0) { System.out.print(x); }

b)In this statement there aren’t enough parentheses to balance the condition (there are only two). The following would be correct:

if (1 + x > Math.pow(x, Math.sqrt(2))) { y = y + x; }

c) In this case there is only a single = in the if statement. Likely the programmer wanted to check for equality rather than set x equal to the value of 1. A correct form would be:

if (x == 1) { y++; }

d) The problem in this case is that the programmer tried to validate the input after she read it thus defeating the whole purpose of input validation. Instead we should take the line which reads the integer into the body of the if statement, like this:

if (in.hasNextInt()) 
{
   x = in.nextInt();
   sum = sum + x;
}
else
{
   System.out.println("Bad input for x");
}

e) The if statements should be an if/else if/else sequence. More than one if statement will be executed for any grade higher than 60 and the letter grade will be wrongly assigned.

ch05/r04

a) -1

b) 1

c) 1.0

d) 2.0

ch05/r05
if (x > 0.0)
{
   y = x;
}
else
{
   y = 0.0;
}
ch05/r06
if (x < 0.0)
{
   y = -x;
}
else
{
   y = x;
}
ch05/r07

Floating-point numbers only have limited precision so it’s very likely that any mathematical operation (like addition, multiplication, etc.) will introduce small errors into the result.

To check to see if an integer equals 10:

if (n == 10)
{
   System.out.println("It's 10!");
}
else
{
   System.out.println("It's not 10!");
}

To check to see if a floating-point number approximately equals 10:

final double EPSILON = 1E-14;
double x = 10.0;
if (Math.abs(x - 10) < EPSILON)
{
   System.out.println("It's approximately 10.0!");
}
else
{
   System.out.println("It's not 10.0!");
}
ch05/r08

a) (x1==x2 && y1==y2)

b) (Math.sqrt(Math.pow(X1-X2, 2) + Math.pow(Y1-Y2, 2)) < 5)

ch05/r09

In the first case when comparing if (floor = 13) you should get the error “Type mismatch: cannot convert from int to boolean".

In the statement count == 0; you should get the error “Syntax error on token “==”, invalid assignment operator”.

ch05/r10
letter number color
g      5      “black”
ch05/r11

The following test cases cover all four branches.

a) “g5”

b) “h5”

c) “g4”

d) “h4”

ch05/r12

Trace of appointment from 10-12 and one from 11-13:

start1 start2 end1 end2 s  e
10     11     12   13   11 12

Since s < e the program would report “The appointments overlap.” Which is indeed the case.

Trace of appointment from 10-11 and one from 12-13

start1 start2 end1 end2 s  e
10     12     11   13   12 11

Since s > e the program would report “The appointments don’t overlap.” Which is correct.

ch05/r13

The flowchart for Exercise R3.11:

ch05/r14

The flowchart:

ch05/r15

The flowchart:

ch05/r16
Test Case Expected Outcome       Comment
====================================================
Start1=12  End1=14 No overlap    Completely separate
Start2=15  End2=16               appointments

Start1=12  End1=14 Overlap       Overlap by 1 hour
Start2=13  End2=15 

Start1=12  End1=14 Overlap       Appointment 2 starts before
Start2=11  End2=15               and ends after Appointment 1

Start1=12  End1=14 No overlap    Appointment 2 starts and ends
Start2=9   End2=10               before Appointment 1

Start1=12  End1=14 Overlap       Exact same appointment
Start2=12  End2=14

Start1=12 End1=14  No Overlap    Appointment 2 is right after
Start2=14 End2=17                Appointment 1, 
boundary condition
ch05/r17
Test Case        Expected Outcome   Comment
=====================================================================
Month=1, Day=10  Season=Winter      First season, not divisible by 3
Month=4, Day=10  Season=Spring      Second season, not divisible by 3
Month=7, Day=10  Season=Summer      Third season, not divisible by 3
Month=10, Day=10 Season=Fall        Fourth season, not divisible by 3
Month=3, Day=21  Season=Spring      Second season, divisible by 3, 
                                    boundary condition
Month=6, Day=21  Season=Summer      Third season, divisible by 3,
                                    boundary condition
Month=9, Day=21  Season=Fall        Fourth season, divisible by 3, 
                                    boundary condition
Month=12, Day=21  Season=Winter     First season, divisible by 3, 
                                    boundary condition
Month=3, Day=20  Season=Winter      First season, divisible by 3
Month=6, Day=20  Season=Spring      Second season, divisible by 3
Month=9, Day=20  Season=Summer      Third season, divisible by 3
Month=12, Day=20 Season=Fall        Fourth season, divisible by 3
ch05/r18
Prompt for and read month from user.
Prompt for and read day from user.
if month equals “January”
   if day equals 1
      print “New Year’s Day”
if month equals “July”
   if day equals 4
      print “Independence Day”
if month equals “November”
   if day equals 11
      print “Veterans Day”
if month equals “December”
   if day equals 25
      print “Christmas Day”
ch05/r19
if score >= 90
   assign A
else if score >= 80
   assign B
else if score >= 70
   assign C
else if score >= 60
   assign D
else
   assign F
ch05/r20

When comparing strings lexicographically each letter in the two strings are compared from first to last with the following rules:

• Letters of the same case come in dictionary order.

• All uppercase letters come before lowercase letters.

• Space comes before all printable characters.

• Numbers come before letters.

• Punctuation also has order listed in Appendix A.

When one letter is found that comes before another, the string it belongs to is ordered before the other.  Thus the sample strings given in the problem have the following order:

"Century 21" < "IBM" < "While-U-Wait" < "wiley.com"
ch05/r21

a)"Jerry"

b) "Tom"

c) "Churchill"

d) "car manufacturer"

e) "Harry"

f) "Car"

g) "Tom"

h) "Car"

i) "bar"

ch05/r22

In the case of an if/else if/else sequence, one clause is guaranteed to be executed, while in the case of nested if statements the internal clause is only true if all the if statements are true.

As an example one of the following lines of code will be printed:

if (n > 10)
{
   System.out.println("Greater than 10!");
}
else if (n >= 0)
{
   System.out.println("Between 0 and 10.");
}
else
{
   System.out.println("Less than 0.")
}

Whereas in this case the print will only execute if n is both greater than or equal to 0 and less than or equal to 10:

if (n >= 0)
{
   if (n <= 10)
   {
      System.out.println("Between 0 and 10.");
   }
}
ch05/r23

When comparing exact values the order of if/else if/else statements does not matter:

if (n == 1)
{
   System.out.println("1.");
}
else if (n == 2)
{
   System.out.println("2.");
}
else
{
   System.out.println("Something else.");
}

When comparing ranges of values it can:

if (n > 10)
{
   System.out.println("Greater than 10!");
}
else if (n >= 0)
{
   System.out.println("Between 0 and 10.");
}
else
{
   System.out.println("Less than 0.");
}
ch05/r24

The condition rewritten to use < operators instead of >= operators:

if (richter < 4.5)
{
   cout << "No destruction of buildings";   
}
else if (richter < 6.0)
{
   cout << "Damage to poorly constructed buildings";
}
else if (richter < 7.0)
{
   cout << "Many buildings considerably damaged, some collapse";
}
else if (richter < 8.0)
{
   cout << "Many buildings destroyed";
}
else
{
   cout << "Most structures fall";
}

Changing the operators to < instead of >= forces the order of the options to be reversed, because of the order in which the comparisons are evaluated.

ch05/r25
status    income    tax
==============================
“Single”  $1050.00  $105.00
“Single”  $20000.00 $2600.00
“Single”  $40000.00 $6400.00
“Married” $1050.00  $105.00
“Married” $20000.00 $2200.00
“Married” $70000.00 $10300.00
“Single”  $8000.00  $800.00
ch05/r26

This is an example of the dangling else problem:

if (gpa >= 1.5)
   if (gpa < 2)
      status = "probation";
else
   status = "failing";

When reading the code it may mistakenly appear that a student fails only when the GPA is less than 1.5, when in reality the code executes like this:

if (gpa >= 1.5)
   if (gpa < 2)
      status = "probation";
   else
      status = "failing";

Now we see all students whose GPAs is over 2.0 are also listed as failing.  To correct for this, we can add curly braces:

if (gpa >= 1.5)
{
   if (gpa < 2)
   {
      status = "probation";
   }
}
else
{
   status = "failing";
}
ch05/r27
p     q     r     (p && q) || !r   !(p && (q || !r))

false false false true               true 
false false true  false              true 
false true  false true               true 
false true  true  false              true 
true  false false true               false 
true  false true  false              true 
true  true  false true               false 
true  true  true  true               false 
ch05/r28

This is true if both A and B can be evaluated successfully. Otherwise it is not. For example, suppose A is

i < str.length()

and B is

str.substring(i, i + 1).equals("!")

Suppose further that i is 6 and str is "Hello!".

Then A && B is false because A is false.

But B && A causes an exception.

ch05/r29

Boolean operations in search engines are spelled out in English while in Java they have symbolic replacements. For example OR is equivalent to “||” in Java while AND NOT would be equivalent to a combination of “&&” and “!=”.

ch05/r30

a) false

b) true

c) true

d) true

e) false

f) false

g) false

h) true

ch05/r31

a) b

b)!b

c)!b

d) b

ch05/r32

a) b = (n == 0);

b) b = !(n == 0);

c) b = ((n > 1) && (n < 2));

d) b = (n < 1) || (n > 2);

ch05/r33

The program attempts to read the integer before it actually tests to see if there’s an integer to read. To correct this problem the int quarters = in.nextInt(); line should be moved inside the body of the if statement.

ch06

ch06/r01
a)
<blank line>
*
**
***
****

b)
=====
*====
**===
***==
****= c) *****
*****
*****
*****
*****
*****
***** <infinite loop>
ch06/r02
a)
0 10
1 9
2 8
3 7
4 6 b) <infinite loop>
ch06/r03
a) 55

b) 6

c) 120

d) 64
ch06/r04

a)

int i = 0;
while (i * i < n) 
{
   System.out.println(i * i);
   i++;
}

b)

int i = 10;
while (i < n)
{
   System.out.println(i);
   i = i + 10;
}

c)

int i = 1;
while (i < n)
{
   System.out.println(i);
   i = i * 2;
}
ch06/r05

a)

int sumOfEvenNumbers = 0;
for (int n = 2; n <= 100; n = n + 2) 
{
   sumOfEvenNumbers = sumOfEvenNumbers + n;
}
// sumOfEvenNumbers now has the sum of all even numbers from 2 to 100

b)

int sumOfSquares = 0;
int currentN = 1;
while (Math.pow(currentN, 2) <= 100) 
{
   sumOfSquares = sumOfSquares + Math.pow(currentN, 2);
   currentN++;
}
// sumOfSquares now has the sum of all squares from 1 to 100

c)

int sumOfOddNumbers = 0;
for (int n = a; n <= b; n++) 
{
   if (n % 2 == 1) 
   {
      sumOfOddNumbers = sumOfOddNumbers + n;
   }
}
//sumOfOddNumbers now has the value of all odd numbers between a and b

d)

int nLeft = n;
int sumOfOddDigits = 0;
while (nLeft > 0) 
{
   int digit = nLeft % 10;
   if (digit % 2 == 1) 
   {
      sumOfOddDigits = sumOfOddDigits + digit;
   }
   nLeft = nLeft / 10;
}
// sumOfOddNumbers now has sum of all odd digits in n
ch06/r06

a)

i j  n
0 10 0 
1  9 1 
2  8 2 
3  7 3 
4  6 4 
5  5 5

b)

i  j  n
0  0  0
1  1  1
2  2  4
3  3  9
4  4  16
5  5  25
6  6  36
7  7  49
8  8  64
9  9  81
10 10 100

c

i   j  n
10 0  0
 9 1  8 
 8 2  14
 7 3  18
 6 4  20
 5 5  20
 4 6  18
 3 7  14
 2 8  8
 1 9  0
 0 10 -10

d)

As the trace table shows, i will never equal j since they pass each other at the 4-6 to 6-4 mark.  The trace table stops right below this point to indicate it is an infinite loop.

i  j  n
0 10  0
2  8  1
4  6  2
6  4  3
8  2  4
...
ch06/r07

a) 1 2 3 4 5 6 7 8 9

b) 1 3 5 7 9

c) 10 9 8 7 6 5 4 3 2

d) 0 1 2 3 4 5 6 7 8 9

e) 1 2 4 8

f) 2 4 6 8

ch06/r08

An infinite loop occurs when the terminating condition in the loop never evaluates to false.  How you stop an infinite loop on your computer depends on your operating system and your IDE.  For example, in the Eclipse IDE there is a red “TERMINATE” button that will stop any Java program at any time.

ch06/r09
first value minimum output
true      
false 4 4  
  7    
  -2 -2  
  -5 -5  
  0 -5 -5
ch06/r10

An off-by-one error occurs when you incorrectly initialize or terminate a loop by one unit.  A common example occurs when looping through a Java String.  The programmer may forget that character positions start at 0 rather than 1 and start his loop one character beyond the actual start of the String.

ch06/r11

A sentinel value is a particular value that is used to indicate the end of a sequence.  By necessity the sentinel cannot be a valid member in the sequence.  For example, an employer may be interested in the average age of her employees.  She could write a program that reads a series of ages and terminates when it reads a negative number.  Since there are no employees with a negative age it makes an appropriate sentinel value.

ch06/r12

Java supports three types of loop statements: for, do, and while.  Use a for loop if you know in advance how many times the loop should be repeated.  Use a do loop if the loop must be executed at least once.  Otherwise, use a while loop.

ch06/r13

a) 10 times

b) 10 times

c) 10 times

d) 21 times

e) This is an infinite loop

f) 11 times

g) 7 times

ch06/r14
Print out calendar header with days of week: Su M T W Th F Sa
 
// The -2 indicates that the first week doesn’t start until Wednesday
current day = -2
last day of month = 31
 
// Let 0 represent Su and 6 represent Sa
weekday = 0
while (current day <= last day of month)
   if (current day > 0)
      Print current day followed by a space
   else
      Print three spaces
   Add one to current day
   Add one to weekday
 
   // Check to see if we’ve printed out a week, print a newline if we have
   if (weekday == 7)
      Print a newline to go to next week
      weekday = 0
ch06/r15
Print out table header
for (celsius = 0; celsius <= 100; celsius = celsius + 10)
   Print right aligned celsius
   Print a | character
   fahrenheit = (9/5) * celsius + 32
   Print right aligned Fahrenheit
   Print newline
ch06/r16
// Initialize current name to something other than -1
current name = ""
read name from input into current name
counter = 0
total score = 0
average score = 0
read next input into current score
while (current score != -1)
   counter = counter + 1
   add current score to total score
   read next input into current score
average score = total score / counter
print average score
print newline

Trace Table:

 
name current score counter total score average score
Harry Morgan 94 1 94 0
  71 2 165 0
  86 3 251 0
  95 4 346 0
  -1     0
        86.5
ch06/r17
// Initialize current name to something other than END
current name = ""
read name from input into current name
while (current name != "END")
   current score = 0
   total score = 0
   read next input into current score
   while (current score != -1)
      add current score to total score
      read next input into current score
   print current name and total score
   print newline

Trace Table

name current
score
total
score
Harry Morgan 94 94
  71 165
  86 251
  95 346
  -1  
Sally Lin 99 99
  98 197
  100 297
  95 392
  90 482
  -1  

 

ch06/r18
int s = 0;
int i = 1;
while (i <= 10)
{
   s = s + i;
   i++;
}
ch06/r19
int n = in.nextInt();
double x = 0;
double s;
s = 1.0 / (1 + n * n);
n++;
x = x + s;
while (s > 0.01)
{
   s = 1.0 / (1 + n * n);
   n++;
   x = x + s;
}
ch06/r20

a)

s n
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 2
 

b)

s n
1 1
2 2
4 3
7 4
11  
 

c)

s n
1 1
2 2
4 3
7 4
11 5
16 6
22 7
29 8
37 9
46 10
56 11
67 12
79 13
92 14
106 15
121 16
137 17
154 18
172 19
191 20
211 21
 
ch06/r21

a) 2 4 7 11 16

b) 4 9 16

c) 10 7

ch06/r22

a) 10

b) 6

c) 3

d) 0

ch06/r23

If a programmer needed to print a list of numbers starting from a to b it is easier to read if the for loop has a and b as symmetric bounds, like this:

for (int i = a; i <= b; i++)

If a programmer needed to loop through all the characters in a string, it is easier to read if the loop has asymmetric bounds based on the length of the string, like this:

for (int i = 0; i < myString.length(); i++)
ch06/r24

Storyboard for incompatible units.

What unit do you want to convert from? cm
What unit do you want to convert to? gal
Sorry, cannot convert from one unit to the other.
What unit do you want to convert from? cm
What unit do you want to convert to? in
Enter values, terminated by zero: 10
10 cm = 3.94 in
What unit do you want to convert from?
ch06/r25

Storyboard showing how valid unit types can be displayed.

What unit do you want to convert from? leagues
Sorry, invalid units.  Valid unit types are:
	in, ft, mi, mm, cm, m, km
	oz, lb, g, kg
	tsp, tbsp, pint, gal, ltr
What unit do you want to convert from? cm
What unit do you want to convert to? in
Enter values, terminated by zero: 10
10 cm = 3.94 in
What unit do you want to convert from?
ch06/r26

Storyboards from Section 6.6 with a new menu.

Converting a Sequence of Values
What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit
1
What unit do you want to convert from? cm
What unit do you want to convert to? in
Enter values, terminated by zero 30
30 cm = 11.81 in
100
100 cm = 39.37 in
0 

What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit 
 
Handling Unknown Units
What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit
1
What unit do you want to convert from? cm
What unit do you want to convert to? inches
Sorry, unknown unit. 
What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit
1
What unit do you want to convert from? cm
What unit do you want to convert to? inch
Sorry, unknown unit. 
What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit
1
What unit do you want to convert from? cm
What unit do you want to convert to? in
3030 cm = 11.81 in
100100 cm = 39.37 in
0
What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit 
 
Exiting the Program
What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit
1
What unit do you want to convert from? cm
What unit do you want to convert to? in
Enter values, terminated by zero
30
30 cm = 11.81 in
100
100 cm = 39.37 in
0 
What would you like to do?     
	Enter 1 to convert units   
	Enter 2 for program help   
	Enter 3 to quit
3
(Program exits)
ch06/r27

Flowchart for the units conversion program in Section 6.6.

ch06/r28

You cannot initialize the largest and smallest variables to zero because it is possible that all of the values entered may be either all larger than zero or all smaller than zero.  

For example, if we are looking for the maximum and set largest to zero, and the values entered are -10.2, -8.1, and -7.6, the value of maximum never changes from zero, because none of the values entered is greater than zero.  The maximum number of those entered should be -7.6, but the program would think it was 0.

ch06/r29

Nested loops are loops contained in other loops.  This sort of structure is common when having to process a table.  One loop would process the rows while the other would process the columns in each row.

ch06/r30
for (int i = 1; i <= width * height; i++) 
{
   System.out.print("*");
   if (i % width == 0)
   {
      System.out.println();
   }
}
ch06/r31

Java has a random number generator (Math.random()) which generates random numbers from 0 up to 1 (exclusive).  To generate a random hour, get a random number between 0 up to 1, multiply it by 12 and cast it to an int; this gives you a random number between 0 and 11.  Next, add 1 to that number to create a number between 1 and 12 which is appropriate for the hour.

The minutes are easier, simply generate a random number between 0 up to 1, multiply it by 60 and cast it to an int.

ch06/r32

This problem is easier to think about if you generate a random number to select which friend to visit.  First generate a random number between 1 and 15 (Harry has 15 total friends).  Next convert the friend numbers to state numbers.  If the number is between 1 and 10, generate a 1 indicating California; if the number is between 11 and 13, generate a 2 indicating Nevada; otherwise generate a 3 indicating Utah.

ch06/r33
  • Step into: steps inside method calls. You should step into a method to check whether it carries out its job correctly.
  • Step over: skips over method calls. You should step over a method if you know it works correctly.
ch06/r34

The procedure depends on the debugger. Most debuggers know about the String class and display its contents immediately when you ask to inspect or watch a string. However, you can also display the instance variables and inspect the value instance variable.

ch06/r35

This varies according to the debugger used. Typically, you inspect a variable of type Rectangle and carry out some action (such as clicking on a tree node) to open up the display of the instance variables. The x, y, width, and height instance variables should then be visible.

ch06/r36

This varies according to the debugger used. Typically, you inspect a variable of type BankAccount and carry out some action (such as clicking on a tree node) to open up the display of the instance variables. The balance variable should then be visible.

ch06/r37

The “divide-and-conquer” strategy involves stepping over the methods in main to pinpoint the location of the failure. When a failure occurs just after a particular method (say f), then restart main, set a breakpoint before f, step into f, and now apply the same strategy to f. Keep going until the error is found.

ch07

ch07/r01
 
a) int[] nums = new int[10];

b) nums[0] = 17;

c) nums[9] = 29;

d) for (int i = 1; i < 9; i++) {nums[i] = -1;}

e) for (int i = 0; i < nums.length; i++) {nums[i]++;}

f) for (int num : nums) {System.out.println(num);}

g) for (int i = 0; i < nums.length; i++) 
   { 
      if (i < nums.length - 1)
         System.out.print(nums[i] + ",");
      else
         System.out.println(nums[i]);
   }

  
ch07/r02

The index of an array specifies the array position in which the element can be read or set.

Legal index values start at 0 and go to the length of the array minus one.

A bounds error occurs when an array is referenced with an index that is outside the range of legal array index values.

ch07/r03

The following is a program that contains a bounds error.

public class R6_12
{
   public static void main(String[] args)
   {
      int[] array = new int[10];
      array[10] = 10;
   }
}

When run it outputs the following error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
 at R6_12.main(R6_12.java:6)
ch07/r04
Scanner in = new Scanner(System.in);
int myArray[10];
for (int i = 0; i < 10; i++)
{
   System.out.println("Enter a number: ");
   myArray[i] = in.nextInt();
}
 
for (int j = 9; j >= 0; j--)
{
   System.out.print(myArray[j] + " ");
}
ch07/r05

a) 

for (int i = 0; i < 10; i++)
{
   values[i] = i + 1;
}

b) 

for (int i = 0; i <= 10; i++)
{
   values[i] = i * 2;
}

c) 

for (int i = 0; i < 10; i++)
{
   values[i] = (i + 1) * (i + 1);
}

d) 

for (int i = 0; i < 10; i++)
{
   values[i] = 0;
}

e) 

int[] values =  {1, 4, 9, 16, 9, 7, 4, 9, 11};

f) 

for (int i = 0; i < 10; i++)
{
   values[i] = i % 2;
}

g) 

for (int i = 0; i < 10; i++)
{
   values[i] = i % 5;
}
ch07/r06

a) 25

b) 13

c) 12

d) This loop condition causes an out-of-bounds index error.  If the condition were i < 10, total would be 22.

e) 11

f) 25

g) 12

h) -1

ch07/r07

a) { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

b) { 1, 1, 2, 3, 4, 5, 4, 3, 2, 1 }

c) { 2, 3, 4, 5, 4, 3, 2, 1, 0, 0 }

d) { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

e) { 1, 3, 6, 10, 15, 19, 22, 24, 25, 25 }

f) { 1, 0, 3, 0, 5, 0, 3, 0, 1, 0 }

g) { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }

h) { 1, 1, 2, 3, 4, 4, 3, 2, 1, 0 }

ch07/r08

To generate an array with ten random numbers between 1 and 100:

for (int i = 0; i < 10; i++)
{
   values[i] = (int) (Math.random() * 100 + 1);
}

To generate an array with ten different random numbers between 1 and 100:

for (int i = 0; i < 10; i++)
{
   values[i] = (int) (Math.random() * 100 + 1);
 
   // Check to see if number has been generated before
   int count = 0;
   for (int j = 0; j < i; j++)
   {
      if (values[j] == values[i])
      {
         count++;
      }
   }
   if (count > 0)
   {
      i--; // if it has, back up and try again
   }
}
ch07/r09

Below, data is an array.

int min = data[0];
int max = data[0];
for (Integer val : data)
{
   if (val > max)
   {
      max = val;
   }
   if (val < min)
   {
      min = val;
   }
}
ch07/r10

a) The loop iterates over the values 1 to 10 which in turn are used as array indices.  Yet, the length of the array is 10, thus its indices range from 0 to 9.

b) The programmer forgot to initialize the array values. One would expect a statement like int[] values = new int[10]; or however many elements the programmer desired.

ch07/r11

a)

for (Object object : array)
{
   System.out.print(object.toString());
}

b)

int max = array[0];
for (Object object : array)
{
   if (object > max)
   {
      max = object;
   }
}

c)

int count = 0;
for (Object object : array) 
{
   if (object < 0) 
   {
      count++;
   }
}
ch07/r12

a)

for (int i = 0; i < values.length; i++)
{
   total = total + values[i];
}

b)

for (int i = 0; i < values.length; i++)
{
   if (values[i] == target)
   {
      return true;
   }
}

c)

for (int i = 0; i < values.length; i++)
{
   values[i] = 2 * values[i];
}
ch07/r13

a)

for (double x : values)
{
   total = total + x;
}

b)

int pos = 0;
for (double x : values)
{
   if (pos >= 1)
   {
      total = total + x;
   }
   pos++;
}

c)

int pos = 0;
for (double x : values)
{
   if (x == target)
   {
      return pos;
   }
   pos++;
}
ch07/r14

a) ArrayList can't take a Java primitive as a type, rather it needs a wrapper class, in this case Integer.

b) In this case the new ArrayList did not define its generic type. One would expect to see new ArrayList<Integer>(); as the initial value. In Java 7, however, the syntax shown is acceptable.

c) Parentheses () are required after new ArrayList<Integer>.

d) The initial size of the ArrayList already is 0 elements, thus the set method cannot be used to set them.

e) The ArrayList reference values is not initialized. The code = newArrayList<Integer>(); should be to the right of the declaration.

ch07/r15

The headers of the described methods.

a) public void sortDecreasing(int[] arr, int currentSize)

b) public void printWithString(int[] arr, int currentSize, string sep)

c) public int numItemsBelow(int[] arr, int currentSize, int value)

d) public void removeItemsLessThan(int[] arr, int currentSize, int value)

e) public void copyLessThan(int[] source, int firstSize, int[] target, int secondSize, int value)

ch07/r16
i	output
0	32
1	| 54
2	| 67.5
3	| 29
4	| 35
ch07/r17
element matches
110 {110}
90 {110}
100 {110}
120 {110, 120}
80 {110, 120}
ch07/r18
pos found
0 false
1 false
2 false
3 true

pos found
0 false
1 false
2 false
3 false
4 false
5 true
ch07/r19
current size i values
5   {110,90,100,120,80}
5 3 {110,90,100,120,80}
5 4 {110,90,100,80,80}
4 5 {110,90,100,80,80}
ch07/r20
Copy the first element into a variable, x.
Loop through the first length – 2 positions of the array using pos as a counter
   Copy the element at pos + 1 to the element at pos.
Copy x into the last position of the array.
ch07/r21
pos = 0
while pos < length of array
   if the element at pos is negative
      remove the element at pos.
   else
      increment pos.
ch07/r22
// x is the element to insert
pos = 0
inserted = false
while pos < length of array and not inserted
   if the element at pos is less than x
      insert x at pos.
      inserted = true.
   else
      increment pos.
if not inserted
   insert x at the end of the array.
ch07/r23
longestRun = 0
pos = 0
while pos < length of array - 1
   if element at pos is equal to element at pos + 1
      currentRun = 0
      currentElement = element at pos
      while pos < length of array - 1 and currentElement equals element at pos
         increment pos
         increment currentRun
      if currentRun > longestRun
         longestRun = currentRun
   else
      increment pos
print longestRun
ch07/r24

The values variable is a reference to another array.  Setting it equal to numbers causes the values reference to point to the numbers array, but it does not change the value of the object originally referred to by values.

ch07/r25

To find the smallest rectangle containing the points defined by the two arrays, compute the max and min of the x-values and the max and min of the y-values.  With those four values, you can define the locations of the x- and y-coordinates of the rectangle as follows:

   Upper left corner:  (min x, max y)

   Lower left corner:  (min x, min y)

   Upper right corner:  (max x, max y)

   Lower right corner:  (max x, min y)

ch07/r26

If the array is already sorted, we no longer need to find the position of the lowest quiz score.  If the array is sorted from lowest to highest, then the lowest quiz score is in the first position in the array.  Technically, we can even compute the sum without actually removing the lowest element, because it is always in the first location.  We can find the sum simply by starting the loop at position 1 instead of position 0:

public double sum(double[] values)
{
   double total = 0.0;
   // Start loop count at 1 to skip lowest score
   for (int n = 1; n < values.length; n++)
   {
      total = total + values[n];
   }
   return total;
}
ch07/r27

Pseudocode for an algorithm using “removes” and “inserts” instead of swaps.

i = 0
j = size / 2
while (i < size / 2)
    Remove item at position j.
    Insert removed item at position i.
    i++
    j++

I will try this algorithm out with four coins, a penny (P), a nickel (N), a dime (D), and a quarter (Q).  

Position   0  1  2  3
           P  N  D  Q
i = 0, j = 2, Remove coin at position j, insert at position 0
Increment i and j.
 
 
Position   0  1  2  3
           D  P  N  Q
i = 1, j = 3, Remove coin at position j, insert at position 1
Increment i and j.
 
 
Position   0  1  2  3
           D  Q  P  N  
i = 2, j = 4.

The reason this is always less efficient that using the swapping algorithm is that our new remove/insert algorithm above requires two method calls (one for the remove, and one for the insert) each time a coin is removed.  In the swapping algorithm, one method call (the swap) moves both coins at the same time.

Another way to look at it is that each time you remove a coin and each time you insert one, you have to move elements in the array to new locations.  (If you remove an element, all the elements above it must move down one.  If you insert, all the elements above it must move up one.)  When you do this as a single swap operation, only the two elements affected are moved.  The other elements do not have to move during a swap.

ch07/r28

When I laid the coins and paper clips out as described in this problem (a series of coins each with a number of paperclips beneath it), I envisioned a two-dimensional array with N rows and 2 columns.  The first column held the value of the coin (whether it was a penny, nickel, dime, or quarter) and the second column held a cumulative count corresponding to the number of that type of coin in column 1.  For instance, if I had a total of 10 coins consisting of 3 pennies (P), 2 nickels (N), 4 dimes (D), and 1 quarter (Q), my initial two-dimensional array might look like this (with all of the “counts” in the second column set to zero):

D0D0P0Q0P0N0D0N0D0P0

Then my algorithm for counting the coins would use a nested loop like this:

Loop (int i = 0; i < 10; i++)
        Loop (int j = 0; j < 10; j++)
             if coins[j][0] equals coins[i][0]
                  Increment the count at location coins[j][i].
             End inner loop.
   End outer loop.

In other words, you look at the coin in the first location (a dime), and then walk through the two-dimensional array in the inner for loop, incrementing the count of any dime you find in the array.  Then you look at the second coin (also a dime), and loop through the inner for loop again, incrementing the count for any dimes you find, and so on.

When you have walked through the entire array in this manner, your final two-dimensional array should look like this:

D4D4P3Q1P3N2D4N2D4P3

Then it is a simple matter of looping through the array, using the algorithms given in this chapter, to find the position of the element with the maximum count in the second column.

ch07/r29
for (int i = 0; i < ROWS; i++)
{
   for (int j = 0; j < COLUMNS; j++)
   {
      values[i][j] = 0;
   }
}
 
for (int i = 0; i < ROWS; i++)
{
   for (int j = 0; j < COLUMNS; j++)
   {
      values[i][j] = (i + j) % 2;
   }
}
 
for (int j = 0; j < COLUMNS; j++)
{
   values[0][j] = 0;
   values[ROWS - 1][j] = 0;
}
 
int sum = 0;
for (int i = 0; i < ROWS; i++)
{
   for (int j = 0; j < COLUMNS; j++)
   {
      sum = sum + values[i][j];
   }
}
 
for (int i = 0; i < ROWS; i++)
{
   for (int j = 0; j < COLUMNS; j++)
   {
      System.out.print(values[i][j] + " ");
   }
   System.out.println();
}
ch07/r30

Assume the two-dimensional array, data, has M rows and N columns:

Loop from row=0 to row=M
     Loop from column=0 to column=N
          If row is 0 or M
               Set data[row][column] equal to -1.
          Else if column is 0 or N
               Set data[row][column] equal to -1.
     End inner loop.
End loop.
ch07/r31

When traversing backward, the indices of the array list have to be decremented (instead of incremented) in the for loop. This process continues while the index i is greater than zero (0). When an object is removed from the array only the indices of the objects greater than the index removed are effected. The loop is only working with the indices less than the index of the object removed, so there is no issue.

ch07/r32

a) True.

b) False.

c) False.

d) False.

e) False.

f) True.

g) True.

ch07/r33

a) Verify that the lengths are equal, and then set a Boolean false if any mismatch occurs.

boolean equal = true;
if (data1.size() != data2.size())
{
   equal = false;
}
for (int i = 0; i < data1.size() && equal; i++)
{
   if (data1.get(i) != data2.get(i))
   {
      equal = false;
   }
}

b) Create a second array list that is empty, then loop over the first:

ArrayList<Integer> data2 = new ArrayList<Integer>();
for (int i = 0; i < data1.size(); i++)
{
   data2.add(data1.get(i));
}

c) Loop over all positions in the array list and set each one to 0:

for (int i = 0; i < data.size(); i++)
{
   data.set(i, 0);
}

d) Loop while the array list still has elements in it and remove the element at position 0:

while (data.size() > 0)
{
   data.remove(0);
}

More simply, one can call ArrayList’s clear method:

data.clear();
ch07/r34

a) True

b) True

c) False

d) True

e) False

f) False.

ch07/r35

Regression testing is testing done to ensure changes to code haven't broken any previously existing functionality. A test suite is a set of tests for the code that check if existing functionality works.

ch07/r36

Debugging cycling is a phenomenon where an issue is resolved that is later seen again after another issue's fix breaks the original fix for the resurfaced issue.

ch08

ch08/r01

Student answers will vary. The four main classes that would be expected would be:

  • Driver
  • Passenger
  • Map
  • Billing
ch08/r02

Student answers will vary. The main expected classes for this system would be:

  • Sponsor
  • Internship
  • Application
ch08/r03

VendingMachine would be an appropriate name for the class because it a) simulates a vending machine, and b) has functionality that matches vending machine functionality exactly, without more or less functions.

PriceChecker would not be an appropriate name for the class because while it does check the price, it also performs a transaction.

ChangeGiver would not be an appropriate name for the class because while it does give change when too much money is given, it will return the money paid if there is not enough.

ch08/r04

a) Invoice would be a good class to use if the goal was to keep track of the invoice as a digital record. The application only takes the information in to print the invoice, so this could be misleading.

b) InvoicePrinter is a good class to use for this application because it describes exactly the functionality of the application.

c) PrintInvoice works as a description of the application, but might not be the best choice because it sounds more like a function or an action than an entire class.

d) InvoiceProgram would be a good class to use if there were more than one action the application could perform. Using the word "program" implies that there are multiple possible functions of the application, whereas one could more easily use the single action provided by the application in its name.

ch08/r05

Actor Class - PaycheckComputer

Non-Actor Class - Payroll

The difference between the two classes if the implied functionality. The actor class defines its functional capacity of the class within its name, whereas the non-actor class only provides the general description of the functionality.

ch08/r06

The System class is not cohesive because it includes many features that are unrelated, such as console I/O, garbage collection, and the time in milliseconds.

ch08/r07

ch08/r08

ch08/r09

The Integer class depends on the String class.

ch08/r10

The class Rectangle depends on the Rectangle2D, Point, Dimension, and String classes.

ch08/r11

boolean hasNext() - Accessor

boolean hasNextDouble() - Accessor

boolean hasNextInt() - Accessor

boolean hasNextLine() - Accessor

String next() - Mutator

double nextDouble() - Mutator

int nextInt() - Mutator

String nextLine() - Mutator

ch08/r12
Accessor methods:
contains
createIntersection 
createUnion
equals
getBounds
getBounds2D
getHeight
getLocation
getSize
getWidth
getX
getY
intersection
intersects
isEmpty
outcode
toString
union

Mutator methods:
add
grow
setBounds
setLocation
setRect
setSize
translate
ch08/r13

The Resistor class in problem P8.8 is immutable because all of its functions are accessors.

ch08/r14

Of the three class, Rectangle, String, and Random, only class String is immutable.

ch08/r15

Of the three classes PrintStream, Date, and Integer, the Integer class is immutable.

ch08/r16

The side effect of the read() method is that it modifies the Scanner parameter that is passed in. A redesign would be to use the Scanner object within a main() method that passes in strings one at a time to the DataSet object.

ch08/r17

public void print() The side effect is modifying System.out to print on the console.

public void print(PrintStream stream) The side effect is modifying the stream parameter.

public String toString() There is no side effect.

ch08/r18

If no function (including main) has a side effect, then you could not observe the program doing anything. Such a program would be useless. (Note that producing output on the screen is a side effect.)

ch08/r19

When you call falseSwap, then a is initialized with 3 and b is initialized with 4. At the end of the falseSwap method, a is 4 and b is 3. Then the method exits and its local variables (including the parameter variables) are forgotten. The contents of x and y are not affected.

ch08/r20
public static void swap(Point2D.Double p)
{
   p.setLocation(p.getY(), p.getX());
}

public static void main(String[] args)
{
   double x = 3;
   double y = 4;
   Point2D.Double p = new Point2D.Double(x, y);
   swap(p);
   x = p.getX();
   y = p.getY();
   System.out.println(x + " " + y);
}

ch08/r21

TODO

ch08/r22

TODO

ch08/r23

We get the error message "non-static method print(int) cannot be referenced from a static context" because the print method is not declared as static. If you change the header of the method to public static void print(int x), then the program will work. The reason the method needs to be declared as static is because we are calling it without an object reference (implicit parameter), but only static methods can be called like that.

ch08/r24
decode
getInteger
highestOneBit
lowestOneBit
numberOfLeadingZeros
numberOfTrailingZeros
parseInt
reverse
reverseBytes
rotateLeft
rotateRight
signum
toBinaryString
toHexString
toOctalString
toString // all of the toString variations, except toString()
valueOf

They are static methods because these methods do not need an implicit parameter.

ch08/r25

All of the valueOf methods in the String class are static methods. Like the methods in the Integer class, these methods are static because these methods do not operate on an object and have only explicit parameters. They create a new String instead of modifying an existing String (implicit parameter, which these methods do not need). The format methods are also static, for the same reason.

ch08/r26

Student answers will vary. The primary objective is to break down the large task into sub-tasks. For example:

  1. Read as many words as will fit on a single line.
  2. Determine total spaces in line including trailing spaces.
  3. Evenly distribute spaces throughout sentence elimination trailing spaces in line.
  4. Print line.
  5. Repeat process again for each remaining lines of text.
ch08/r27

It is not a good design because using public static variables is not a good idea; they can accidentally get overwritten in large programs. A better way to do this is to have static methods System.getIn() and System.getOut() that return these streams.

ch08/r28

To write a Java program without import statements, the user needs to specify the path names of the classes that are used in the program.

/**
   A component that draws two rectangles.
*/
public class RectangleComponent extends javax.swing.JComponent 
{  
   public void paintComponent(java.awt.Graphics g)
   {  
      // Recover Graphics2D
      java.awt.Graphics2D g2 = (java.awt.Graphics2D) g;

      // Construct a rectangle and draw it
      java.awt.Rectangle box = new java.awt.Rectangle(5, 10, 20, 30);
      g2.draw(box);

      // Move rectangle 15 units to the right and 25 units down
      box.translate(15, 25);

      // Draw moved rectangle
      g2.draw(box);
   }
}

ch08/r29

The default package is the package that contains the classes with no package specifier. All classes that we have programmed up to this point were in the default package.

ch08/r30

The exception is reported, and the remaining methods continue to be executed. This is an advantage over a simple tester class whose main method would terminate when an exception occurs, skipping all remaining tests.

ch09

ch09/r01

a) HourlyEmployee, SalariedEmployee

b) SalariedEmployee

c) super class: Employee, sub class: Manager

d) HourlyEmployee, SalariedEmployee

e) none

f) name, hourlyWage

ch09/r02

a) Superclass: Employee Subclass: Manager

b) Superclass: Student Subclass: GraduateStudent

c) Superclass: Person Subclass: Student

d) Superclass: Employee Subclass: Professor

e) Superclass: BankAccount Subclass: CheckingAccount

f) Superclass: Vehicle Subclass: Car

g) Superclass: Vehicle Subclass: Minivan

h) Superclass: Car Subclass: Minivan

i) Superclass: Vehicle Subclass: Truck

ch09/r03

It's not useful because in terms of inventory, toasters, car vacuums, and travel irons all behave the same. There are a certain number of them, and they cost a certain amount.

ch09/r04

ChoiceQuestion inherits the following methods from its superclass:

setText
setAnswer
checkAnswer

It overrides the following method:

display

And it adds the following methods:

addChoice
ch09/r05

SavingsAccount inherits the following methods from its superclass:

deposit
getBalance

It overrides the following methods:

withdraw
monthEnd

It adds the following method:

setInterestRate
ch09/r06

CheckingAccount has a single instance variable:

private int withdrawals;

ch09/r07

a)legal

b) not legal

c) not legal

d) legal

ch09/r08

ch09/r09

Answers may vary depending on one's definition of a pickup truck (is it a car or truck?) and motorcycle (is it a bicycle with an engine?).

ch09/r10

Answers may vary depending on one's definition of a seminar speaker.

ch09/r11

The (BankAccount) x cast is casting the variable type of the object without changing its value whereas the (int) x cast can actually change the underlying primitive value.

ch09/r12

a)true

b) true

c) false

d) true

e) false

f) false

ch10

ch10/r01
  a) a-b = -294967296
  b) b-a = 294967296
  c) Integer.compare(a, b) = 1
  d) Integer.compare(b, a) = -1
  
ch10/r02
  a) a-b = 0.3
  b) b-a = -0.3
  c) Double.compare(a, b) = 1
  d) Double.compare(b, a) = -1
  
ch10/r03

The following require a cast:

c = i; // c = (C) i;
i = j; // i = (I) j;
ch10/r04

None of them will throw an exception.

ch10/r05

The following are legal:

a. e = sub;

c. sub = (Sandwich) e;

The following statement will compile but throw an exception at run time.

f. e = (Edible) cerealBox;

ch10/r06

ch10/r07

a. Rectangle a = r;

b. Shape b = r;

f. Serializable f = r;

g. Object g = r;

ch10/r08

The call Rectangle r = s.getBounds(); is an example of polymorphism because the Shape interface declares the method, and each class that implements the interface (Rectangle2D.Double, Ellipse2D.Double, Line2D.Double, etc.) provides its own implementation of the method. The correct implementation is picked at run time.

ch10/r09

The Employee class must
1) implement Measurable and
2) include a method public double getMeasure()

To use the second solution in 10.4, you

1) create an interface Measurer that defines a callback method (measure) and

2) you create a small helper class with the method that tells the average method how to measure the objects public double measure(Object anObject)

The callback method decouples your class with other classes. It is a more generic and flexible solution . It is no more difficult to implement than a pure interface solution.

ch10/r10

You will get a compiler error. The String class does not implement the Measurable interface.

ch10/r11

A callback is objtained by implementing the Measurer interface. Provide a class StringMeasurer that implements Measurer.

public class StringMeasurer implements Measurer
{
   public double measure(Object anObject)
   {
      string aString = (String) anObject;
      double length = aString.length();
      return length;
   }
}
 

Now you need to construct an object of the StringMeasurer class and pass it to the average method.

Measurer stringMeas = new StringMeasurer();
String[] strings = { . . . };
double averageLength = Data.average(strings, stringMeas);
ch10/r12

You will get an error. When the callback method is used, a String object will be passed to a method that id designed for calculating the area of a Rectangle object. String objects do not have getWidth() and getHeight() methods.

ch10/r13

The f method can access the variables b, t, and x.

ch10/r14

The compiler gives an error saying that the local variable is accessed from within inner class and needs to be declared final:

local variable a is accessed from within inner class; needs to be declared final

If we change the variable so that it is declared as final, then the inner class can access it, provided it does not try to assign a new value.

ch10/r15

We would need to put each class (InvestmentViewer1 and AddInterestListener) in its own file. With this change, the class AddInterestListener is no longer able to access the account variable. Thus, we need to add a "private BankAccount account" variable to the class AddInterestListener, and have it receive the bank account in the constructor.

ch10/r16

An event is an external activity to which a program may want to react. For example, "user clicked on button X" is an event.

An event source is the user-interface component that generates a particular event. Event sources report on events. When an event occurs, the event source notifies all event listeners.

An event listener belongs to a class that is provided by the application programmer. Its methods describe the actions to be taken when an event occurs.

ch10/r17

With a console application, the programmer is in control and it can ask the user for input, in the order that is most convenient for the program.

With a graphical user interface application, the programmer lays out the various elements for user input. Then the user is in control. The user can click and type into the components in any order, and the programmer must be able to cope with that variety.

ch10/r18

An ActionEvent is generated when the user-interface library has detected a particular user intent, such as clicking on a button or hitting ENTER in a text field.

A MouseEvent is generated whenever the user moves or clicks the mouse.

ch10/r19

An ActionListener is only interested in one notification: when the action happens.

A MouseListener has multiple methods because there are several potentially interesting mouse events, such as pressing, releasing, or clicking the mouse button.

ch10/r20

Yes; a class can be the event source for multiple event types. For example, a JButton is the event source for both mouse events and action events.

You can listen to the mouse events of a button, simply by installing a mouse listener:

button.addMouseListener(mouseListener);

You might want to do that for example to make the button glow in a different color whenever the mouse hovers over it.

ch10/r21

Every event carries the source object. You can retrieve it with the getSource method.

A mouse event has the following additional information:

a) the x- and y- component of the mouse position and b) the click count

An action event has the following additional information:

a) the command string associated with the action and b) the modifier keys held down during the action event

Hint: This information can be found in the API documentation.

ch10/r22

Event listeners often need to access instance variables from another class. An inner class can access the instance variables of the outer class object that created it. Thus, it is convenient to use inner classes when implementing event listeners.

If Java had no inner classes, we could pass the values of instance variables needed to be accessed to the event listener constructor, so that local references/copies can be stored in the event listener object.

ch10/r23

The paintComponent method is called by the GUI mechanism whenever it feels that a component needs to be repainted. That might happen, for example, because the user just closed another window that obscured the component.

A programmer calls the repaint method when the programmer feels that the component needs to be repainted (for example, if the state of the object has changed). That call is a request to the GUI mechanism to call paintComponent at an appropriate moment.

ch10/r24

A frame is a window to which you can add a component to be displayed on the screen. A frame can be displayed on its own, even if it is empty. However, we cannot simply add multiple components directly to a frame-they would be placed on top of each other. A panel is a container to group multiple user-interface components together. A panel needs to be added to a frame to be displayed.

ch11

ch11/r01

If you open a file for reading that doesn't exist, Java will throw a FileNotFoundException.

If you open a file for writing that doesn't exist, Java will create a new empty file.

ch11/r02

Java will throw a FileNotFoundException whose error message says "(Access is denied)".

ch11/r03

When the program ends any unwritten data in the buffer will not be written to the file. Closing the PrintWriter flushes the buffer to the file before closing the file.

ch11/r04

You need to use an escape character (an extra backslash) before the backslash, like this:

String filename = "c:\\temp\\output.dat";
ch11/r05
args[0]: -Dname=piglet
args[1]: -I\eeyore
args[2]: -v
args[3]: heff.txt
args[4]: a.txt
args[5]: lump.txt
ch11/r06

(The original answer is misleading. First, throwing an exception does not create a new exception. The new expression is still the means to create the exception. Second, the method does not halt unless the exception is not caught within the method.)

An exception is thrown to report an error. When an exception is thrown, control continues at the nearest enclosing exception handler that is capable of handling the specified exception type. If no such handler exists, then the program terminates.

Catching an exception is the means by which to handle the reported error. An exception is caught and handled (processed), ideally, at a point in the program where the error can be addressed.

ch11/r07

A checked exception indicates something beyond your control has gone wrong. Methods that throw these types of exceptions must specify that they do so by using the throws reserved word. An example is FileNotFoundException.

An unchecked exception indicates an error in the code and does not need to be explicitly handled with a try-catch block. An example is IndexOutOfBoundsException.

ch11/r08

Because IndexOutOfBoundsException is an unchecked exception, and by definition unchecked exceptions do not need to be declared by the throws reserved word. (These exceptions are caused by errors in code that a programmer should have detected during testing.)

ch11/r09

The next line of code processed after a throw statement is the first line in the first catch block hierarchy that processes that type of exception.

ch11/r10

If an exception does not have a matching catch clause, the current method terminates and throws the exception to the next higher level. If there is no matching catch clause at any higher level, then the program terminates with an error.

ch11/r11

Your program can do anything with the exception object that it chooses to. It can print it to System.out, ignore it, or anything else that is legal to program into the catch block.

ch11/r12

Not always. It's possible that the type of the exception handled in the catch block is an "ancestor" of the exception type that is actually passed into it. This is legal in Java since a variable of superclass type can always reference a subclass object.

ch11/r13

When using the try-with-resources statement, the close method is called on the variable when the try-block is completed. If an exception occurs, the close method is called before it is passed to the handler.

try (PrintWriter out = new PrintWriter(filename))
{
    writeData(out);
}   //out.close() is always called
ch11/r14

It depends on the exception type being caught by the catch clause. The close method of the Closeable interface throws exceptions of type IOException while the close method of the AutoCloseable interface throws exceptions of type Exception.

ch11/r15

next can throw a NoSuchElementException if no more tokens are available or an IllegalStateException if the scanner is closed.

nextInt can throw everything that next can plus an InputMismatchException if the next token does not match the Integer regular expression, or is out of range.

These are all unchecked exceptions.

ch11/r16

Because the first line of the file is a 1, readData constructs an array to hold one value and, after the next line is read from the file, the program throws an IOException because it expected to reach the end of the file. The error report could be improved by printing the number of elements that the program expected to read. Then it becomes obvious that the input file does not indicate the correct number.

ch11/r17

As the program is set up, no. But readFile can throw a NullPointerException if it is passed a null value for the String filename argument. However, the program prevents this from occurring because the filename is initialized from in, which always returns a non-null value.

ch11/r18

If the PrintWriter construction is left outside the try block, the compiler complains because the FileNotFoundException must be caught. The compiler also complains that the IOException is never thrown in the body of the corresponding try statements.

If we move the construction to inside the try block, then the FileNotFoundException exception would be caught by the IOExceptioncatch block. The modified code does not work correctly if the close method throws an exception, because it would not be caught by the catch block.

ch12

ch12/r01

This book recommends the following object-oriented development process:

1. Gather program requirements.

2. Discover classes.

3. Determine the responsibilities of each class and identify collaborating classes.

4. Determine the relationships between the classes.

5. Document the behavior of classes using javadoc comments.

6. Implement classes.

ch12/r02

Classes correspond to nouns in the task description.

ch12/r03

Methods correspond to verbs in the task description.

ch12/r04

After discovering a method, it is important to identify the responsible object because it may need more than one method to carry out the task, and it may need to collaborate with other classes.

ch12/r05

University-Student: aggregation; a university has students

Student-TeachingAssistant: inheritance; a teaching assistant is a student

Student-Freshman: inheritance: a freshman is a student

Student-Professor: neither

Car-Door: aggregation; a car has doors

Truck-Vehicle: inheritance; a truck is a vehicle

Traffic-TrafficSign: no relationship

TrafficSign-Color; no relationship. (Color is an attribute)

ch12/r06

The class BMW can inherit from the class Vehicle-every BMW is a vehicle. However, the BMW company (which is different from the class of all BMWs) is an object of the class VehicleManufacturer. Inheritance is not appropriate for describing the relationship between an instance of a class (an object) and a class.

ch12/r07

The Circle.setLocation method needs to move the center of the circle; the radius is not affected. That is exactly what Point.setLocation does, so the method can be inherited.

However, a circle isn't-a point, so it doesn't make conceptual sense to use inheritance.

The other way around, it makes some conceptual sense. A point is a circle with radius 0. But then it becomes difficult to construct a circle using a point and a radius, since a point is defined only in terms of a circle. It makes more sense to define a class Point and a separate class Circle.

ch12/r08
Coinget value get name               
 
CashRegisterrecord purchaseCoinenter payment give change
ch12/r09
Quizadd question Questionpresent questions               
 
Questionset question textStringset answer check answer display
ch12/r10

ch12/r11
Countryget area get density get name  get population           
 
CountryReaderread file get largest areaCountryget largest density get largest population

Country.html

CountryReader.html

ch12/r12

Student.htmlCourse.htmlReportCard.htmlGrade.html

ch12/r13

One would expect a VendingMachine, Product class and Coin class.

ch12/r14

Answers can vary, but a possible design could use an Employee class to keep track of hourly rates and hours worked as well as a Paycheck class that would use an Employee class to generate a paycheck.

ch12/r15

ch13

ch13/r01

Recursion solves a problem by using the solution to the same problem with simpler values.

Iteration uses some form of a loop (for loop, while loop) to solve a problem.

Infinite recursion occurs when the recursion never stops. A method calls itself over and over again and never reaches an end.

A recursive helper method is a recursive method that is called by another, usually non-recursive, method.

ch13/r02

If the array only has one element, return that element.

Otherwise, recursively find the smallest element of the array that is obtained by removing the last element. Then return the smaller of the last element and the value returned by that recursive call.

ch13/r03

(Similar to Quicksort)

Choose a random pivot element.

Partition the array into [sub-array1], [pivot], [sub-array2] where sub-array1 has elements less than pivot and sub-array2 has elements greater than pivot.

Check size of sub-array1.

If it is greater than k, then recurse with only sub-array1. If it is equal to k-1, then the pivot is the kth element. If it is less than k , then recurse with only sub-array2.

ch13/r04

If the array has no elements or only one element, you are done.

Otherwise, first find the smallest element in the array. After obtaining the smallest number, swap that number with the first element in the array and recursively sort the remaining numbers in the array.

ch13/r05

If the array only has one element, return that element.

Otherwise, recursively find the subarray that is obtained by removing the first element. Then return the mergesort of the first element and the value returned by that recursive call.

ch13/r06

x0 = 1

xn = x * xn-1

ch13/r07

x0 = 1

x2n + 1 = x * x2n, (odd case)

x2n = (xn)2, (even case)

The approach is significantly faster because it reduces the calls to "pow" to as little as 2 + log2n, when n is a power of 2.

For example:

Using the first method:

x1023 took 1024 calls

x1024 took 1025 calls

Using the second method:

x1023 took 20 calls

x1024 took 12 calls

ch13/r08
0! = 1
n! = n * (n - 1)!
ch13/r09

When computing fib(n), the function is called 2 * fib(n) - 1 times, as fibCount indicates.

import java.util.Scanner;
 
/**
   This program computes Fibonacci numbers using a recursive
   method.
*/
public class FibTester
{
   private static int fibCount;
 
   public static void main(String[] args)
   {
      Scanner in = new Scanner(System.in);
      System.out.print("Enter n: ");
      int n = in.nextInt();
 
      for (int i = 1; i <= n; i++)
      {
         fibCount = 0;
         long f = fib(i);
         System.out.println("fib(" + i + ") = " + f);
         System.out.println("number of times fib(n) is called = " + fibCount);
      }
   }
 
   /**
      Computes a Fibonacci number.
      @param n an integer
      @return the nth Fibonacci number
   */
   public static long fib(int n)
   {
      fibCount++;
      if (n <= 2) { return 1; }
      else { return fib(n - 1) + fib(n - 2); }
   }
}
ch13/r10

moves(1) = 2n - 1

To guess this formula, compute:

moves(2) = 2 * moves(1) + 1 = 3

moves(3) = 2 * moves(2) + 1 = 7

moves(4) = 2 * moves(3) + 1 = 15

moves(5) = 2 * moves(4) + 1 = 31

The formula can then be verified by induction.

moves(1) = 1 = 21 - 1

moves(n) = 2 * moves(n -1) + 1 = 2 * (2n -1-1) + 1 = 2n-1

ch13/r11

If n is 1, return a collection containing the empty set and the set { 1 }.

Otherwise, first find all subsets of the set { 1 ... n-1 }. For each subset S in that collection, add two sets to the answer, namely S and S union {n}.

ch13/r12

This algorithm begins with the numbers from 0 to n - 1 in ascending order. It then progresses until the numbers are in descending order at which point 'hasMorePermutations' returns false. At each step a new permutation is made such that the new sequence is lexicographically greater than the previous (e.g., 132 is lexicographically greater than 123; for this specific sequence of numbers one can think more directly of the step as creating a new permutation that is greater than the previous).

A new permutation is generated by finding in the previous permutation the rightmost pair of ascending values (i.e., the pair of ascending values that is nearest to the end of the sequence). If such a pair does not exist, then the final permutation has already been discovered (that in which the sequence is descending). If such a pair is found, then the rightmost value that is greater than the first of the pair is found. This is either the second value of the pair or a value to the right of the pair.

If the value found is the second of the pair, then the remainder of the sequence is descending. In this case, the two values of the pair are swapped and the remainder of the sequence is reversed (so that it is now ascending). This remaining portion will then be permuted to continue the lexicographical orderings.

If the value found is not the second of the pair, then it is the largest of the descending "tail" of the sequence and, thus, the next lexicographic option for the position of the first element of the pair. The tail is reversed to continue the lexicographic orderings.

ch13/r13

3-4+5

(Previous answer assumed ()s around 3 - 4.)

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 3

getTermValue returns 3

getExpressionValue consumes -

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 4

getTermValue returns 4

getExpressionValue consumes +

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 5

getTermValue returns 5

getExpressionValue returns 4 (-1 + 5)

3-(4+5)

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 3

getTermValue returns 3

getExpressionValue consumes -

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue consumes the ( input

getFactorValue calls getExpressionValue

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 4

getTermValue returns 4

getExpressionValue consumes +

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 5

getTermValue returns 5

getExpressionValue returns 9

getFactorValue consumes the ) input

getFactorValue returns 9

getTermValue returns 9

getExpressionValue returns -6 (3 - 9)

(3-4)*5

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue consumes the ( input

getFactorValue calls getExpressionValue

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 3

getTermValue returns 3

getExpressionValue consumes -

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 4

getTermValue returns 4

getExpressionValue returns -1

getFactorValue consumes the ) input

getFactorValue returns -1

getTermValue consumes *

getTermValue calls getFactorValue

getFactorValue returns 5

getTermValue returns -5 (-1 * 5)

getExpressionValue returns -5

3 * 4 + 5 * 6

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 3

getTermValue consumes *

getTermValue calls getFactorValue

getFactorValue returns 4

getTermValue returns 12 (3 * 4)

getExpressionValue consumes +

getExpressionValue calls getTermValue

getTermValue calls getFactorValue

getFactorValue returns 5

getTermValue consumes *

getTermValue calls getFactorValue

getFactorValue returns 6

getTermValue returns 30 (5 * 6)

getExpressionValue returns 42 (12 + 30)

ch14

ch14/r01

Searching means to find an element in a collection of elements. Sorting means to arrange a collection of elements in a particular order.

ch14/r02

Array length 0 or 1: i < a.length - 1 is not true when i equals 0, the for loop in the sort method never executes and the array is unchanged. That is ok.

Array length 2: The for loop in sort executes once, with i = 0. minimumPosition(a, 0) is called. The for loop in that method executes with from = i and going from 1 to less than 2; i.e., that loop also executes once. minPos is initially 0. If a[1] is less than a[0], then minPos is set to 1. When the method returns, the two values are swapped, which causes the array to be sorted.

Array length 3: There are six possible variations of the array. Using 1, 2, 3 for the three elements, they are:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Here is a walk-through for the last scenario. The others are similar.

                sort   minimumPosition
a[0] a[1] a[2]  i      from  minPos   i
3    2    1     0        0     0      1
3    2    1     0        0     1      2
3    2    1     0        0     2
1    2    3     1        1     1      2
1    2    3     1
ch14/r03
n^2+2n+1 O(n^2) n^3-1000n^2+10^9 O(n^3)
n^10+9n^9+20n^8+145n^7 O(n^10) n + log(n) O(n)
(n+1)^4 O(n^4) n^2+nlog(n) O(n^2)
(n^2+n)^2 O(n^4) 2^n+n^2 O(2^n)
n+0.001n^3 O(n^3) (n^3+2n)/(n^2+0.75) O(n)
ch14/r04
T(2000)/T(1000) 2004997/502497=3.99 f(2000)/f(1000) 4
T(4000)/T(1000) 8009997/502497=15.94 f(4000)/f(1000) 16
T(10000)/T(1000) 50024997/502497=99.55 f(10000)/f(1000) 1000
ch14/r05

For a set of 2000 records, it will take 10 seconds.

For a set of 10,000 records, it will take 50 seconds.

ch14/r06
  O(n) O(n^2) O(n^3) O(n log(n)) O(2^n)
1000 5 5 5 5 5
2000 10 20 40 11 can't compute
3000 15 45 135 17 . . .
10000 50 500 5000 67 . . .

In the last column, the values get large too quickly. The following may be more helpful:

  O(2^n)
1000 5
1001 10
1002 20
1003 40
ch14/r07

O(log(n))

O(sqrt(n))

O(n)

O(n log(n))

O(n sqrt(n))

O(n^2 log (n))

O(n^3)

O(n log(n))

O(2^n)

O(n^n)

ch14/r08

The array needs to be traversed once to find the minimum, so the time complexity is O(n), where n is the length of the array. Finding both the minimum and the maximum is no worse than 2O(n) = O(n)

ch14/r09

The complexity of the given method is O(n).

ch14/r10

If the list has a single value then return 1.

Otherwise initialize a value for longest run to zero. Iterate over the list of values counting lengths of runs by counting duplicate values (i.e. difference is zero) When the difference between consecutive values is not zero compare the current run to longest run. If current run is longer then set longest run to current run. Reset current run to zero and continue to end of the list.

ch14/r11

a) Sorting takes the most time. Using the Quicksort the complexity would be O(n log(n)).

b) Counting the duplicate elements takes the most time. The complexity would be O(n^2).

c) Counting the frequency of each element takes the most time. The complexity again would be O(n^2).

ch14/r12

a) 4 7 11 4 9 5 11 7 3 5

Run 1: 3 7 11 4 9 5 11 7 4 5

Run 2: 3 4 11 7 9 5 11 7 4 5

Run 3: 3 4 4 7 9 5 11 7 11 5

Run 4: 3 4 4 5 9 7 11 7 11 5

Run 5: 3 4 4 5 5 7 11 7 11 9

Run 6: 3 4 4 5 5 7 7 11 11 9

Run 7: 3 4 4 5 5 7 7 9 11 11

Run 8: 3 4 4 5 5 7 7 9 11 11

b) -7 6 8 7 5 9 0 11 10 5 8

Run 1: -7 6 8 7 5 9 0 11 10 5 8

Run 2: -7 0 8 7 5 9 6 11 10 5 8

Run 3: -7 0 5 7 8 9 6 11 10 5 8

Run 4: -7 0 5 5 8 9 6 11 10 7 8

Run 5: -7 0 5 5 6 9 8 11 10 7 8

Run 6: -7 0 5 5 6 7 8 11 10 9 8

Run 7: -7 0 5 5 6 7 8 8 10 9 11

Run 8: -7 0 5 5 6 7 8 8 9 10 11

Run 9: -7 0 5 5 6 7 8 8 9 10 11

ch14/r13

a) 5 11 7 3 5 4 7 11 4 9

split: 5 11 7 3 5_4 7 11 4 9

split: 5 11_7 3 5_4 7_11 4 9

split: 5_11_7_3 5_4_7_11_4 9

split: 5_11_7_3_5_4_7_11_4_9

merge: 5_11_7_3 5_4_7_11_4 9

merge: 5 11_3 5 7_4 7_4 9 11

merge: 3 5 5 7 11_4 4 7 9 11

merge: 3 4 4 5 5 7 7 9 11 11

b) 9 0 11 10 5 8 -7 6 8 7 5

split: 9 0 11 10 5_8 -7 6 8 7 5

split: 9 0_11 10 5_8 -7 6_8 7 5

split: 9_0_11_10 5_8_-7 6_8_7 5

split: 9_0_11_10_5_8_-7_6_8_7_5

merge: 9_0_11_5 10_8_-7 6_8_7 5

merge: 0 9_5 10 11_-7 6 8_5 7 8

merge: 0 5 9 10 11_-7 5 6 7 8 8

merge: -7 0 5 5 6 7 8 8 9 10 11

ch14/r14

a)

Iteration 1: Check element at index 0. -7 is not 7.

Iteration 2: Check element at index 1. 1 is not 7.

Iteration 3: Check element at index 2. 3 is not 7.

Iteration 4: Check element at index 3. 3 is not 7.

Iteration 5: Check element at index 4. 4 is not 7.

Iteration 6: Check element at index 5. 7 is found. Done.

b)

Step 1: Check element at index 4 ((0 + 8) / 2). 4 < 8, look in larger half (7 8 11 13).

Step 2: Check element at index 6 ((5 + 8) / 2). 8 == 8. Done.

c)

Step 1: Check element at index 3 ((0 + 7) / 2). 3 < 8, look in larger half (5 7 10 13).

Step 2: Check element at index 5 ((4 + 7) / 2). 7 < 8, look in larger half (10, 13).

Step 3: Check element at index 6 ((6 + 7) / 2). 10 > 8, look in smaller half, but smaller half is empty. Value is not found.

ch14/r15

To look at each a[i] in turn requires n steps, where n is the length of the array. Each of these steps requires n - 1 element visits for the counting, and on average n / 2 steps for the element removal. Therefore, this is an
O(n(n-1 + n/2)) = O(n2) algorithm.

ch14/r16

In the merging step, the items from both lists have to be compared as we remove them from the lists to create the sorted array. If the item being removed is the same as the last item added, we have to throw it way (it is a duplicate). This extra step takes O(n). Overall the new merge sort algorithm takes O(n log(n)) to complete.

ch14/r17

Sorting takes O(n log(n)) time. After the array is sorted, we traverse it.

If we detect adjacent duplicates, we must move the remainder of the array down, which takes on average n/2 steps. So in the worst case this might be an O(n log n + n(n/2)) = O(n2) algorithm.

However, you can easily do better. Sort the array O(n log(n)). Traverse the array, and whenever the next element is strictly larger, append it into a second array (O(n)). Then copy the second array back into the first (O(n)). The result is an O(n log(n)) algorithm. (You can even avoid the second array by moving the elements to the head of the original array.)

ch14/r18

The trouble is that we can't sort the array since that would disturb the original order. However, we can sort a copy to have a fast lookup for duplicates. Here is the algorithm.

Make a copy (O(n)) and sort it (O(n log(n))). Make a companion boolean array to the sorted array and set all values in that array to false. Traverse the array and do the following n times:

For each element, use binary search in the copy (O(log (n))) and then look at the neighbors to determine whether the element is a duplicate. If so, check if the corresponding value in the companion array is false, indicating that this element has never been used previously. If the element is not a duplicate or it has never been used, then append it to a second array, and mark the corresponding boolean as true. Since this needs to be done for each element, we have O(n log(n)) for this phase. The total time complexity is therefore O(n log(n)).

ch14/r19

Selection sort has O(n2), even when the array is already sorted. Selection sort works by building a sorted prefix of the array. It does this by searching for the smallest value in the (suffix) portion of the array to find the next value to add to the known sorted prefix. The algorithm has no mechanism to determine that the assumed unsorted portion is actually sorted. As such, the entirety of the assumed unsorted portion will be searched on each iteration.

On the other hand, insertion sort assumes the array is already sorted, and when it is, it iterates only once through the array. Iteration sort realizes this assumption as it iterates by attempting to insert the next value in the array (as the elements are traversed) into the known sorted prefix. With the array already sorted, inserting the next value will take constant time (the time to compare to the last value in the known sorted portion). Thus, in the case that the array is already sorted, insertion sort has O(n).

ch14/r20

No, it does not. The insertion sort algorithm finds the position where the element needs to be inserted at the same time that it moves the elements that need to be moved to make space for the new element. Thus, it does not actually take any extra iterations to find the position. Using a binary search will find the insertion position in O(log (n)) but will not improve the O(n2) order of the algorithm because the elements will still need to be moved to allow insertion of the element which takes O(n).

ch14/r21

Because there are two nested loops, the running time is O(n2). More specifically, the inner loop must compare each pair of adjacent elements which is a O(n) operation. The outer loop continues as long as the array is not sorted, but determining if an array is sorted is also a O(n) operation. Thus, the algorithm is O(n2).

ch14/r22

The running time of radix sort on n numbers with d digits is O(n * d). It is preferable to merge sort when the number of digits, d, is less than log(n) and when the array is not too large because of the memory required for the auxiliary arrays.

ch14/r23

Selection sort is not stable because the order of occurrence of the same key is hard to maintain after swap. Specifically, swapping the next value in the array with the smallest in the remaining portion of the array may place a duplicate (the next value) later in the array than another element of the same value.

Because multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array, insertion sort is stable. In particular, insertion sort shifts values into the sorted portion of the array from the right. A value will only shift to the left if it is less than the value to its left. As such, when a value meets a duplicate, it remains after the duplicate as it was in the original array.

ch14/r24

Create an array of 256 counters initially set to 0. Iterate through the array of n bytes. For each element, increment the counter at the corresponding index in the counter array (i.e., element i of the byte array is used as an index into the counter array (map the bytes to the range 0 to 255)). This step takes O(n) to analyze each element in the byte array. Iterate through the counter array and for each counter add an equal number of entries in the byte array with value corresponding to the counter position (i.e., the counter at index 0 with value 7 will result in 7 entries in the byte array with value -128). This step also takes O(n) to update each of the entries in the byte array. The algorithm is O(n).

ch14/r25

Let's first make a single array of pairs (word, page). If there are n words (in all arrays together), that takes O(n) time. Then sort the pairs by word, breaking ties by page. That takes O(n log(n)) time. Finally, rewrite into an array of pairs (word, page set). This can again be done in O(n) time. (Note that duplicates can be removed in constant time since the pages are already sorted.) This gives a total of O(n log(n)) time.

ch14/r26

Sort the second array, which takes O(n log(n)) time. For each element of the first array, try binary search across the other array. If you find it, report that there exists a match. Since there are n elements and each binary search takes O(log(n)) time, the running time will at most be O(n log(n)).

ch14/r27

(The previous solution used an additional array, which is unnecessary unless the original array must remain unchanged.)

Sort the array, which takes O(n log(n)) time. For each element x in the array, perform a binary search to find v - x in the array. If found, then x and v - x are both in the array. This step takes n binary searches, each of which takes O(log(n)), for a total of O(n log(n)).

ch14/r28

Sort the second array, which takes O(n log(n)) time. For each element of the first array, try binary search across the other array. Collect each match. Since there are n elements and each binary search takes O(log(n)) time, the total running time will be O(n log(n)).

ch14/r29

For a sorted array, the running time will be linear O(n log(n)). The fact that the array is sorted does give a perfect partitioning at each step (meaning there will be log(n) levels of recursion), but each step must still examine every element of the subarray during the partitioning phase (though no values will be swapped).

ch14/r30

If the pivot is in the middle, the running time would be O(n2) for an array in which the successive pivot values are in sorted order. For instance, the array 2 6 4 1 3 5 7 will use the value 1 as the first pivot (the solution in Special Topic 14.3 can be used mostly as is by swapping the element at the pivot with the first element before partitioning). This results in a partitioning with one subarray holding all remaining values 6 4 2 3 5 7. Again, the pivot selected leaves one subarray holding all remaining values 4 6 3 5 7. The split on pivot 3 gives 6 4 5 7; split on pivot 4 gives 6 5 7; the split on 5 gives 6 7; and splitting on 6 gives 7. As illustrated, the length of the partition is one less than the previous partition. This results in O(n) levels of recursion with O(n) steps in the partitioning process at each level.

ch15

ch15/r01

A list is a good choice here. A list will allow duplicate items to be listed, a likely possibility on an invoice, and implies an order which also may be important for an invoice.

ch15/r02

A list is also a good choice here. A useful appointment calendar application will allow the user to browse appointments; although this is possible with stack or queue implementation, it would be awkward.

ch15/r03

One could create a map to a list of event objects. Then each key (date object) would return a list of all the appointments on that date.

ch15/r04

You can use the methods addAll removeAll containsAll retainAll from the Collection interface to accomplish the following set operations:

1) union: Call the addAll method from one set sending in the other set as the argument.

2) intersection: Call the retainAll method from one set sending in the other set as the argument.

3) difference: Call the removeAll method from one set sending in the found intersection from part 2.

4) subset: Call the containsAll method from one set sending in a collection which represents a subset to be tested.

ch15/r05

The code prints:

Tom
Diana
Harry

The best description to see what is going on is to examine the state of the linked list at each step. In the notation below the list is enclosed by [ and ].

1.

staff.addFirst("Harry");
staff = ["Harry"]

2.

staff.addFirst("Diana");
staff = ["Diana", "Harry"]

3.

staff.addFirst("Tom");
staff = ["Tom", "Diana", "Harry"]

4.

System.out.println(staff.removeFirst()); Prints Tom.

staff = ["Diana", "Harry"]

5.

System.out.println(staff.removeFirst()); Prints Diana.

staff = ["Harry"]

6.

System.out.println(staff.removeFirst()); Prints Harry.

staff = []
ch15/r06

The code prints:

Harry
Tom
Diana

The best description to see what is going on is to examine the state of the linked list at each step. In the notation below the list is enclosed by [ and ].

1.
staff.addFirst("Harry");
staff = ["Harry"]

2.
staff.addFirst("Diana");
staff = ["Diana", "Harry"]

3.
staff.addFirst("Tom");
staff = ["Tom", "Diana", "Harry"]

4.
System.out.println(staff.removeLast()); Prints Harry.
staff = ["Tom", "Diana"]

5.

System.out.println(staff.removeFirst()); Prints Tom.

staff = ["Diana"]

6.

System.out.println(staff.removeLast()); Prints Diana.

staff = []
ch15/r07

This code prints out:

Diana
Tom
Harry

The best description to see what is going on is to examine the state of the linked list at each step. In the notation below the list is enclosed by [ and ].

1.

staff.addFirst("Harry");
staff = ["Harry"]

2.

staff.addLast("Diana");
staff = ["Harry", "Diana"]

3.

staff.addFirst("Tom");
staff = ["Tom", "Harry", "Diana"]

4.

System.out.println(staff.removeLast()); Prints Diana.

staff = ["Tom", "Harry"]

5.

System.out.println(staff.removeFirst()); Prints Tom.

staff = ["Harry"]

6.

System.out.println(staff.removeLast()); Prints Harry.

staff = []
ch15/r08

This code prints the following:

Diana
Harry

The iterator builds up a list (Tom, Diana, Harry), then removes the first Tom while the loop removes the rest. Here is the state of the linked list at each step. In the notation below the list is enclosed by [ and ], and the iterator is indicated by a |.

1.

iterator.add("Tom");
staff = ["Tom"|]

2.

iterator.add("Diana");
staff = ["Tom", "Diana"|]

3.

iterator.add("Harry");
staff = ["Tom", "Diana", "Harry"|]

4.

iterator = staff.listIterator();
staff = [|"Tom", "Diana", "Harry"]

5.

if (iterator.next().equals("Tom"))
staff = ["Tom", |"Diana", "Harry"]

6.

iterator.remove();
staff = [|"Diana", "Harry"]

7.

while (iterator.hasNext())
System.out.println(iterator.next());

Iteration 1 prints Diana:

staff = ["Diana", |"Harry"]

Iteration 2 prints Harry:

staff = ["Diana", "Harry"|]
ch15/r09

The following code prints:

Diana
Romeo
Harry
Juliet

It is best explained by examining the state of the linked list. In the notation below the list is enclosed by [ and ], and the iterator is indicated by a |.

1.

iterator.add("Tom");
staff = ["Tom"|]

2.

iterator.add("Diana");
staff = ["Tom", "Diana"|]

3.

iterator.add("Harry");
staff = ["Tom", "Diana", "Harry"|]

4.

iterator = staff.listIterator();
staff = [|"Tom", "Diana", "Harry"]

5.

iterator.next();
staff = ["Tom", |"Diana", "Harry"]

6.

iterator.next();
staff = ["Tom", "Diana", |"Harry"]

7.

iterator.add("Romeo");
staff = ["Tom", "Diana", "Romeo", |"Harry"]

8.

iterator.next();
staff = ["Tom", "Diana", "Romeo", "Harry"|]

9.

iterator.add("Juliet");
staff = ["Tom", "Diana", "Romeo", "Harry", "Juliet"|]

10.

iterator = staff.listIterator();
staff = [|"Tom", "Diana", "Romeo", "Harry", "Juliet"]

11.

iterator.next();
staff = ["Tom", |"Diana", "Romeo", "Harry", "Juliet"]

12.

iterator.remove();
staff = [|"Diana", "Romeo", "Harry", "Juliet"]

13.

while (iterator.hasNext())
System.out.println(iterator.next());

Iteration 1 prints Diana:

staff = ["Diana", |"Romeo", "Harry", "Juliet"]

Iteration 2 prints Romeo:

staff = ["Diana", "Romeo", |"Harry", "Juliet"]

Iteration 3 prints Harry:

staff = ["Diana", "Romeo", "Harry", |"Juliet"]

Iteration 4 prints Juliet:

staff = ["Diana", "Romeo", "Harry", "Juliet"|]
ch15/r10
// remove all  strings of length <= 3
Iterator<String> itr - list.iterator();
while (itr.hasNext())
{
   String item = itr.next();
   if (item.length() <= 3)
   {
      itr.remove();
   }
}
  
ch15/r11
// remove all  strings of length <= 3
theList.removeIf(str -> str.length() <= 3)
  
ch15/r12

Linked lists can be advantageous over arrays if an application needs to add or remove data arbitrarily throughout the list; this process is relatively easy using linked lists but more difficult with arrays. A disadvantage is that randomly accessing elements within the linked list can be inefficient compared to an array.

ch15/r13

Answers can vary here.

Since there is a known upper bound on the data (10,000 elements) and the employee directory is relatively fixed, one could argue the use of an array list due to its efficient random access operator. On the other hand, if the employee list is heavily modified, one may prefer a linked list due to its ease of modification.

In practice, 6,000 elements and several hundred accesses is not a large data set or a computationally complex problem. It's likely that there will be no noticeable performance difference between the two.

ch15/r14

Since appointments are often added and removed, one would probably prefer a linked list. The linked list will allow easy addition and removal of appointments.

ch15/r15

A queue since this data structure specifically limits additions to one end and removals from the other. A stack is the opposite where removals and additions occur on the same end.

ch15/r16

When "A"..."Z" are pushed on the first stack they will be stored in reverse order "Z"..."A". When popped off the first and pushed on the second, they will be in alphabetical order again "A"..."Z". Thus, they will be popped off the second stack in alphabetical order and will print "A"..."Z".

ch15/r17

Although both a set and map are unordered, the relevant property of a set is membership, where a map is a data structure that allows lookups of values based on a given key.

ch15/r18

To compute the union of set A and set B, remove one element from B at a time and add each element to A; continue this until B is empty.

To compute the intersection of set A and set B, remove each element from A, use contains to check whether the element is in B and if it is, add it to a temporary set; continue this until A is empty. The resulting set is the intersection between A and B.

ch15/r19

A union between a set A and B can be easily computed with the addAll method. First addAll elements from A to a copy of A, then addAll elements in B to that copy. The result is the union between A and B.

An intersection can be computed with the removeAll method. First, make a copy of B, then removeAll elements in B that are also in A. This leaves you all the elements in B that are not the intersection between B and A; thus removeAll of those elements from the original set of B, and you're left with the intersection.

ch15/r20

A map can have two keys with the same value because the map would fetch either value depending on the key.

On the other hand, a map cannot have two values with the same key, as the map would be unable to distinguish which one is associated with an identical key.

ch15/r21

If a set contained (key, value) pairs, one could implement a get by iterating over the set until a key was found that matched the requested key, then the algorithm would return the value associated with that key.

The put operation can be implemented by first checking that no (key, value) pair exists with the same key, then adding the given (key, value) pair to the set.

ch15/r22

Printing all key/values pairs of a map:

a) Using ketSet method:

//Assuming String/Integer key/value pairs
for (String key : theMap.keySet())
{
   Integer value = theMap.get(key);
	System.out.println(key + " - " + value);
}

b) Using entrySet method:

//Assuming String/Integer key/value pairs
Set set = theMap.entrySet();
Interator itr = set.iterator();
while (itr.hasNext())
{
   Map.Extry entry = (Map.Entry)itr.next();
	System.out.println(entry.getKey() + " - " + entry.getValue());
}

c) Using forEach and functional notation:

//Assuming String/Integer key/value pairs
theMap.forEach((key, value) -> System.out.println(key + " - " + value));
ch15/r23

This code:

String a = "Juliet";
System.out.println(a.hashCode());

Prints:

-2065036585

Which conforms to Table 6.

ch15/r24

This code:

String a = "VII";
      String b = "Ugh";
      System.out.println(a.hashCode() == b.hashCode());

Prints:

true

Which proves the hash codes are the same.

ch15/r25

The figure in the exercise should look like this:

Start at A

A (right)

Visit B

B (up)

B (right)

Visit H

H (up)

H (right)

H (left)

B (right)

Visit P

P (right)

P (left)

H (right)

H (left)

B (right)

Visit Q

Q (right)

Q (down)

P (left)

H (right)

H (left)

B (right)

Visit R. Dead end

Q (down)

P (left)

H (right)

H (left)

B (right)

Visit J

J (right)

P (left)

H (right)

H (left)

B (right)

Visit K. Exit.

ch15/r26

Start at A

A-right

Visit B

B-up B-right

Visit C. Dead end

B-up

Visit H.

H-up H-right H-left

Visit G.

G-up H-up H-right

Visit I.

I-up G-up H-up

Visit P.

P-right P-left I-up G-up

Visit L. Dead end.

P-right P-left I-up

Visit N.

N-left P-right P-left

Visit O. Dead end.

N-left P-right

Visit Q.

Q-right Q-down N-left

Visit M. Dead end.

Q-right Q-down

Visit J.

J-right Q-right

Visit R. Dead end.

J-right

Visit K. Exit.

ch16

ch16/r01

Insertion:

Removal:

Insertion:

Removal:

ch16/r02

Insertion:

Removal:

Insertion:

Removal:

ch16/r03

Both are O(n) operations, where n is the length of the list.

ch16/r04

The first is an O(n) operation, but the second is O(n^2) since removing an element is an O(n) operation.

ch16/r05

It is tempting to set previous to null after a call to add or remove, but that doesn't work. If one visits the first element, then previous is legitimately null.

Instead, one can set previous and position to the same value after each call to add or remove. This can never happen after a call to next. (After calling next, we either have previous == null and position == first, or previous != null and position == previous.next. In either case, previous != position.)

public void remove()
{
    if (position == previous) { throw new IllegalStateException(); }
    if (position == first)
    {
       removeFirst();
    }
    else
    {
       previous.next = position.next;
    }
    position = previous;
}
 
public void add(Object element)
{
    if (position == null)
    {
       addFirst(element);
       position = first;
    }
    else
    {
       Node newNode = new Node();
       newNode.data = element;
       newNode.next = position.next;
       position.next = newNode;
       position = newNode;
    }
    previous = position;
}
ch16/r06

O(n)

ch16/r07

Correction: The problem statement should refer to the size method in P16.6.

The currentSize instance variable needs to be incremented in the add method and decremented in the addFirst and removeFirst method of the list class and the remove method of the iterator. With this change, add and remove are still O(1). No other methods change the currentSize variable.

ch16/r08

Correction: The problem statement should refer to the size method in P16.6.

With the implementation in P16.7, get is O(n). Therefore, the loop is O(n^2).

ch16/r09

Correction: The problem statement should refer to the size method in P16.6.

Because a call get(i + 1) that follows a call get(i) is O(1), this loop is O(n).

ch16/r10

When the iterator has traversed the first element, its position reference points to the first node. If one calls removeFirst, the iterator points to a node that is no longer in the linked list.

Now suppose we call remove on the iterator:

if (position == first)
{
   removeFirst();
}
else
{
   previous.next = position.next;
}
position = previous;

As you can see from the drawing, position != first, and the second branch is executed. Because previous is null, an exception is thrown.

ch16/r11
public class R16_11
{
    public static void main(String[] args)
    {
       LinkedList staff = new LinkedList();
       staff.addFirst("Tom");
       staff.addFirst("Romeo");
       staff.addFirst("Harry");
       staff.addFirst("Diana");
 
       ListIterator iterator = staff.listIterator(); // |DHRT
       iterator.next(); // D|HRT
       staff.removeFirst();
       iterator.remove();
    }
}
 
$ java R16_11
Exception in thread "main" java.lang.NullPointerException
 at LinkedList$LinkedListIterator.remove(LinkedList.java:163)
        at R16_11.main(R16_11.java:14)
ch16/r12

Have the first iterator before the first element, and the second iterator traverse the first element of a list. Then insert an element through the first iterator. The figure shows the result.

Now call remove on the second iterator.

if (position == first)
{
   removeFirst();
}
else
{
   previous.next = position.next;
}
position = previous;

As you can see from the figure, position != first, and the second branch is executed. Because previous is null, an exception is thrown.

ch16/r13
public class R16_13
{
    public static void main(String[] args)
    {
       LinkedList staff = new LinkedList();
       staff.addFirst("Tom");
       staff.addFirst("Romeo");
       staff.addFirst("Harry");
       staff.addFirst("Diana");

       ListIterator iterator1 = staff.listIterator();
       ListIterator iterator2 = staff.listIterator();
       iterator1.next();
       iterator1.add("Fred");
       iterator2.remove();
    }
}
 
$ java R16_13
Exception in thread "main" java.lang.IllegalStateException
 at LinkedList$LinkedListIterator.remove(LinkedList.java:155)
        at R16_13.main(R16_13.java:15)
ch16/r14

Add a mutationCount to the LinkedList class. Add an iteratorMutationCount in the LinkedListIterator class. In the methods addFirst and removeFirst of the LinkedList class, increment the mutationCount field.

When you construct an iterator, set

iteratorMutationCount = mutationCount

In the methods add and remove of the LinkedListIterator class, increment both counts.

At the beginning of the add and remove method of the LinkedListIterator class, add the statement

if (mutationCount != iteratorMutationCount)
{
   throw new ConcurrentModificationException();
}
ch16/r15

To get to the kth element of a list of length n takes O(k) steps if one starts at the front, or O(min(k, n - k)) steps if one starts at the front or back, whichever is closer. Assuming k is randomly chosen between 0 and n - 1, on average, O(k) = O(n / 2) = O(n), and O(min(k, n - k)) = O(n / 4) = O(n).

ch16/r16

The get operation is now O(1) since we can look up the link to n - n % 10 in constant time, and then make < 10 hops to get to n. However, maintaining that array of node references is very expensive when adding or removing elements in the middle of an array. For example, if one removes an element in position 19, all references to locations 20, 30, ..., have to be updated - an O(n / 10) = O(n) operation. In other words, we have lost the benefit of O(1) insertion and removal.

ch16/r17

As n elements are added, an O(n) resize will occur every 10 steps. Because Big-Oh discards constant factors (in this case, 1/10), the result remains O(n).

ch16/r18

First fill the array with 10 * 2k elements, so that it is just about to reallocate.

Then add one element and remove one. The addition reallocates, and the removal reallocates again. The cost is not O(1) - you can make it arbitrarily high by choosing an appropriate k.

ch16/r19

For each addLast operation, charge $2. Spend $1 on moving the value to be added to the end of the array, and put the other $1 in the bank. When it comes time to reallocate the array to one that is twice as large, you must copy n elements, but there will be enough money in the bank to pay for that.

For each removeLast operation, charge $2. Spend $1 on returning the removed value, and put the other $1 in the bank. When it comes time to reallocate the array to one that is 1/2 as large, you must copy n / 4 elements, so there will be more than enough money in the bank to pay for that.

ch16/r20

Moving the head element to the tail is simply q.add(q.remove()), also O(1). Moving the tail to the head requires a loop:

int n = q.size();
for (i = 1; i < n; i++) { q.add(q.remove()); }

For example, if n = 4

A B C D

D A B C

C D A B

B C D A

The loop is executed n - 1 times, so it's O(n).

ch16/r21

a) addFirst, removeFirst, addLast are O(1), but removeLast is O(n); see Section 16.1.8

b) All are O(1)

c) All are O(1+)

ch16/r22

No. There are two situations when head==tail: when the queue is entirely empty, or when it is entirely full.

ch16/r23

a.

1  2  3  4  5  _  _  _  _  _  currentSize = 5
H              T

b.

1  2  3  4  5  _  _  _  _  _  currentSize = 2
         H     T

c.

6  7  8  4  5  1  2  3  4  5  currentSize = 10
         H     T
4  5  1  2  3  4  5  6  7  8  _  _  _  _  _  _  _  _  _  _  currentSize = 10
H                             T
4  5  1  2  3  4  5  6  7  8  9  10  _  _  _  _  _  _  _  _  currentSize = 12
H                                    T

d.

4  5  1  2  3  4  5  6  7  8  9  10  _  _  _  _  _  _  _  _  currentSize = 4
                        H            T
ch16/r24

You have stacks S1 and S2.

When adding a value, add it to S1. When removing a value, first check if S2 is empty, in which case you pop all values from S1 and push them onto S2. Then pop the value from S2.

For example,

S1: S2:

Add 1

S1: 1 S2:

Add 2

S1: 1 2 S2:

Add 3

S1: 1 2 3 S2:

Remove

S1: S2: 3 2 1

S1: S2: 3 2

Remove

S1: S2: 3

Add 4

S1: 4 S2: 3

Remove

S1: 4 S2:

Remove

S1: S2: 4

S1: S2

The cost for adding is clearly O(1), because we just add to a stack. The cost for removing is O(1+). We pay for transferring elements from S1 to S2, but that cost is amortized over each removal.

ch16/r25

You have two queues, an active one (A) and a temporary one (T). When pushing an element, add it to the active one. When popping an element, move all but the last element from the active one to the temporary one. The last one is the one to be returned. Then flip the active and temporary queues.

The cost for pushing is O(1) because we add to a queue. The cost for popping is O(n) because we need to move n - 1 elements to the other queue.

ch16/r26

It doesn't work if one has different objects with the same content. Consider a hash set of Fred's favorite colors. You want to find out whether Fred loves green. No problem - look for Color.GREEN. But what about chartreuse? If you construct a new Color(127, 255, 0) to find out, then that object has a different ID than the new Color(127, 255, 0) that Fred constructed.

ch17

ch17/r01

There is only one general tree of a given height with one leaf:

o
|
o
|
.
.
.
|
o

If the tree is a binary tree, then there are 2(h - 1) versions, depending on whether each edge points left or right. For example, if h = 3:

     o        o            o             o
    /        /              \             \
   o        o                o             o
  /          \              /               \
o            o            o                 o

A general tree of height 2 has one root and k - 1 leaves:

      o
  / / | \ \
o o  o  o o

If the tree is a binary tree, there are three possibilities:

    o   o           o
   /     \         / \
  o       o       o   o
ch17/r02

Set maximum to the number of siblings in the root. Find the maximum number of siblings in each subtree and compare that to the number of siblings in the root. If any are larger, set maximum to that number.

ch17/r03

If r is a leaf, TPL(r) = 1.

Otherwise, if r has children c1...ck, then TPL(r) = LEAVES(r) + TPL(c1) + ... + TPL(ck), where LEAVES(r) is the number of leaves of the tree r, recursively defined as

LEAVES(r) = 1 if r is a leaf, and

LEAVES(r) = LEAVES(c1) + ... + LEAVES(ck) if r has children c1... ck

ch17/r04

Here is an inductive proof of both facts.

If the tree has one leaf, then it certainly has >= l - 1 interior nodes. There are three such trees:

     o    o   o
     /     \
    o       o

The latter two have interior nodes with one child, but the first one has no interior nodes at all, or l - 1 interior nodes.

Now assume that r is the root of a tree with children c1 and c2, which have l1 and l2 leaves respectively. Note that l1 + l2 = l. Inductively, c1 has >= l1 - 1 interior nodes and c2 has >= l2 - 1 interior nodes. Therefore, r has >= l1 - 1 + l2 - 1 + 1 = l - 1 interior nodes since r itself is an interior node.

Now assume that r = l - 1 = l1 - 1 + l2- 1 + 1. Then we know that c1 must have exactly l1 - 1 interior nodes and c2 must have exactly l2 - 1 interior nodes. (If one had more, the other would have to have fewer, violating the inductive assumption.) Therefore, all of the interior nodes in c1 and c2 have two children. In particular, neither is empty, and r has two children as well.

ch17/r05

A binary search tree is a binary tree. However, in a binary search tree, each subtree has the property that all descendants to the left are smaller than the value in the subtree's root, and that all descendants to the right are larger than the value in the subtree's root.

Here is a binary tree that isn't a binary search tree:

        Harry
       /     \
    Tom       Diana

Here is a binary tree that is a binary search tree:

        Diana
             \
            Tom
            /
         Harry
ch17/r06

In a balanced tree, each subtree has the property that the number of descendants to the left is approximately equal to the number of descendants to the right. In an unbalanced tree, this property does not hold.

Here is a balanced binary tree:

        Harry
       /     \
    Tom       Diana

Here is a binary tree that is not balanced:

        Diana
             \
            Tom
            /
         Harry
ch17/r07
       Adam
 
       Adam
           \
            Eve
 
       Adam
           \
           Eve
               \
                Romeo
 
       Adam
           \
            Eve
                \
                Romeo
               /      
          Juliet       
 
       Adam
           \
            Eve
                \
                Romeo
               /      \
          Juliet       Tom
 
       Adam
           \
            Eve
          /     \
     Diana       Romeo
               /      \
          Juliet       Tom
 
       Adam
           \
            Eve
         /      \
     Diana       Romeo
               /      \
          Juliet       Tom
         /
    Harry
ch17/r08

The tree is

                      Harry
                    /       \
                Diana         Tom
               /     \       /
             Adam    Eve   Juliet
                                 \
                                 Romeo

Printing this tree with the print method yields the printout

Adam
Diana
Eve
Harry
Juliet
Romeo
Tom

That's the same printout as the printout resulting from the tree in the preceding exercise because the tree contents are always printed in sorted order, no matter in which order the nodes were inserted.

ch17/r09

2 7 4 1 8 5 3 9 6 10

ch17/r10

Given a binary tree t with left and right children l and r, define

elem(k, t) = undefined if t is a leaf and k> 0, or if t is empty

= elem(k, l) if k<size(l)

= t.data if k = size(l)

= elem(k - size(l) - 1, r) otherwise

The algorithm must compute the size of each left subtree, which is O(n). (Consider the worst case where the tree is completely populated with 2h - 1 nodes. Then the left subtrees have sizes 2(h - 1) - 1, 2(h - 2) - 1, ..., which add up to about 2h or n.)

The remainder of the algorithm is O(log(n)). Therefore, the total execution time is O(n).

ch17/r11

The algorithm is the same as the one described in Exercise R17.11. However, if each node has the size of its subtree pre-calculated, the total cost is O(log(n)), the length of the path to the kth node. (Here we assume the tree to be balanced.)

When adding an element, then the sizes need to be incremented on all nodes along the path from the added node to the root. You can do it as you recurse the tree, moving to the left or right to find the insertion location. The effort is proportional to the path to the insertion location, or O(log(n)), assuming the tree is balanced. This won't affect the efficiency of the add operation.

Similarly, when removing an element, you can decrement the sizes of the traversed nodes in O(log(n)) time.

ch17/r12

Let t1 and t2 be binary trees with children l1, r1 and l2, r2 respectively.

sameShape(t1, t2) = true if t1 and t2 are both leaves or both empty

= false if t1 is a leaf but t2 is not, or t2 is a leaf and t1 is not

= false if t1 is empty but t2 is not, or t2 is empty and t1 is not

= sameShape(l1, l2) && sameShape(r1, r2) otherwise

Since the algorithm recursively visits all nodes of t1 and t2 in the "worst" case in which the shapes are the same, its execution time is O(n1 + n2).

18: We show this by induction. If bh = 1, then the tree has at least 22 - 1 = 1 nodes. Now assume that bh> 1. If a child is black, then its black height is bh - 1. If it is red, it must have two black children, each of black height bh - 1. In either case, each subtree has >= 2(bh - 1) - 1 children by induction, and the tree has >= 2 * 2(bh - 1) - 2 + 1 = 2bh - 1 children.

ch17/r13

ch17/r14

Inorder:

a as fleece had its lamb little mary snow was white

Preorder:

mary had a fleece as little lamb its was snow white

Postorder:

as fleece a its lamb little had snow white was mary
ch17/r15

No children: as, its, snow, white

One child: a, fleece, lamb, little

Two children: mary, had, was

No children: In each case, the node can be removed without any change to the rest of the tree.

One child: In each case, the node can be removed and be replaced by its single child:

Two children: mary, had, was

No children: as, its, snow, white

One child: a, fleece, lamb, little

Two children: mary, had, was

No children: In each case, the node can be removed without any change to the rest of the tree.

One child: In each case, the node can be removed and be replaced by its single child:

Two children: mary, had, was

No children: as, its, snow, white

One child: a, fleece, lamb, little

Two children: mary, had, was

No children: In each case, the node can be removed without any change to the rest of the tree.

One child: In each case, the node can be removed and be replaced by its single child:

Two children: mary, had, was

No children: as, its, snow, white

One child: a, fleece, lamb, little

Two children: mary, had, was

No children: In each case, the node can be removed without any change to the rest of the tree.

One child: In each case, the node can be removed and be replaced by its single child:

Two children: mary, had, was

No children: as, its, snow, white

One child: a, fleece, lamb, little

Two children: mary, had, was

No children: In each case, the node can be removed without any change to the rest of the tree.

One child: In each case, the node can be removed and be replaced by its single child:

Two children: mary, had, was

No children: as, its, snow, white

One child: a, fleece, lamb, little

Two children: mary, had, was

No children: In each case, the node can be removed without any change to the rest of the tree.

One child: In each case, the node can be removed and be replaced by its single child:

Two children: mary, had, was

No children: as, its, snow, white

One child: a, fleece, lamb, little

Two children: mary, had, was

No children: In each case, the node can be removed without any change to the rest of the tree.

One child: In each case, the node can be removed and be replaced by its single child:

Two children: mary, had, was

ch17/r16

Underlined nodes are black; others are red.

ch17/r17

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

No children: its, snow, a, fleece, white

One child: lamb, mary

Two children: little, had, was, as

No children: its and snow are red and can be removed without any change to the tree. Because a and fleece are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:

To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white is red and can be removed:

One child: lamb, mary

Two children: To remove little:

To remove had:

To remove was:

To remove as:

ch17/r18

We show this by induction. If bh = 1, then the tree has at least 22 - 1 = 1 nodes. Now assume that bh > 1. If a child is black, then its black height is bh - 1. If it is red, it must have two black children, each of black height bh - 1. In either case, each subtree has >= 2(bh - 1) - 1 children by induction, and the tree has >= 2 * 2(bh - 1) - 2 + 1 = 2bh - 1 children.

ch17/r19

rbts(1) = 3

    b      b          b
          /            \
         r              r

rbts(bh) = (rbts(bh - 1) + rbts(bh - 1)2)2

Therefore, rbts(2) = (3 + 9)2 = 144

rbts(3) = (144 + 1442)2 = 435974400

ch17/r20

The maximum is attained when one has as many red nodes as possible.

        b
     /     \
    r        r
  /  \      / \
 b    b    b   b
/\   /\  /\   /\
r r r r  r r  r r

That's a complete tree with h = 2 * bh and 2h - 1 = 4bh - 1 nodes.

ch17/r21

Every interior red node must have two black children. (It can't have red children because of the double red rule. If it had no children, it wouldn't be interior. If it had one black child, the equal exit cost rule would be violated.) Therefore, there must be at least twice as many black nodes as interior red nodes.

ch17/r22

The color of the root never matters, except in the last step of bubbling up a double-red, where a red root is colored black. Omitting this step doesn't change the big-oh efficiency.

ch17/r23

With dummy nodes, each node has exactly two children, and the "equal exit cost" refers to paths from the root to leaves of the tree, not nulls. It also eliminates one of the cases in the removal algorithm (the second easy one).

ch17/r24

When removing an element from a priority queue, the element with the highest priority is retrieved. To implement a priority queue with a binary search tree is straightforward. We just need to add elements as we normally would; and, to remove an element from the priority queue, we would find the largest element in the tree (the rightmost element) and remove it. Adding, finding, and removing an element are each O(log(n)) operations. Thus, adding and removing an element from a priority queue - if implemented with a binary search tree - would take O(log(n)) time.

ch17/r25

None of the traversal orders (preorder, inorder, postorder) would print a heap in sorted order because the heap structure is a level-by-level structure, and not a node-by-node structure like that of a binary search tree. On a heap there is no relationship between the left branch of a node and the right branch of a node, other than the fact that both contain elements that are greater or equal than the node itself (a min-heap). For example, consider the heap:

      85
   /     \
  90     86
 /  \   /  \
91  92 88  89

Preorder traversal: 85 90 91 92 86 88 89
Inorder traversal: 91 90 92 85 88 86 89
Postorder traversal: 91 92 90 88 89 86 85

ch17/r26

A heap of height h has h - 1 complete levels, but the last level can have 1 to 2h - 1 elements. A complete binary tree has 2h - 1 elements. Thus, a heap has 2h - 1 elements plus the number of elements in the last level. The minimum number of elements that a heap can have is 2h - 1 and the maximum number of elements that a heap can have is

2h - 1 + 2h - 1 - 1 = 2h - 1.

ch17/r27

The nodes are stored as

Unused | Root = n00 | Level 1 = n10 n11 | Level 2 = n20 n21 n22 n23 | . . .
  [0]        [1]             [2]                 [4]

There are 2k nodes in level k (because each complete level has twice as many nodes as its parent).

Therefore, the kth level starts at index 1 + 1 + 2 + 4 + . . . + 2k -1 = 2k.

The jth node in the kth level has index i = 2k + j.

Since it is preceded by j nodes in its level, its children are preceded by 2j nodes in the next level. That is, they are in positions 2j and 2j + 1. (Note that we count positions starting with 0.)

Therefore, their array indexes are 2k + 1 + 2j and 2k + 1 + 2j + 1.

Those are the same values that the child node formula produces: The left child index is 2i = 2 * (2k + j) = 2k + 1 + 2j, and the right child index is 2i + 1 = 2 * (2k + j) + 1 = 2k + 1 + 2j + 1.

The formula for the parent index follows immediately. If the child of the parent with index p has index i = 2p or i = 2p + 1, then clearly p = i / 2, where / denotes integer division.

ch17/r28

Start calling fixHeap with the parent of the last node, then move to the root

11 | 27 8 | 14 45 6 24 | 81 29 33
               --
 
11 | 27 8 | 14 45 6 24 | 81 29 33
            --
    
11 | 27 8 | 81 45 6 24 | 14 29 33
        -
 
11 | 27 24 | 81 45 6 8 | 14 29 33
     --
 
11 | 81 24 | 29 45 6 8 | 14 27 33
--
 
81 | 45 24 | 29 33 6 8 | 14 27 11

Now keep swapping the root with the last unsorted element, and call fixHeap after each swap.

45 | 33 24 | 29 11 6 8 | 14 27 / 81
33 | 29 24 | 27 11 6 8 | 14 / 45 81
29 | 27 24 | 14 11 6 8 / 33 45 81
27 | 14 24 | 8 11 6 / 29 33 45 81
24 | 14 6 | 8 11 / 27 29 33 45 81
14 | 11 6 | 8 / 24 27 29 33 45 81
11 | 8 6 / 14 24 27 29 33 45 81
8 | 6 / 11 14 24 27 29 33 45 81
6 / 8 11 14 24 27 29 33 45 81

ch18

ch18/r01

Type parameters are variables that can be instantiated with class or interface types.

ch18/r02

A generic class has one or more type parameters. In order to use a generic class, you need to instantiate the type parameters, that is, supply actual types. Ordinary classes do not use type parameters.

ch18/r03

A generic class is a class with one or more type parameters. A generic method is a method with one or more type parameters.

ch18/r04

You must provide a type argument for instantiating a generic class so that the compiler knows the memory size for each each element within the gereic class. There is no need to supply type arguments when invoking an instantiation of a generic class since the type class is already known.

ch18/r05

The toArray method in the java.util.LinkedList class:

public <T> T[] toArray(T[] a)
ch18/r06
AbstractMap<K,V>
Dictionary<K,V>
EnumMap<K extends Enum<E>,V>
HashMap<K,V>
Hashtable<K,V>
IdentityHashMap<K,V>
LinkedHashMap<K,V>
TreeMap<K,V>
WeakHashMap<K,V>
ch18/r07
java.lang.Class<T>
java.lang.Enum<T>
java.util.concurrent.Exchanger<V>
java.util.concurrent.ExecutorCompletionService<V>
java.util.concurrent.FutureTask<T>
ch18/r08

A binary search locates a value in a sorted array by determining whether the value occurs in the first or second half, then repeating the search in one of the halves. To know if the key occurs in the first half or second half, the binary search algorithm needs to be able to determine whether the key is smaller or greater than the middle element. The type bound allows it to use the compareTo method of the Comparable interface to compare values because any value in the array must implement Comparable.

ch18/r09

All classes are descendants of the class Object. The class Object has a method to calculate the hash code of an object. Thus, objects of any class can be stored in a hash set.

ch18/r10

It is an array list of Pairs of objects of the same type (e.g. an array list of String pairs).

ch18/r11

public static <T extends Comparable<? super T>> void sort(List<T> a) means that the type variable T must extend Comparable<U> for some type U where U is any supertype of T (or possibly T itself).

The bound <T extends Comparable> would not have been sufficient. Suppose we want to sort an ArrayList<BankAccount>, where the class BankAccount implements Comparable<BankAccount>. Then we would get a warning. A Comparable object is willing to compare itself against any object, but a BankAccount is only willing to compare against another BankAccount.

public static <T extends Comparable<T>> void sort(List<T> a) does not suffice either because it is still too restrictive. Suppose the BankAccount class implements Comparable<BankAccount>. Then the subclass SavingsAccount also implements Comparable<BankAccount> and not Comparable<SavingsAccount>.

ch18/r12

We will call the method with the raw ArrayList parameter the "legacy method". You can pass a parameterized type, such as ArrayList<String> or ArrayList<BankAccount> to the legacy method. This is not completely safe - after all, the legacy method might insert an object of the wrong type. Nevertheless, your program will compile without a warning.

For example, compiling and running the following program does not produce a warning or error:

import java.util.ArrayList;

public class Test
{
   public static void print(ArrayList list)
   {
      for (int i = 0; i < list.size(); i++)
      {
         System.out.println(list.get(i));
      }
   }

   public static void main(String args[])
   {
      ArrayList<String> strList = new ArrayList<String>();
      strList.add("A");
      strList.add("B");
      strList.add("C");
      print(strList);
   }
}
ch18/r13

We will call the method with the raw ArrayList parameter the "legacy method".

The code calling the legacy method will compile without a warning. A warning is issued for the legacy method. When the wrong element is inserted, no error happens at that time. When the element with the wrong type is later retrieved, then a ClassCastException occurs.

Consider this example:

import java.util.ArrayList;
 
public class Test
{
   public static void main(String args[])
   {
      ArrayList<String> strList = new ArrayList<String>();
      strList.add("A");
      strList.add("B");
      strList.add("C");
      doSomethingBad(strList);
      String first = strList.get(0);
   }
 
   public static void doSomethingBad(ArrayList list)
   {
      list.add(0, new BankAccount(10000));
   }
}

Compiling with the -Xlint:unchecked option yields this warning:

javac -Xlint:unchecked Test.java
Test.java:17: warning: [unchecked] unchecked call to add(int,E) as a
member of the raw type java.util.ArrayList
      list.add(0, new BankAccount(10000));
              ^

We get the following run-time error:

java Test
Exception in thread "main" java.lang.ClassCastException: BankAccount
cannot be cast to java.lang.String
 at Test.main(Test.java:12)
ch18/r14

Compiling

ArrayList<BankAccount> accounts = new ArrayList<BankAccount>();
if (accounts instanceof ArrayList<String>) 
{   
   System.out.println("true");
}
else 
{
   System.out.println("false");
}

produces the following error:

Test.java [15:1] illegal generic type for instanceof
      if (accounts instanceof ArrayList<String>) System.out.println("true");
                                       ^

The virtual machine that executes Java programs does not work with generic classes or methods. Instead, it uses raw types, in which the type parameters are replaced with ordinary Java types. Each type parameter is replaced with its bound, or with Object if it is not bounded. The compiler erases the type parameters when it compiles generic classes and methods.

At run time, Java uses raw types (e.g. Object or Comparable). Since "accounts instanceof ArrayList<String>" cannot be translated to a run-time raw type, its use is not allowed.

ch18/r15

You should look for the source code in a directory similar to

C:\Program Files\Java\jdk1.6.0_03\src.zip

and inside the zipped file, under java\util you should find ArrayList.java. Copy this file and look through it. You see immediately that the class contains an array of Object elements.

private transient Object[] elementData;

There is a constructor:

public ArrayList(Collection<? extends E> c)

The argument is a Collection that inherits from a class of type parameter E. The Collection elements are placed into the Object array by using the following:

elementData = c.toArray();

It is expected that the toArray method will return an Object array. If the conversion doesn’t happen correctly, it compensates by coercing it with a copy and specifying the original class.

if (elementData.getClass() != Object[].class)
   
{
   elementData = Arrays.copyOf(elementData, size, Object[].class);
}

ch19

ch19/r01
  1. words.filter(w -> w.startsWith("a")).count()
  2. words.filter(w -> w.startsWith("a")).filter(w -> w.length() > 10).count()
  3. words.filter(w -> w.startsWith("a")).limit(100).count()
ch19/r02

Traditional Code to collect 5 large words from an ArrayList<String>

int count = 0;
ArrayList<String> resultList = new ArrayList<>();
Iterator<String> oldList = words.iterator();
while (oldList.hasNext() && count < 5)
{
   String str = oldList.next();
   if (str.length() > 10)
   {
      resultList.add(str);
      count++;
   }
}

New code with Streams

resultStream = wordList.stream();
   .filter(w -> w.length() > 10)
   .limit(5);

The new stream syntax is easier to understand.

ch19/r03

a) This statement finds the first 100 elements that have a length greater than 10.

b) This statement finds the elements with length greater than 10 within the first 100 elements.

ch19/r04

1) Using the Stream.of method by listing the elements:

  Stream<String> wordStream = Stream.of("Mary", "had", "a", "little", "lamb");
  

2) Using the Steam.of method and an Array of objects:

  String[] words = {"Mary", "had", "a", "little", "lamb"};
  Stream<String> wordStream = Stream.of(words);
  

3) Using the stream method of a collection:

  List<String> wordList = new ArrayList<>();
Stream<String> wordStream = wordList.stream();

ch19/r05

a) List<Integer> result = stream.collect(Collectors.toList());

b) Integer[] result = stream.toArray(Integer[]::new);

c) Use b) above and then process the wrapper array converting it to an array of primitives.

ch19/r06

a) Stream<String> to Stream<Double>

  Stream<Double> dblValues = strValues.stream()
    .mapToDouble(s -> Double.parseToDouble(s));

a) Stream<Double> to Stream<String>

  Stream<String> strValues = dblValues.stream()
    .map(s -> Double.toString(s));
ch19/r07

1. lambda body is a single expression

  // returns names larger than 10 characters
  name -> name.length() < 10

2. lambda body uses a defined method call

  // returns names larger than 10 characters
  name -> bigNames(name)

3. lambda body uses a functional block

  // returns names larger than 10 characters
  name ->
  {
     int len = name.length();
     if (len > 10)  return name;
  }
ch19/r08

Three different ways of printing when the optional value is present and not printing when it is not are as follows.

1. System.out.print(optResults.orElse(""));
2. optResults.ifPresent(v -> System.out.print(v));
3. if (optResults.isPresent())
   {
      System.out.print(optResults.get()):
   }
  

Options 1 and 3 above can be configured to print "None" if the optional value is not present.

ch19/r09

1. Create an IntStream from individual integers or from an array.

  IntStream stream = IntStream.of(3, 1, 4, 1, 5, 9);
int[] values = . . .;
stream = IntStream.of(values);

2. Create an IntStream from a range of consecutive integers.

  IntStream stream = IntStream.range(a, b); 

3. Create an IntStream from a random range of integers: inclusive of loBound and exclusive of hiBound.

  Random generator = new Random();
IntStream dieTosses = generator.ints(loBound, hiBound);

4. Create an IntStream from a String objects Unicode points.

  IntStream codePoints = str.codePoints(); 

5. Create an IntStream from another stream by applying some function.

  IntStream lengths = words.mapToInt(w -> w.length()); 

Options 1, 3, and 5 can be used to create a DoubleStream with the corresponding methods used.

ch19/r10

a) Using the mapToInt approach:

int maxOfLengths = words
.mapToInt(w -> w.length())
.max();

b) Using the stream.max approach on a non-primitive stream:

final Comparator<String> comp = (s1, s2) -> Integer.compare( s1.length(), s2.length());
int maxOfLengths = words
  .max(comp);
The advantage of the first approach is that it does not need a comparator for primitive type streams.
ch19/r11
findFirst
findAny
min
max
count
toArray
collect
forEach
allMatch
anyMatch
noneMatch
  
ch19/r12
averagingDouble
averagingInt
averagingLong
counting
groupingBy
joining
maxBy
minBy
summingDouble summingInt
summingLong
toList
toSet
ch19/r13

The intent of the .orElse values is to provide a meaningful value when the compution cannot be completed. For example, the average().orElse(0) provides the value 0 when the average cannot be computed beacause there are no values to average and the result would require dividing by zero. Both min().orElse(Double.MAX_VALUE) and max().orElse(Double.MIN_VALUE) provide a default value when calculating the minimum and maximum of a set of values.

ch20

ch20/r01

Yes, you can. You have to set the frame's layout (actually the frame's content pane layout) to FlowLayout:

frame.setLayout(new FlowLayout());

Then, you can just add the user interface components, one by one:

frame.add(new JButton("A"));
   frame.add(new JButton("B"));
ch20/r02

A layout manager is an object that arranges components inside a container. The advantage of a layout manager is that the layout works even if the size of the components or the container changes. That can happen because components have different sizes in different look and feel implementations, or simply because the user resizes the container.

ch20/r03

If you place a single button in the CENTER area, it grows to fill the entire center area.

ch20/r04

If you place multiple buttons in the SOUTH area, they are put on top of each other. Only the last one shows up.

ch20/r05

If you omit the second parameter of the add method when adding a component to a container that uses a border layout, then the component is added to the center.

ch20/r06

The second button appears nested (inside) the first button.

ch20/r07

The drawback of the grid layout is that the first and second column have the same size (because each cell gets the same size in a grid layout). It would be nicer if the first column was much narrower, so that there would be more room for the sliders.

Unfortunately, that isn't easy to achieve with the basic layouts. You can use (3,1) grid layout with 3 flow layouts, each of which contains a label and a slider. But then the sliders won't line up. Or you can use a border layout, put one (3,1) grid layout to hold the labels to the West and another grid layout to hold the sliders in the center. That will probably work OK, because labels and sliders have approximately the same height.

The best way to achieve a good layout is to use the GridBagLayout, but that layout manager is quite complex and is not used in this book.

ch20/r08

The GridBagLayout, like the GridLayout, arranges components in a grid of rows and columns. But, in the GridBagLayout the rows and columns do not have to have the same size, a component can span several cells, and components do not have to fill the entire area. All this comes at the cost of increased complexity.

ch20/r09

When creating a check box or radio button, you can specify an icon to use in the constructor:

new JRadioButton("JRadioButton", new ImageIcon("icon.gif"));
   new JCheckBox("JCheckBox", new ImageIcon("icon.gif"));

You cannot set an icon in a JComboBox component.

ch20/r10

Radio buttons are used to select exactly one of a number of options.

Check boxes are used to select any combination of a number of options.

ch20/r11

The button group for radio buttons is responsible for turning the previously selected button off when another button is selected. That ensures that only one radio button from the group is selected at any time. You don't need a button group for check boxes because in a group of check boxes, it is OK to have several check boxes selected.

ch20/r12

The menu bar is the horizontal bar at the top of a window.

A menu is a vertical arrangement of submenus and menu items.

A menu item is an individual item inside a menu. Only menu items generate action events.

ch20/r13

The constructor with no arguments produces a slider with a range of min=0, max=100. Simply replacing the sliders in our program with default sliders would not have worked - there would be no way to specify white (red=green=blue=255). The maximum value (red=green=blue=100) would be a dark gray.

It would have been possible to fix the program by scaling the slider values from the range [0,100] to the range [0,255], but that would have been more work than using the other constructor.

ch20/r14

You construct a vertical slider like this:

JSlider mySlider = new JSlider(SwingConstants.VERTICAL, min, max, value);

You can also use JSlider.VERTICAL because JSlider implements the SwingConstants interface.

ch20/r15

Action events describe one-time changes, such as button clicks. Change events describe continuous changes, such as moving a JSlider. In the case of a JComboBox, the events generated are one-time changes, not continuous changes.

ch20/r16

Use the JList component to show a list of items, with several items visible at the same time.

ch20/r17

The Swing documentation lists the following components:

JButton
JCheckBox
JCheckBoxMenuItem
JColorChooser
JComboBox
JComponent
JDesktopPane
JDialog
JEditorPane
JFileChooser
JFormattedTextField
JFrame
JInternalFrame
JLabel
JLayeredPane
JList
JMenu
JMenuBar
JMenuItem
JOptionPane
JPanel
JPasswordField
JPopupMenu
JProgressBar
JRadioButton
JRadioButtonMenuItem
JRootPane
JScrollBar
JScrollPane
JSeparator
JSlider
JSpinner
JSplitPane
JTabbedPane
JTable
JTextArea
JTextField
JTextPane
JToggleButton
JToolBar
JToolTip
JTree
JViewport
JWindow

Not all of them correspond to visible components, but about 30 of them do.

ch20/r18

The following statistics are valid for Java 6.

Here are the 31 methods of JProgressBar:

addChangeListener(ChangeListener l)
createChangeListener()
fireStateChanged()
getAccessibleContext()
getChangeListeners()
getMaximum()
getMinimum()
getModel()
getOrientation()
getPercentComplete()
getString()
getUI()
getUIClassID()
getValue()
isBorderPainted()
isIndeterminate()
isStringPainted()
paintBorder(Graphics g)
paramString()
removeChangeListener(ChangeListener l)
setBorderPainted(boolean b)
setIndeterminate(boolean newValue)
setMaximum(int n)
setMinimum(int n)
setModel(BoundedRangeModel newModel)
setOrientation(int newOrientation)
setString(String s)
setStringPainted(boolean b)
setUI(ProgressBarUI ui)
setValue(int n)
updateUI()

In addition, JProgressBar inherits 130 methods from JComponent, 57 methods from Container, 150 methods from Component, 10 methods from Object, All together, the class has 378 methods!

ch20/r19

Inheritance is not a requirement for JFrame. By extending the class, however, you can add instance variables and call helper methods you might want to use to create components.

ch20/r20

A label is a display area for a short text string or an image, or both. The text cannot be edited.

A text field holds a single line of editable text. A text area displays multiple lines of editable text.

ch20/r21

The append method is declared in the JTextArea class.

The setText method is declared in the JTextComponent class.

The getGraphics method is declared in the JComponent class.

ch20/r22

JTextArea can hold multiple lines of text. The program shows how the interest accumulates over time. So JTextArea is used in the program to accumulate the results into one text area. An array of labels could be created in the actionListener to display each result in a separate label.

ch21

ch21/r01

Streams handle binary data, accessing sequences of bytes. Readers and writers handle data in text form, accessing sequences of characters.

ch21/r02

The exercise should say PrintWriter, not FileWriter. Most text editors will automatically convert the text using the proper encoding. In Microsoft Word, the software detects the encoding and asks the user to confirm it before opening the file. If a different encoding is specified, the values in the file are interpreted as different characters.

import java.io.PrintWriter;
import java.io.FileNotFoundException;
import java.io.UnsupportedEncodingException;
 
public class EncodingTester
{
   public static void main(String[] args) 
      throws FileNotFoundException, UnsupportedEncodingException
   {
      PrintWriter out = new PrintWriter("output1.txt", "UTF-8");
      out.println("If you write to a file reader, there will be a "
      + "compile-time error because input files don't support output "
      + "operations such as print.\n If you write to a random access "
      + "file that was opened for reading only, there will be an "
      + "exception.");
 
      PrintWriter out2 = new PrintWriter("output2.txt", "UTF-16");
      out2.println("If you write to a file reader, there will be a "
      + "compile-time error because input files don't support output "
      + "operations such as print.\n If you write to a random access "
      + "file that was opened for reading only, there will be an "
      + "exception.");
 
      out.close();
      out2.close();
   }
}
ch21/r03

You need to open a RandomAccessFile to open a file for both reading and writing. For example,

RandomAccessFile f = new RandomAccessFile("bank.dat", "rw");
ch21/r04

If you write to a file reader, there will be a compile-time error because input files don't support output operations such as print.

ch21/r05

If you write to a random access file that was opened for reading only, there will be an exception.

ch21/r06

To break the Caesar cipher, you can try all 25 keys (b...z) to decrypt the message. Look at the decryptions and see which one of them corresponds to English text.

ch21/r07

If you try to save an object to a object stream and the object is not serializable, an exception is thrown.

ch21/r08
java.lang.Boolean
java.lang.Character
java.lang.Double
java.lang.Integer
java.lang.String

java.lang.Throwable and its subclasses, i.e., all exceptions

java.io.File
ch21/r09

If you simply save the entire ArrayList, you do not have to save the number of elements. If you saved a collection manually, you'd first have to write out the length, then all entries. When reading the collection back in, you'd have to read in the length, then allocate sufficient storage, and then read and store all entries. It is much simpler to just write and read the ArrayList and let the serialization mechanism worry about saving and restoring the length and the entries.

ch21/r10

Sequential access forces you to read all bytes in a file in order, starting from the first byte and progressing through the last byte. Once a byte has been read, it cannot be read again, except by closing and reopening the file. With random access, you can repeatedly select any position in the file for reading or writing.

ch21/r11

The file pointer denotes the current position in a random access file for reading and writing. You move it with the seek method of the RandomAccessFile class. You get the current position with the getFilePointer method. The position is the number of bytes from the beginning of the file, as a long integer, because files can be longer than 2GB (the longest length representable with an int).

ch21/r12
f.seek(0);
f.seek(f.length() - 1);
f.seek(f.length() / 2);
ch21/r13

It is legal to move the file pointer past the end of the file. If you write to that location, the file will be enlarged. If you read from that location, an exception is thrown.

ch21/r14

You can't move the file pointer on System.in. It is not a RandomAccessFile, therefore a call to the seek method is a compile-time error.

ch21/r15

Passing an absolute path to the resolve method returns the passed-in path.

ch21/r16

The following example shows usage of relativize with both files and directories:

Path path01 = Paths.get("Foo.txt");
Path path02 = Paths.get("Bar.txt");
Path path03 = Paths.get("/Java/JavaTemp/Foo.txt");
Path path04 = Paths.get("/Java/2015");

Path path01_to_path02 = path01.relativize(path02);
System.out.println(path01_to_path02);

Path path02_to_path01 = path02.relativize(path01);
System.out.println(path02_to_path01);

Path path03_to_path04 = path03.relativize(path04);
System.out.println(path03_to_path04);

Path path04_to_path03 = path04.relativize(path03);
System.out.println(path04_to_path03);
        

Would result in the following:

..\Bar.txt
..\Foo.txt
..\..\2015
..\JavaTemp\Foo.txt
ch21/r17

Depth first order means that it will traverse downward through the directories until it reaches the bottom of the tree. From there it will handle all siblings at each level as it moves through the tree in a recursive nature. Directory children are listed after their parents. Files will be listed before directories. The listing of each directory will be displayed alphabetically.

ch22

ch22/r01

The reason is that the code calls run on the GreetingRunnable objects so they run in sequence in the same thread. It should create a thread for each and call start on the threads.

ch22/r02

Yes, the thread scheduler may just switch to thread B while thread A is sleeping. Then thread B may also go to sleep, and the scheduler may find both thread A and B sleeping at the same time.

Yes, for example, thread A can be printing to the console while the thread scheduler decides to give the time slice to thread B. Thread B gets its turn and resumes working on whatever it was doing.

ch22/r03

There is one MAIN thread in the program plus other threads for the GUI. For example, when one does not implement the EXIT_ON_CLOSE feature, the program will not end after a user closes the GUI window.

ch22/r04

The stop method for stopping a thread is deprecated because a thread may have occupied some resources, such as database connections. If we just stop the thread without releasing the resources, the database will eventually run out of connections for others that have work to do.

A thread can be terminated by calling threadName.interrupt().

ch22/r05

Suppose a long computation is being carried out in a thread, the computation is not yet completed, and the user is no longer interested in the result and wishes to terminate the computation. Then it is time to terminate the thread.

ch22/r06

The problem is that the threads cannot be terminated by interrupting them.

ch22/r07

A race condition occurs if the effect of multiple threads on shared data depends on the order in which the threads are scheduled. Race conditions can be avoided using lock objects to control the threads that attempt to manipulate a shared resource.

ch22/r08

If the remove method goes to sleep after it removes an element but before it updates currentSize, the add method will use the wrong value when it increments currentSize.

Similarly, if the remove method goes to sleep after it removes an element but before it updates currentSize, the growBufferIfNecessary method may increase the buffer size and copy the removed element to the new buffer.

ch22/r09

If push goes to sleep before setting first to the new node, an attempt to pop the stack may return an error (if first is null) or the wrong value.

If pop goes to sleep before setting first to first.next, push could set the new node to link to the element that was to be removed by pop. When pop wakes, it will not remove the desired element, but rather set it to first, thereby eliminating the new first created by push.

ch22/r10

If the remove method goes to sleep after it removes an element but before it updates head, the growBufferIfNecessary method will set head to the wrong value.

Similarly, if the remove method goes to sleep after it removes an element but before it updates currentSize, the growBufferIfNecessary method may increase the buffer size, copy the removed element to the new buffer, and set tail to the wrong value.

21.11

A deadlock occurs if no thread can proceed because each thread is waiting for another thread to do some work first.

One important way to avoid deadlocks is to call signalAll/notifyAll after a state change that may allow waiting threads to proceed. But there are other potental causes for deadlocks that are not so easily remedied.

ch22/r11

The sleep method puts the current thread to sleep for a given number of milliseconds, after which it wakes up. The await method blocks the thread and allows another thread to acquire the object lock. In other words, sleep will sleep for a specified period of time; a waiting thread is blocked until another thread calls signalAll or signal on the condition object for which the thread is waiting.

ch22/r12

It will wait forever.

ch22/r13

There are two threads: the animation thread and the GUI thread. They share a resource, namely the array of values. But the animation thread is almost 100% certain to be sleeping when the GUI thread paints the graph. If for some reason, the display was repainted while the animation thread was modifying it, then it would display the wrong image. Thus, no synchronization is needed.

ch22/r14

The array to be sorted is filled automatically with random numbers. There is no need for user input in the animation.

ch23

ch23/r01

Answers will vary. Some IP addresses may be dynamically assigned by the Internet provider.

ch23/r02

Yes. It needs the computer's IP address (or domain name) and the port number used by the desired application.

ch23/r03

A port number is an integer between 0 and 65,535. It indicates the program that should receive data coming to the computer over TCP. Yes, a computer can receive data on different ports.

ch23/r04

A server is a provider of services. A client is a consumer of services. Usually, multiple clients can connect to a server at one time.

ch23/r05

A socket is an object that encapsulates a TCP/IP connection. A Socket object is used by client applications to connect to the server for services. A ServerSocket object is used by server applications to listen for client connections.

ch23/r06

The socket constrcutor throws an UnknownHostExeption if it can not find the host.

ch23/r07

java.net.ConnectException will be thrown. The exception message is Connection refused: connect.

ch23/r08

It uses the address of the computer to which you want to connect.

ch23/r09

The purpose of the accept method is to wait and listen for a new client socket.

ch23/r10

You will use an InputStream obtained from the Socket.

ch23/r11

Because people usually want to communicate with the server by sending and receiving text. Then, turning the streams into scanners and writers is preferable.

ch23/r12

Print writers buffer their outputs. They will not send the characters in the buffer until the buffer is full. That is why we sometimes needs to flush the output stream or writer in order make sure every character is send to the server.

ch23/r13

HTTP, which stands for Hypertext Transfer Protocol, is the protocol that defines communication between web browsers and web servers.

HTML, which stands for Hypertext Markup Language, is a document format (with tags such as <h1> or <ol>) that describes the structure of a document, including headings, bulleted lists, images, hyperlinks, and so on.

ch23/r14

(user input is in bold)

~$ telnet horstmann.com 80
Trying 67.220.118.65...
Connected to horstmann.com.
Escape character is '^]'.
HEAD / HTTP/1.1
Host: horstmann.com
Blank line
HTTP/1.1 200 OK
Date: Fri, 06 Jan 2012 14:54:13 GMT
Server: Apache/2.2.22 (Unix) mod_ssl/2.2.22 OpenSSL/0.9.7a 
mod_auth_passthrough/2.1 mod_bwlimited/1.4 FrontPage/5.0.2.2635 
mod_fcgid/2.3.5 Sun-ONE-ASP/4.0.3
Last-Modified: Thu, 08 Dec 2011 06:19:43 GMT
ETag: "305e572-1944-4b38ea7747dc0"
Accept-Ranges: bytes
Content-Length: 6468
Content-Type: text/html
 
Connection closed by foreign host.
~$
ch23/r15
~$ openssl s_client -connect pop.gmail.com:995
CONNECTED(00000003)
depth=1 C = US, O = Google Inc, CN = Google Internet Authority
verify error:num=20:unable to get local issuer certificate
verify return:0
---
Certificate chain
  0 s:/C=US/ST=California/L=Mountain View/O=Google Inc/CN=pop.gmail.com
    i:/C=US/O=Google Inc/CN=Google Internet Authority
  1 s:/C=US/O=Google Inc/CN=Google Internet Authority
    i:/C=US/O=Equifax/OU=Equifax Secure Certificate Authority
---
Server certificate
-----BEGIN CERTIFICATE-----
MIIDWjCCAsOgAwIBAgIKaNGwUQADAAAirzANBgkqhkiG9w0BAQUFADBGMQswCQYD
VQQGEwJVUzETMBEGA1UEChMKR29vZ2xlIEluYzEiMCAGA1UEAxMZR29vZ2xlIElu
dGVybmV0IEF1dGhvcml0eTAeFw0xMTAyMTYwNDQwMzdaFw0xMjAyMTYwNDUwMzda
MGcxCzAJBgNVBAYTAlVTMRMwEQYDVQQIEwpDYWxpZm9ybmlhMRYwFAYDVQQHEw1N
b3VudGFpbiBWaWV3MRMwEQYDVQQKEwpHb29nbGUgSW5jMRYwFAYDVQQDEw1wb3Au
Z22haWwuY29tMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCc8H+gCR0/95Tb
Lkj7jdj0oXmfGzsSswdSjo6yWdcHpjv6cbaakHakclxBs47M8Gs3fJxuNqVMpt2Q
YorJuoBuVZjM59/rIeJwmOwSlzf1POxpEFUvm1ASAeBnBheBt0Fv+BCfI8DjZKgn
SvHCqQJfNgxpJBXOLbFVjBsPqF8w6wIDAQABo4IBLDCCASgwHQYDVR0OBBYEFHzY
GJFnJ+gmONoIX6cyTAEl9ePYMB8GA1UdIwQYMBaAFL/AMOv1QxE+Z7qekfv8atrj
axIkMFsGA1UdHwRUMFIwUKBOoEyGSmh0dHA6Ly93d3cuZ3N0YXRpYy5jb20vR29v
Z2xlSW50ZXJuZXRBdXRob3JpdHkvR29vZ2xlSW50ZXJuZXRBdXRob3JpdHkuY3Js
MGYGCCsGAQUFBwEBBFowWDBWBggrBgEFBQcwAoZKaHR0cDovL3d3dy5nc3RhdGlj
LmNvbS9Hb29nbGVJbnRlcm5ldEF1dGhvcml0eS9Hb29nbGVJbnRlcm5ldEF1dGhv
cml0eS5jcnQwIQYJKwYBBAGCNxQCBBQeEgBXAGUAYgBTAGUAcgB2AGUAcjANBgkq
hkiG9w0BAQUFAAOBgQB0GTFAoMNxCFJ3aVMzvrZgCD9hG2Ee3Sx5GMQ0yDjcFvzS
ZIci9Gr18HMVBusIuFLw8TvBD7PEXtZLhh6hbj+Xdg9CIqlIjdqJFRixJU06xqKH
akIhNBDxy5ky3VugqlGdysbMjo/aXCFdl42GproXdUPH24Erljur885LklMk/g==
-----END CERTIFICATE-----
subject=/C=US/ST=California/L=Mountain View/O=Google Inc/CN=pop.gmail.com
issuer=/C=US/O=Google Inc/CN=Google Internet Authority
---
No client certificate CA names sent
---
SSL handshake has read 1738 bytes and written 347 bytes
---
New, TLSv1/SSLv3, Cipher is RC4-SHA
Server public key is 1024 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
     Protocol  : SSLv3
     Cipher    : RC4-SHA
     Session-ID: 
E807CC6FD8596BE65B9F89276AA0826CAF767013986609117D7FB569D3A41892
     Session-ID-ctx:
     Master-Key: 
EF204E4804C225E5CEB46D1A168FF3812DAB67144C4F9A1963F830C63EEEA245B6E15872DEE22A98A3C0DEF74491B22B
     Key-Arg   : None
     PSK identity: None
     PSK identity hint: None
     Start Time: 1325862776
     Timeout   : 7200 (sec)
     Verify return code: 20 (unable to get local issuer certificate)
---
+OK Gpop ready for requests from 108.81.230.128 f5pf97180872pbc.16
user xxx.xxx@xxx.xxx
+OK send PASS
pass xxxxxxx
+OK Welcome.
list
+OK 286 messages (6055394 bytes)
1 10738
2 3787
3 10578
4 3371
5 2677
6 5064
...
278 18139
279 6694
280 6118
281 4473
282 7932
283 2918
284 7725
285 34395
286 101699
.
retr 284
+OK message follows
Delivered-To: xxx.xxx@xxx.xxx
Received: by 10.229.142.136 with SMTP id q8cs472qcu;
         Fri, 19 Nov 2010 19:23:00 -0800 (PST)
Received: by 10.231.169.206 with SMTP id a14mr1065068ibz.13.1290223370535;
         Fri, 19 Nov 2010 19:22:50 -0800 (PST)
Received: by Domino with HTTP; Tue, 8 Jun 2010 23:01:48 -0700
Message-ID: <EE4E633C3CB25FD8AFFBE30579D5FCFC@sjsu.edu>
X-Notes-Message-ID: <DE3532AB794549BF8699DD5C5F91CA0D@ad.science.sjsu.edu>
MIME-Version: 1.0
Date: Tue, 8 Jun 2010 23:01:48 -0700
From: xxx.xxx@xxx.xxxx
To: xxx.xxx@xxx.xxx
Reply-To: xxx.xxx@xxx.xxx
Subject: RE: sharing question bank.
Content-type: multipart/alternative;
 Boundary="0__=07BBFD72DF8227CA8f9e8a93df938690918c07BBFD72DF8227CA"
Content-Disposition: inline
 
 
 
--0__=07BBFD72DF8227CA8f9e8a93df938690918c07BBFD72DF8227CA
Content-type: text/plain; charset=US-ASCII
 
message body
 
--0__=07BBFD72DF8227CA8f9e8a93df938690918c07BBFD72DF8227CA--
.
quit
+OK Farewell.
read:errno=0
ch23/r16

One can use high level APIs such as the URLConnection and HttpURLConnection classes.

ch23/r17

A URL instance represents a Uniform Resource Locator, a pointer to a "resource" on the World Wide Web.

A URLConnection instance can be used both to read from and to write to the resource referenced by the URL.

ch23/r18

A URL, or Uniform Resource Locator, is a pointer to an information resource (such as a web page or an image) on the World Wide Web.

You create a URL object from a URL string, such as new URL("http://horstmann.com/"). To connect to the URL, use the openConnection method. That yields a URLConnection object. Call its getInputStream method to get an InputStream.

ch24

ch24/r01
CREATE TABLE Person
(
  Name VARCHAR(30),
  Driver_License_No CHAR(16),
  Address VARCHAR(100)
)

CREATE TABLE Car
(
  Vehicle_ID INTEGER,
  Owner_License CHAR(16),
  Manufacturer VARCHAR(20),
  Type VARCHAR(10),
  Year INTEGER
)
ch24/r02
CREATE TABLE LibraryBook
(
   Library_ID INTEGER,
   ISBN CHAR(13),
   Patron_ID INTEGER
)

CREATE TABLE BookData
(
   ISBN CHAR(13),
   Author VARCHAR(40),
   Title VARCHAR(40)
)

CREATE TABLE Patron
(
   Patron_ID INTEGER,
   Name VARCHAR(40),
   Street VARCHAR(40),
   City VARCHAR(30),
   State CHAR(2),
   Zip CHAR(5)
)
ch24/r03
CREATE TABLE Coin
(
  Name VARCHAR(20),
  Value INTEGER
)

CREATE TABLE Purse
(
  Owner_Name VARCHAR(30),
  Purse_ID INTEGER
)

CREATE TABLE Coin_Sets
(
  Purse_ID INTEGER,
  Coin_Name VARCHAR(20),
  Quantity INTEGER
)
ch24/r04
CREATE TABLE Student
(
  Student_ID INTEGER,
  Name VARCHAR(30)
)

CREATE TABLE Class
(
   Class_ID INTEGER,
   Classroom_ID INTEGER,
   Professor_ID INTEGER,
   Title VARCHAR(30)
)

CREATE TABLE Professor
(
   Professor_ID INTEGER,
   Name VARCHAR(30)
)

CREATE TABLE Classroom
(
   Classroom_ID INTEGER,
   Location VARCHAR(20)
)

CREATE TABLE Enrollment
(
   Student_ID INTEGER,
   Class_ID INTEGER
)
ch24/r05
CREATE TABLE Book
(
   ISBN INTEGER,
   Author VARCHAR(30),
   Title VARCHAR(50),
)

INSERT INTO Book VALUES
(
  123456789, 'Cay Horstmann', 'Big Java'
)

INSERT INTO Book VALUES
(
  234523897, 'Philip M. Lewis', 'Database and Transaction Processing'
)

INSERT INTO Book VALUES
(
  135754523, 'Mark Birbeck', 'Professional XML 2nd Edition'
)

INSERT INTO Book VALUES
(
  458734515, 'Damon Hougland', 'Core JSP'
)
ch24/r06
CREATE TABLE Car
(
  Car_ID INTEGER,  
  Manufacturer VARCHAR(20),
  Model VARCHAR(10),
  Year INTEGER
)

INSERT INTO Car VALUES
(
  145460985, 'Honda', 'Civic', 1997
)

INSERT INTO Car VALUES
(
  324052349, 'Ford', 'Ranger', 1987
)
ch24/r07
SELECT Description FROM Product;
ch24/r08
SELECT Name 
FROM Customer
WHERE State = 'CA'
ch24/r09
SELECT Name
FROM Customer
WHERE State = 'CA' OR State = 'NV'
ch24/r10
SELECT Name
FROM Customer
WHERE State <> 'HI'
ch24/r11
SELECT Name
   FROM Customer, Invoice
   WHERE Customer.Customer_Number = Invoice.Customer_Number
      AND Invoice.Payment = 0
ch24/r12
SELECT Product.Description
   FROM Customer, Product, Invoice, LineItem
   WHERE Customer.Customer_Number = Invoice.Customer_Number 
     AND Invoice.Invoice_Number = LineItem.Invoice_Number
     AND LineItem.Product_Code = Product.Product_Code
     AND Customer.State = 'CA'
ch24/r13
SELECT Product.Description, LineItem.Quantity
   FROM Product, LineItem
   WHERE LineItem.Invoice_Number = 11731
      AND LineItem.Product_Code = Product.Product_Code
ch24/r14
SELECT SUM(LineItem.Quantity)
   FROM LineItem
   WHERE LineItem.Invoice_Number = 11731
ch24/r15
SELECT SUM(Product.Price * LineItem.Quantity)
   FROM Product, LineItem
   WHERE LineItem.Invoice_Number = 11731
      AND LineItem.Product_Code = Product.Product_Code
ch24/r16
UPDATE Product
   SET Price = Price * 1.10
ch24/r17
DELETE FROM Customer
   WHERE State = 'CA'
ch24/r18

Oracle

JDBC driver: oracle.jdbCustomer.driver.OracleDriver
URL: jdbc:oracle:oci8:@

MySQL

JDB driver: com.mysql.jdbc.Driver
URL: jdbc:mysql://localhost/
ch24/r19

A typical answer is

/home/username/jdk1.7.0_01/db/lib/derby.jar

or

c:\Program Files\java\jdk1.7.0_01\db\lib\derby.jar
ch24/r20
Column 1 Column 2
a 3
b 4
c 5
d 2
e 1
ch24/r21

The Connection object makes a connection to the database and has a method that creates a Statement object. One uses statements to execute SQL commands.

ch24/r22

SELECT yields a result set, INSERT and UPDATE yield an update count, CREATE TABLE and DROP TABLE yield neither.

ch24/r23

1. An iterator initially points to the first element of the collection. The result set initially points before the first element, and you must advance it once in order to fetch the first element.

2. Conceptually, iteration is composed of three operations: test, fetch, and advance. The java.util.Iterator groups the fetch and advance operations into a single method (next). The ResultSet groups the test and advance operations into a single method (also called next).

ch25

ch25/r01
HTML:  "<li>" is same as "<LI>"
 XML:   "<LI>" is not the same as "<li>"     // case sensitive
 
 HTML:  <img src="hamster.jpeg">
 XML:   <img src="hamster.jpeg"/>      // must provide end-tag
 
 HTML:  <img src="hamster.jpeg" width=400 height=300>
 XML:   <img src="hamster.jpeg" width="400" height="300"/> // quote attribute values
ch25/r02
<bankaccount>
     <accountnumber>1111</accountnumber>
     <interestrate>5</interestrate>
     <balance>15356</balance>
</bankaccount>
ch25/r03
                                 <bankaccount>
                              /        |        \
                            /          |          \
                          /            |            \
                 <accountnumber>  <interestrate>  <balance>
                       /               |               \
                     1111              5              15356
ch25/r04

The exercise should refer to Figure 5.

<sentence>
    <noun-phrase>
        <article>the</article>
        <adjective-list>
            <adjective>hungry</adjective>
        </adjective-list>
        <noun>hamster</noun>
    </noun-phrase>
    <verb>eats</verb>
    <noun-phrase>
        <article>a</article>
        <adjective-list>
            <adjective>quick</adjective>
            <adjective-list>
               <adjective>brown</adjective>
            </adjective-list>
        </adjective-list>
        <noun>fox</noun>
    </noun-phrase>
</sentence>
ch25/r05
<book>
    <authorname>Cay Horstmann</authorname>
    <title>Big Java, Late Objects</title>
    <year>2013</year>
</book>
ch25/r06
<book>
    <authorname>Cay Horstmann</authorname>
    <title>Big Java</title>
    <year>2015</year>
    <language>EN</language>
</book>

We choose to represent the language as an element because it is not used to interpret the element content. If the software actually translated the title into another language, then an attribute might be more appropriate, but library and shopping software will generally not care about the book's language - it will simply present the language as an informational item to the user, which is no different than the title and author information.

ch25/r07

Mixed content means an element can contain text, sub-elements, or both.

Mixed content makes it more difficult to write a strict DTD because you can't specify any rules for the elements that are mixed with the text. For example, you cannot control the order in which elements appear.

ch25/r08
<purse>
    <coins>
        <coin>
            <value>0.25</value>
            <name>quarter</name>
        </coin>
        <quantity>3</quantity>
    </coins>
    <coins>
        <coin>
            <value>0.10</value>
            <name>dime</name>
        </coin>
        <quantity>1</quantity>
    </coins>
    <coins>
        <coin>
            <value>0.05</value>
            <name>nickel</name>
        </coin>
        <quantity>2</quantity>
    </coins>
</purse>
ch25/r09

Because the paint program does not know why one arranged the graphical elements in a certain way, it cannot update the arrangement in a logical way when the image changes.

ch25/r10

a. 0.5

b. quarter

c. en

d. value

e. 2

f. 1

ch25/r11

a. /purse/coin[1]/value

b. count(/purse/coin)

c. name(/purse/coin[1]/*[1])

d. name(/purse/coin[1]/name/@*[1])

e. /purse/coin[2]/name/@lang

ch25/r12

The output of p.getDescription() can contain characters that are invalid XML.

If a description contains a < sign, the XML parser will interpret it as the start of a tag. If it contains an & symbol, the XML parser will interpret it as the start of an entity reference.

In this case, the remedy is to replace all & with &amp; and all < with &lt;.

If you generated code inside attributes, you would also have to escape " symbols. Knowing what to replace where requires a detailed understanding of the XML specification. It is much better to use an XML library to generate XML.

ch25/r13
<!DOCTYPE bankaccounts [
 
<!ELEMENT bankaccounts (bankaccount*)>
<!ELEMENT bankaccount (accountnumber, interestrate, balance)>
<!ELEMENT accountnumber (#PCDATA)>
<!ELEMENT interestrate (#PCDATA)>
<!ELEMENT balance (#PCDATA)>
 
]>
ch25/r14
<!DOCTYPE patron [
    
<!ELEMENT patron (name, phonenumber, book*)>
<!ELEMENT name (#PCDATA)>
<!ELEMENT phonenumber (#PCDATA)>
<!ELEMENT book (bid, author, title)>
<!ELEMENT bid (#PCDATA)>
<!ELEMENT author (#PCDATA)>
<!ELEMENT title (#PCDATA)>
 
]>
ch25/r15
<!DOCTYPE productlist [
 
<!ELEMENT productlist (product*)>
<!ELEMENT product (name, price, score)>
<!ELEMENT name (#PCDATA)>
<!ELEMENT price (#PCDATA)>
<!ELEMENT score (#PCDATA)>
<!ATTLIST price currency CDATA #IMPLIED>
 
]>
ch25/r16
<!DOCTYPE invoice [
    
<!ELEMENT invoice (number, address, items)>
<!ELEMENT number (#PCDATA)>
<!ELEMENT address (name, company, street, city, state, zip)>
<!ELEMENT name (#PCDATA)>
<!ELEMENT company (#PCDATA)>
<!ELEMENT street (#PCDATA)>
<!ELEMENT city (#PCDATA)>
<!ELEMENT state (#PCDATA)>
<!ELEMENT zip (#PCDATA)>
 
<!ELEMENT items (item*)>
<!ELEMENT item (product, quantity)>
<!ELEMENT product (description, price)>
<!ELEMENT description (#PCDATA)>
<!ELEMENT price (#PCDATA)>
<!ELEMENT quantity (#PCDATA)>
 
]>
ch25/r17
<!DOCTYPE sentence [
 
<!ELEMENT sentence (noun-phrase, verb, noun-phrase)>
<!ELEMENT noun-phrase (article, adjective-list, noun)>
<!ELEMENT article (#PCDATA)>
<!ELEMENT adjective-list (adjective, adjective-list?) >
<!ELEMENT adjective (#PCDATA)>
<!ELEMENT noun (#PCDATA)>
<!ELEMENT verb (#PCDATA)>
 
]>
ch25/r18
<!DOCTYPE expression [
    
<!ELEMENT expression (term, (expression, additive-operator, term)?)>
<!ELEMENT additive-operator (#PCDATA)>
<!ELEMENT term (factor, (term, multiplicative-operator, factor)?)>
<!ELEMENT multiplicative-operator (#PCDATA)>
<!ELEMENT factor (integer | (lparen, expression, rparen))>
<!ELEMENT lparen (#PCDATA)>
<!ELEMENT rparen (#PCDATA)>
<!ELEMENT integer (minus?, digits)>
<!ELEMENT minus (#PCDATA)>
<!ELEMENT digits (digit+)>
<!ELEMENT digit (#PCDATA)>
 
]>

ch26

ch26/r01

The language is HTML.

Images:

<img class="sideimage" alt="Photo of Cay Horstmann" src="images/cay-rowing.gif" />
<img alt="" src="images/violet.jpg" style="border: 0px solid ; width: 73px; height: 76px;" title="" />
<img alt="Zork 1 Logo" height="78" src="images/zork1.gif" width="99" />

Links: (there are many)

An email link:<a href="mailto:cay@horstmann.com">cay@horstmann.com</a>

A link to a file: <a href="caypubkey.txt">PGP Key</a>

A link to another site: <a href="http://www.uni-kiel.de/">Christian-Albrechts-Universit&auml;t</a>

<a href="http://www.kiel.de/">Kiel</a>
<a href="http://www.syr.edu">Syracuse University</a>
<a href="http://www.umich.edu">University of Michigan</a

Bullets: (there are several like this list)

<ul>
  <li><a href="http://www.java.net/blogs/cayhorstmann/">My Java blog</a></li>
  <li><a href="https://plus.google.com/117406678785944293188/posts">My Google+ page</a></li>
  <li><a href="http://www.sjsu.edu/people/cay.horstmann">My SJSU course   page</a></li>
  <li><a href="quotes.html">Memorable quotes</a></li>
  <li><a href="resume.html">My resume</a></li>
  <li>Fellow Horstmanns who are interested in the family genealogy may want to turn to <a href="http://www.family-horstmann.net">Bernhard Horstmann's site</a></li>
</ul>

Input elements: none

ch26/r02

The user data is after the equal signs in the last line (e.g., jqpublic, secret). login=log%20in means the value generated by a mouse press on the submit button named login that has the label "Log in".

ch26/r03

A JSF page contains HTML and JSF tags.

The JSF container is server-side software that converts a JSF page to an HTML page, replacing all JSF tags with text and HTML tags.

ch26/r04

A bean is a Java class with a default constructor and getter/setter methods that allow access to its properties.

ch26/r05

A bean property is a value of a bean that can be accessed through getter and setter methods.

ch26/r06

Yes, because it allow users to get and set its properties, and it has a default constructor.

ch26/r07

To separate the presentation (HTML) from the business logic (Java computation).

ch26/r08

To see the distinction, consider an expression variable.feature. In Java, this denotes the instance variable named feature. In a JSF variable, this causes a method getFeature or setFeature to be called.

ch26/r09

A bean is constructed when it is called in a value expression. Yes, different users accessing a JSF application will have their own instance of the bean associated with their browser.

ch26/r10

The submit button of the login page should invoke a method that returns an outcome string. The method should return one string (such as "login_ok") if the user was properly authenticated and a different string (such as "login_error") otherwise. The faces-config.xml file should contain navigation rules for each of these outcomes.

ch26/r11
Component JSF Tag Swing Equivalent
Text Field h:inputText JTextField
Password Field h:inputSecret JPasswordField
Text Area h:inputTextArea JTextArea
Radio Button Group h:selectOneRadio JRadioButton, used with a ButtonGroup
Checkbox h:selectOneCheckbox JCheckBox
Checkbox Group h:selectManyCheckbox Use multiple JCheckBox objects
Menu h:selectOneMenu h:selectManyMenu JList
Image h:graphicImage Image (BufferedImage or VolatileImage)
Submit Button h:commandButton JButton
ch26/r12

In a client-server application, the business logic resides on the client machine. In a three-tier application, the business logic resides on the web server.