Solution Manual for Data Structures and Algorithms in Java 1st Edition, Peter Drake

Chapter 2 Exercises Solutions

 

• int is not a polymorphic type.  int has no methods because it is a primitive type, but it’s operators which could be considered the equivalent to methods consistently perform the same actions no matter the variable that holds the int. The fact that int is a primitive type infers that it does not have such functionality as polymorphism.

 

Interger.parseInt(“25”);

 

• Because this can only be accessed in nonstatic methods, there can never be an instance where we have access to the reference this when the reference is null.  Therefore the assertion is never needed.

 

• The method invocation  roll() will definitely affect the state of d2 if d1==d2 since this implies that d1 and d2 reference the same instance of Die. If d1 != d2, the method invocation will be guaranteed not to affect d2.

 

• Because any class can override the equals() method and implement it anyway it wishes, it is impossible to guarantee that equals() will return true when objects are equal in the sense of ==. However, since the references are to the same instances, comparing any part of the object will always produce equalities. Because of this, when objects are equal in the == sense, we can assume the equals() method will return true. The same is not true for the reverse. It is possible and quite common to have two separate instances of the same class contain equivalent information.

 

• It is definitely true that foo == bar.  It is possibly (very very likely) true that foo.equals(bar) true.

 

• Invoking the equals() method calls the Object class’s equals() method which simply compares the object references and therefore cannot be used to verify if each of the array cells is equal.

 

• It is more efficient because when the condition is true, it avoids the comparison operations that it would otherwise have to do on line 12-18.

 

public boolean equals(Object that) {

if(this == that) {

return true;

}

if(that == null) {

return false;

}

if(getClass() != that.getClass()) {

return false;

}

ComplexNumber thatComplexNumber = (ComplexNumber)that;

return imaginaryPart == that.imaginaryPart

&& realPart == that.realPart;

}

 

2.10

 

2.11

• This can be stored in a two-dimensional array where the second dimension is dynamically allocated where the first row allocation is the first dimensions length minus one and each subsequent row has one less cell than the previous row.

 

• Three

 

• This statement is legal because objects can reference arrays. This statement would allocate 10 cells for reference to objects which in this case point to int arrays.

 

• The simple equals() and toString() would be invoke the methods from the object method which simply equate or print out the top level reference respectively. With the deepEquals() and deepToString(), each cell at each dimension of the array are compared.

 

 

 

 

• This does violate encapsulation because it allows direct access to local information that should not be modified outside the scope of the class.

 

/** Play until someone wins. */

public void play() {

boolean player = HORIZONTAL;

while (true) {

System.out.println(“n” + this);

if (player == HORIZONTAL) {

System.out.println(“Horizontal to play”);

} else {

System.out.println(“Vertical to play”);

}

if (!(hasLegalMoveFor(player))) {

System.out.println(“No legal moves — you lose!”);

return;

}

int row = -1;

int column = -1;

boolean validPlace = false;

while(!validPlace) {

System.out.print(“Row: “);

row = INPUT.nextInt();

System.out.print(“Column: “);

column = INPUT.nextInt();

validPlace = validatePlace(row, column, player);

if (!validPlace) {

System.out.println(“Not a legal move — try again”);

}

}

playAt(row, column, player);

player = !player;

}

}

 

/** Make sure the domino placement is valid **/

public boolean validatePlace(int row, int column, boolean player) {

if(row < 0 || row > 7 || column < 0 || column > 7) {

return false;

}

if(player == HORIZONTAL && column > 6) {

return false;

}

if(player != HORIZONTAL && row > 6) {

return false;

}

if(squares

[column] == true) {

return false;

}

if (player == HORIZONTAL && squares

[column + 1] == true) {

return false;

}

if (player != HORIZONTAL && squares

[column] == true) {

return false;

}

return true;

}

 

2.19

 

/** The game of Domineering. */

public class Domineering {

 

/** For reading from the console. */

public static final java.util.Scanner INPUT

= new java.util.Scanner(System.in);

 

/** The player who plays their dominoes horizontally. */

public static final boolean HORIZONTAL = false;

 

/** The player who plays their dominoes vertically. */

public static final boolean VERTICAL = true;

 

/** Array of board squares, true if occupied. */

private boolean[][] squares;

 

/** The dimension of the board. */

private int size;

 

/** The board is initially empty. */

public Domineering(int size) {

this.size = size;

squares = new boolean[size][size];

// Java initializes all array elements to false

}

 

/**

* Return true if there is a legal move for the specified player.

*/

public boolean hasLegalMoveFor(boolean player) {

int rowOffset = 0;

int columnOffset = 0;

if (player == HORIZONTAL) {

columnOffset = 1;

} else {

rowOffset = 1;

}

for (int row = 0; row < (size – rowOffset); row++) {

for (int column = 0; column < (size – columnOffset); column++) {

if (!(squares

[column]

|| squares

[column + columnOffset])) {

return true;

}

}

}

return false;

}

 

/** Play until someone wins. */

public void play() {

boolean player = HORIZONTAL;

while (true) {

System.out.println(“n” + this);

if (player == HORIZONTAL) {

System.out.println(“Horizontal to play”);

} else {

System.out.println(“Vertical to play”);

}

if (!(hasLegalMoveFor(player))) {

System.out.println(“No legal moves — you lose!”);

return;

}

System.out.print(“Row: “);

int row = INPUT.nextInt();

System.out.print(“Column: “);

int column = INPUT.nextInt();

playAt(row, column, player);

player = !player;

}

}

 

/**

* Play a domino with its upper left corner at row, column.

*/

public void playAt(int row, int column, boolean player) {

squares

[column] = true;

if (player == HORIZONTAL) {

squares

[column + 1] = true;

} else {

squares

[column] = true;

}

}

 

public String toString() {

String result = ” “;

for (int column = 0; column < size; column++) {

result += ” “+ column;

}

for (int row = 0; row < size; row++) {

result += “n” + row;

for (int column = 0; column < size; column++) {

if (squares

[column]) {

result += ” #”;

} else {

result += ” .”;

}

}

}

return result;

}

 

/** Create and play the game. */

public static void main(String[] args) {

System.out.println(“Welcome to Domineering.”);

System.out.print(“Please enter the width of the board:”);

Domineering game = new Domineering(INPUT.nextInt());

game.play();

}

 

}