review-jc-8

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.