Solution:
| | | | | | | | | 4 | | | | | | | | | | | | 5 | | | | | | | | 1 | | + | | 5 | | | | 5 | | | | 7 | | * | |35 | | | |35 | | - | |35 | | - | |35 | | - | | 2 | | + | | 2 | | + | | 2 | | + | | 2 | | + | | 2 | | + | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ before 1st ) after 1st ) before 2nd ) after 2nd ) before 3rd ) | | | | | 3 | | | | | | | | | | | | | | | |30 | | | |30 | | / | |10 | | | |10 | | | | | | | | 2 | | + | | 2 | | + | | 2 | | + | | 2 | | + | |12 | | | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ after 3rd ) before 4th ) after 4th ) before 5th ) after 5th ) |
2. The problem was to develop a child class of the following Java class:
public class Counter {
private int cntrVal; // instance variable
public Counter() { cntrVal = 0; } // constructor
public int getCount() { return cntrVal; } // observer
public void increment() { cntrVal++; } // mutator
public void decrement() { cntrVal--; } // mutator
}
|
The child class was to be able to report, via an observer method numSignChanges(), how many times the count value changed signs. Of course, an instance variable had to be introduced for the purpose of storing the sign change count. In order to maintain the correct count of sign changes, both the increment() and decrement() methods had to be overridden, in each case to update the sign change count whenever necessary (namely when an increment resulted in the count value becoming zero or a decrement resulted in the count value becoming −1).
Solution:
public class CounterWithSignChangeCount extends Counter {
private int signChangeCount; // instance variable
// constructor
// -----------
public CounterWithSignChangeCount() {
super(); // call parent class's constructor
signChangeCount = 0; // not necessary (0 is default)
}
// observer
// --------
public int numSignChanges() { return signChangeCount; }
// mutators
// --------
@Override
public void increment() {
super.increment();
if (getCount() == 0) { // count value must have just
signChangeCount++; // changed from -1 to 0
}
}
@Override
public void decrement() {
super.decrement();
if (getCount() == -1) { // count value must have just
signChangeCount++; // changed from 0 to -1
}
}
}
|
3. Given are these Java classes:
public class Automobile {
// instance variables
public String make;
public String model;
public int year;
...
...
}
|
public abstract class AutomobileSorter {
public void sort(Automobile[] carAry) {
...
...
}
protected abstract boolean lessThan(Automobile car1,
Automobile car2);
}
|
The task was to develop concrete child classes of AutomobileSorter whose inherited sort() method sorts the given array according to make and year, respectively.
A hint mentioned that the String class's compareTo() method is such that for strings s1 and s2 the truth value of the expression s1.compareTo(s2) < 0 corresponds to that of the statement "s1 is less than s2" (according to lexicographic order).
Solution:
public class AutoSorterByMake extends AutomobileSorter {
@Override
protected boolean lessThan(Automobile car1, Automobile car2) {
return car1.make.compareTo(car2.make) < 0;
}
}
public class AutoSorterByYear extends AutomobileSorter {
@Override
protected boolean lessThan(Automobile car1, Automobile car2) {
return car1.year < car2.year;
}
}
|
4. The task was to complete the development of a method that returns the length of a longest plateau in a given array of int values.
Solution:
/* Returns the length of a longest plateau in the given array.
** precondition: a.length > 0
*/
public static int lengthOfLongestPlateau(int[] a) {
final int N = a.length; // N is an abbreviation for a.length
int platStart = 0; // location at which the "current" plateau begins
int k = 1 ; int maxLenSoFar = 1 ;
// loop invariant:
// 1 ≤ k ≤ N ∧ a[platStart .. k) is a plateau ∧
// maxLenSoFar = length of longest plateau in a[0..k)
while ( k != N ) {
if (a[platStart] != a[k]) {
platStart = k;
}
k = k+1;
// the "current" plateau is a[platStart .. k)
maxLenSoFar = Math.max(maxLenSoFar, k-platStart);
}
// assert: k = N and maxLenSoFar = length of longest plateau in a[0..k)
}
|
Note that the occurrence of a[platStart] could be replaced by a[k-1], as we know that they are equal to each other. (Reasoning: The loop invariant requires that a[platStart .. k) is a plateau, which means that all its elements are equal, including its first, a[platStart] and its last, a[k-1].)
One could criticize the solution above for recomputing the value of maxLenSoFar during every loop iteration, including ones when its value could not possibly change. After all, there is no chance of its value needing to be modified during an iteration when the beginning of a new plateau is encountered (at location k). It follows that the method body can be rewritten like this:
final int N = a.length; // N is an abbreviation for a.length
int platStart = 0; // location at which the "current" plateau begins
int k = 1 ; int maxLenSoFar = 1 ;
// loop invariant:
// 1 ≤ k ≤ N ∧ a[platStart .. k) is a plateau ∧
// maxLenSoFar = length of longest plateau in a[0..k)
while ( k != N ) {
if (a[platStart] != a[k]) {
// the "current" plateau is now a[k..k+1) (of length one)
platStart = k; // beginning of new plateau encountered
}
else {
// the "current" plateau is extended to include location k
// and thus is now a[platStart .. k+1)
maxLenSoFar = Math.max(maxLenSoFar, k+1-platStart);
}
k = k+1;
}
// assert: k = N and maxLenSoFar = length of longest plateau in a[0..k)
}
|
Several students took the attitude that the maxLenSoFar variable should be considered for a possible update only when the beginning of a "new" plateau is encountered. This can be the basis for an alternative solution (see below), but it is slightly less elegant than the one above, because it requires that the length of the "rightmost" plateau be taken into account after the loop has terminated. Notice the subtle change in the last conjunct of the loop invariant, which now says that the value of maxLenSoFar is the maximum among the lengths of all "former" plateaus (i.e., those ending before location platStart) but does not take into account the length of the "current" plateau (i.e., the one beginning at location platStart).
final int N = a.length; // N is an abbreviation for a.length
int platStart = 0; // location at which the "current" plateau begins
int k = 1 ; int maxLenSoFar = 1 ;
// loop invariant:
// 1 ≤ k ≤ N ∧ a[platStart .. k) is a plateau ∧
// maxLenSoFar = length of longest plateau in a[0..platStart)
while ( k != N ) {
if (a[platStart] != a[k]) {
// update 'maxLenSoFar' in case the "previous" plateau
// a[platStart .. k) is the longest one so far
maxLenSoFar = Math.max(maxLenSoFar, k-platStart);
// the "current" plateau is now a[k..k+1) (of length one)
platStart = k; // beginning of new plateau encountered
}
k = k+1;
}
// Take account of the rightmost plateau a[platStart .. N)
maxLenSoFar = Math.max(maxLenSoFar, N-platStart);
// assert: k = N and maxLenSoFar = length of longest plateau in a[0..k)
}
|
5. The task was to develop a class Pet whose instances represent pets having a name, owner, birthday, and (after death) a "deathday". The constructor was to establish values for all of these attributes except for the date of death (which is assumed not to be known when the Pet object is created). For each of these four attributes there was to be an observer to report its value, plus there was to be a mutator by which a date of death is established.
Solution: The most common error made by students was to ignore both the instruction indicating the existence of Java classes Person and CalendarDate and the warning indicating that the only mentions of String should pertain to a pet's name. The intent was for the student to recognize that Person and CalendarDate are the appropriate abstractions/classes corresponding to, respectively, a pet's owner and birthday/deathday.
public class Pet {
// instance variables
// ------------------
private String name;
private CalendarDate birthday, deathday;
private Person owner;
// constructor
// -----------
/* Establishes this pet's name, birthdate, and owner.
*/
public Pet(String name, CalendarDate bDate, Person owner) {
this.name = name;
this.birthday = bDate;
this.owner = owner;
this.deathday = null; // not necessary; null is the default
}
// observers
// ---------
public String nameOf() { return this.name; }
public CalendarDate birthDate() { return this.birthday; }
public Person ownerOf() { return this.owner; }
public CalendarDate deathDate() { return this.deathday; }
// mutator
// -------
/* Records that this pet died on the specified date.
*/
public void recordDeath(CalendarDate deathDate) {
this.deathday = deathDate;
}
}
|