3. The problem was to twice trace execution of the Binary Search algorithm (see below) on the array show below, by showing the values of the variables low, high and mid at the conclusion of each loop iteration. The search keys were to be 42 and 14.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | -3| 0 | 9 | 11| 14| 14| 21| 24| 24| 31| 34| 39| 41| 43| 43| 51| 55| 67| 72| 75| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
Solution:
When low high mid When low high mid
+------------------+-----+------+-----+ +------------------+-----+------+-----+
| Before 1st iter. | 0 | 20 | - | | Before 1st iter. | 0 | 20 | - |
+------------------+-----+------+-----+ +------------------+-----+------+-----+
| After 1st iter. | 11 | 20 | 10 | | After 1st iter. | 0 | 10 | 10 |
+------------------+-----+------+-----+ +------------------+-----+------+-----+
| After 2nd iter. | 11 | 15 | 15 | | After 2nd iter. | 0 | 5 | 5 |
+------------------+-----+------+-----+ +------------------+-----+------+-----+
| After 3rd iter. | 11 | 13 | 13 | | After 3rd iter. | 3 | 5 | 2 |
+------------------+-----+------+-----+ +------------------+-----+------+-----+
| After 4th iter. | 13 | 13 | 12 | | After 4th iter. | 3 | 4 | 4 |
+------------------+-----+------+-----+ +------------------+-----+------+-----+
For key = 42 | After 5th iter. | 4 | 4 | 3 |
+------------------+-----+------+-----+
For key = 14
|
As the instructions indicate, each loop iteration ends with either low == mid+1 or high == mid. That is a direct consequence of the fact that, during each iteration, exactly one among the assignment statements low = mid+1 and high = mid is executed (after which no further changes are made to any of the variables).
/* Returns the minimum value k such that either k == a.length or a[k] >= key.
** pre: The elemetns in a[] are in ascending order.
*/
public static int binarySearch(int[] a, int key) {
int low = 0, high = a.length;
// loop invariant: Every element in a[0..low) is < key and
// every element in a[high..a.length) is >= key
while (low != high) {
int mid = (low + high) / 2;
if (a[mid] < key)
{ low = mid + 1; }
else // a[mid] >= key
{ high = mid; }
}
return low;
}
|
/* An instance of this class represents a pair of six-sided dice, such as
** are used in board games and other games of chance.
*/
public class PairOfDice {
/* Returns the total number of dots showing on the dice (between 2 and 12). */
public int dotsShowing() { ... }
/* Rolls the pair of dice. */
public void roll() { ... }
|
The problem was to supply the body of a method that rolls a pair of dice (provided via a parameter in the form of an instance of the class PairOfDice) until the same result occurs twice in a row. The value to be returned is the number of times the dice were tossed.
Solution: A couple of fundamental observations are key to developing a solution. One is that a loop is necessary, which follows from the fact that the method must roll a pair of dice repeatedly until such time as a particular condition has been met. Another is that, because the relevant condition pertains to the results of the two most recent dice rolls, a variable is needed to store/remember the result of the earlier of those two rolls. (After all, there is no method in the PairOfDice class by which to ascertain the result of any but the most recent roll.)
/* Given a pair of dice (represented by the instance of PairOfDice provided via the
** parameter), this method rolls the dice repeatedly until such time as the same
** result has occurred twice in a row (i.e., on consecutive dice rolls). The
** value returned is the number of times that the dice were rolled. For example,
** if the results of the rolls were 9, 5, 12, 7, and 7, the value returned would
** be five.
*/
public static int numRollsUntilRepeat(PairOfDice dice) {
int prevRoll = -1; // or any other value not in [2..12]
dice.roll();
int count = 1;
while (dice.dotsShowing() != prevRoll) {
prevRoll = dice.dotsShowing();
dice.roll();
count = count + 1;
}
return count;
}
|
Here is an alternative solution that makes use of Java's do-while loop. When (and only when) a loop is intended to iterate at least once (and thus it is not necessary to evaluate the loop guard until after the first iteration), a do-while loop is an appropriate construct.
public static int numRollsUntilRepeat2(PairOfDice dice) {
int prevRoll;
dice.roll();
int count = 1;
do {
prevRoll = dice.dotsShowing();
dice.roll();
count = count + 1;
}
while (dice.dotsShowing() != prevRoll);
return count;
}
|
A less-experienced programmer perhaps would have been more likely to come up with a solution such as the one below, which makes use of a boolean variable for the purpose of indicating whether or not two consecutive dice rolls produced the same result.
public static int numRollsUntilRepeat3(PairOfDice dice) {
dice.roll();
int count = 1;
int currentRoll = dice.dotsShowing();
boolean keepGoing = true;
while (keepGoing) {
int prevRoll = currentRoll;
dice.roll(); count = count + 1;
currentRoll = dice.dotsShowing();
if (prevRoll == currentRoll) {
keepGoing = false;
}
}
return count;
}
|
5. The problem here was to augment the Fraction class (the subject of a recent programming assignment) with the methods isLessThan() and reciprocalOf().
Solution: The added code in in blue.
public class Fraction {
/* instance variables */
private int numerator, denominator;
/* constructor */
public Fraction(int numer, int denom) { setTo(numer, denom); }
/* observers */
public int getNumerator() { return this.numerator; }
public int getDenominator() { return this.denominator; }
...
...
/* private methods */
/* Updates the instance variables to make them describe the fraction
** numer/denom in simplest form. If denom==0, an exception is thrown.
*/
private void setTo(int numer, int denom) { ... }
/* NEW METHODS */
/* Reports whether or not this fraction (i.e., the instance of Fraction
** upon which this method was called) is less than the given one, 'frac'.
** One rule by which to make this determination is this: Assuming that the
** fractions are in simplest form, a/b < c/d is equivalent to a*d < b*c.
*/
public boolean isLessThan(Fraction frac) {
return this.getNumerator() * frac.getDenominator() <
this.getDenominator() * frac.getNumerator()
}
/* Returns a new instance of Fraction representing this one's reciprocal.
**
** pre: this.getNumerator() != 0
*/
public Fraction reciprocalOf() {
return new Fraction(this.getDenominator(), this.getNumerator());
}
{
|
Note that each occurrence of this. is optional. Also, the calls to getNumerator() (respectively, getDenominator()) could have instead referred directly to instance variable numerator (respectively, denominator).