download instant at
Chapter 2 Solutions
Exercise 2.1
static Point translate3(Point p, int dx, int dy) {
// input: a nonnull point p, and two integers dx and dy
// side effect: translates point p by dx and dy
// output: point p after it is translated
p.setX(p.getX() + dx);
p.setY(p.getY() + dy);
return p;
}
Exercise 2.2
// methods of Point class
public void translate(int dx, int dy) {
// side effect: translates this point by dx and dy
moveBy(dx, dy);
}
public double distance(Point p) {
// input: a non-null point p
// output: distance between this point and p
long dx = getX() - p.getX();
long dy = getY() - p.getY();
long d2 = dx * dx + dy * dy;
return Math.sqrt((double)d2);
}
Exercise 2.3
(a) static double Math.random()
// EFFECTS: Returns a random number between 0.0 and 1.0.
(b) static void System.gc()
// MODIFIES: Java interpreter
// EFFECTS: Runs the garbage collector.
(c) void String.concat(String str) throws NullPointerException
// EFFECTS: If str is null throws NullPointerException;
// else concatenates str to the end of this string.
(d) void String String.charAt(int indx)
throws IndexOutOfBoundsException
// EFFECTS: If 0 <= indx < length() returns the
// character at index indx (where zero-based indexing
// is assumed); else throws IndexOutOfBoundsException.
(e) String String.replace(char oldChar, char newChar)
// EFFECTS: Returns a new string resulting from replacing
// all occurrences of oldChar in this string with newChar.
(f) int Integer.parseInt(String s) throws NumberFormatException
// EFFECTS: If s is well formed parses s as a signed
// decimal integer; else throws NumberFormatException.
(g) static void Arrays.sort(int[] a, int fromIndex, int toIndex)
throws ArrayIndexOutOfBoundsException,
IllegalArgumentException
// MODIFIES: a
// EFFECTS: If fromIndex > toIndex throws
// IllegalArgumentException; else if fromIndex < 0 or
// toIndex > a.length throws ArrayIndexOutOfBoundsException;
// sorts the subarray of a from index fromIndex through
// toIndex-1.
Exercise 2.4
static int min(int[] a, int lo, int hi) throws NullPointerException,
ArrayIndexOutOfBoundsException, IllegalArgumentException {
// EFFECTS: If a is null throws NullPointerException;
// else if a is empty throws ZeroArraySizeException; else if
// 0 <= lo <= hi < a.length returns the index of some
// smallest element in a[lo..hi];
// else throws IllegalArgumentException.
if (a == null) throw new NullPointerException();
if (a.length == 0) throw new ZeroArraySizeException();
if (hi < lo) throw new IllegalArgumentException();
int indx = lo;
for (int i = lo+1; i <= hi; i++)
if (a[i] < a[indx])
indx = i;
return indx;
}
Exercise 2.5
static int min(int[] a) throws ZeroArraySizeException,
NullPointerException {
// EFFECTS: If a is null throws NullPointerException;
// else if a is empty throws ZeroArraySizeException;
// else returns the index of some smallest item in a.
return min(a, 0, a.length-1);
}
Exercise 2.6
There are several problems with returning special values to indicate exceptions:
- The special values cannot then be used as "normal" return values.
- Client code must test for the special values within its logic. These tests will be mixed with the logic for normal processing.
- If the client code cannot handle the exception directly, it must arrange to propagate the exception to its caller. It does not have the advantage of Java's more elegant exception mechanism.
There are also disadvantages of setting a flag variable to indicate exceptions:
- The variable must be accessible to client code and any exception handlers.
- If the client code cannot handle the exception directly, it must arrange to propagate the exception to its caller. It does not have the advantage of Java's more elegant exception mechanism.
- The flag may inadvertently be reset before the client reads it.
Note that the special return values and flag values that a procedure can set are part of the procedure's specification.
Exercise 2.7
static void swap(int[] a, int i, int j) {
// REQUIRES: 0 <= i,j < a.length.
// MODIFIES: a
// EFFECTS: Swaps the contents of a[i] and a[j] while leaving
// unchanged the contents of the remaining elements of a.
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
Exercise 2.8
public class SortIntegerArgs {
public static void main(String[] args) {
try {
int[] a = getNumbers(args);
sort(a);
printNumbers(a);
} catch (NumberFormatException e) {
String msg = "Error: argument " + e.getMessage();
msg += " is badly formed.";
System.out.println(msg);
System.exit(0);
}
}
static int[] getNumbers(String[] args)
throws NumberFormatException {
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
a[i] = Integer.parseInt(args[i]);
return a;
}
static void printNumbers(int[] a) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
static void sort(int[] a) throws NullPointerException {
sort(a, a.length);
}
static void sort(int[] a, int n) throws NullPointerException {
for (int i = 0; i < n; i++) {
int indx = min(a, i, n-1);
swap(a, i, indx);
}
}
static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
static int min(int[] a, int lo, int hi)
throws NullPointerException, ArrayIndexOutOfBoundsException,
IllegalArgumentException {
if (hi < lo) throw new IllegalArgumentException();
int indx = lo;
for (int i = lo+1; i <= hi; i++)
if (a[i] < a[indx])
indx = i;
return indx;
}
}
Exercise 2.9
static void sort(int[] a, int n) throws NullPointerException,
IllegalArgumentException {
if ((n < 0) || (n > a.length))
throw new IllegalArgumentException();
for (int i = 0; i < n; i++) {
int indx = min(a, i, n-1);
swap(a, i, indx);
}
}
Exercise 2.10
static void sort(int[] a) throws NullPointerException {
// MODIFIES: a
// EFFECTS: If a is null throws NullPointerException;
// else sorts a in non-decreasing order.
sort(a, a.length);
}
Exercise 2.11
It is never a problem for a client to call a procedure that achieves a stronger postcondition than the client requires, or for a client to call a procedure that requires a weaker precondition than the client satisfies. We explore these points further when we treat polymorphism and the substitution principle in Section 5.5.
Exercise 2.12
The SortStringArgs class is similar to our SortIntegerArgs class with only two differences:
- we are handling strings rather than integers, and
- two strings are compared using the String.compareTo method.
(In Section 5.5, polymorphism is used to develop a general sorting program that can be used to sort all kinds of comparable objects.)
public class SortStringArgs {
public static void main(String[] args) {
sort(args);
printStrings(args);
}
static void printStrings(String[] a) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
static void sort(String[] a) throws NullPointerException {
sort(a, a.length);
}
static void sort(String[] a, int n) throws NullPointerException {
for (int i = 0; i < n; i++) {
int indx = min(a, i, n-1);
swap(a, i, indx);
}
}
static void swap(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
static int min(String[] a, int lo, int hi)
throws NullPointerException,
ArrayIndexOutOfBoundsException, IllegalArgumentException {
if (hi < lo) throw new IllegalArgumentException();
int indx = lo;
for (int i = lo+1; i <= hi; i++)
if (a[i].compareTo(a[indx]) < 0)
indx = i;
return indx;
}
}
Exercise 2.14
static int power(int a, int b) {
// REQUIRES: b is nonnegative.
// EFFECTS: Returns a raised to the b power.
if (b == 0) return 1;
else return a * power(a, b-1);
}
Exercise 2.15
static void haltsOnNoInput(int a) {
haltsOnNoInput(a);
}
static void haltsOnOnlySomeInput(int a) {
if (a == 0) return;
else haltsOnOnlySomeInput(a);
}
Exerise 2.16
This is the inefficient version directly based on the inductive definition of the Fibonacci sequence. See Exercise 2.16 in the text for a recursive procedure that computes Fibonacci numbers efficiently.
static long fib(int n) {
// REQUIRES: n is non-negative (and a lot of time for large n)
// EFFECTS: Returns element n in the Fibonacci sequence.
if ((n == 0) || (n == 1)) return n;
else return fib(n-1) + fib(n-2);
}
Exercise 2.17
static int sumOver(int[] a, int lo, int hi) {
// REQUIRES: a is not null, and 0 <= lo <= hi < a.length.
// EFFECTS: Returns the sum a[lo] + … + a[hi].
if (lo == hi) return a[lo];
else return a[lo] + sumOver(a, lo+1, hi);
}
static int squareMap(int[] a, int lo, int hi) {
// REQUIRES: a is not null, and 0 <= lo <= hi < a.length.
// EFFECTS: Replaces each item x in a[lo..hi] by x squared.
if (lo == hi) {
a[lo] = a[lo] * a[lo];
return;
} else {
a[lo] = a[lo] * a[lo];
squareMap(a, lo+1, hi);
}
}
static int summation(int n) {
// REQUIRES: n is non-negative.
// EFFECTS: Returns 0+1+…+(n-1)+n.
if (n == 0) return 0;
else return n + summation(n-1);
}
static int summationInConstantTime(int n) {
// REQUIRES: n is non-negative.
// EFFECTS: Returns 0+1+…+(n-1)+n.
return (n * (n+1)) / 2;
}
static int find(int x, int[] a, int lo, int hi)
// REQUIRES: a is not null, and 0 <= lo <= hi < a.length.
// EFFECTS: Returns the position of the first x in a[lo..hi];
// returns -1 if x does not occur in a[lo..hi].
if (lo == hi) {
if (a[lo] == x) return lo;
else return -1;
} else {
if (a[lo] == x) return lo;
else return find(x, a, lo+1, hi);
}
}
The solutions given above follow the natural inductive definition for each problem. Some can be made more efficient, for example:
static int find(int x, int[] a, int lo, int hi)
// REQUIRES: a is not null, and 0 <= lo <= hi < a.length.
// EFFECTS: Returns the position of the first x in a[lo..hi];
// returns -1 if x does not occur in a[lo..hi].
if (a[lo] == x)
return lo;
else if (lo == hi)
return -1;
else
return find(x, a, lo+1, hi);
}
Moreover, the procedure specifications can be revised so that subarrays of length zero count as legal input. For example:
static int find2(int x, int[] a, int lo, int hi)
// REQUIRES: a is not null, and (0 <= lo <= hi < a.length) or
// hi < lo.
// EFFECTS: If hi < lo or x does not occur in a[lo..hi] then
// returns -1; else returns the position of the first occurrence
// of x in a[lo..hi].
if (hi < lo)
return -1;
else if (a[lo] == x)
return lo;
else
return find2(x, a, lo+1, hi);
}
Exercise 2.18
public class MergeSortIntegerArgs {
public static void main(String[] args) {
try {
int[] a = getNumbers(args);
sort(a);
printNumbers(a);
} catch (NumberFormatException e) {
String msg = "Error: argument " + e.getMessage();
msg += " is badly formed.";
System.out.println(msg);
System.exit(0);
}
}
static int[] getNumbers(String[] args)
throws NumberFormatException {
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
a[i] = Integer.parseInt(args[i]);
return a;
}
static void printNumbers(int[] a) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
static void sort(int[] a) {
msort(a, 0, a.length-1);
}
static void msort(int[] a, int lo, int hi) {
if (lo == hi) return;
else {
int mid = (lo + hi) / 2;
msort(a, lo, mid);
msort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
}
static void merge(int[] a, int lo, int mid, int hi) {
int[] b = new int[hi-lo+1];
int i = lo, j = mid+1, k = 0;
while ((i < mid+1) & (j < hi+1)) {
if (a[i] < a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
if (i == mid+1)
System.arraycopy(a, j, b, k, hi-j+1);
else
System.arraycopy(a, i, b, k, mid-i+1);
System.arraycopy(b, 0, a, lo, b.length);
}
}
download instant at