### Midterm Exam -- Thursday, May 17th -- ANSWERS

Spring 2001 -- Professor Futrelle
College of Computer Science, Northeastern U., Boston, MA

• This was a closed-book test, duration 65 minutes.

Updated May 31st, 2001.

Question 1.

Write a simple class with two methods method1() and method2() that have distinct implementations but are each members of the specificand set for the following specification. Your answer must consist of Java code that you write. (The methods may be static or not. The distinction is not important here.)

"Given two arguments of type double, return the average of the two unless their difference is between -1.0 and +1.0 (inclusive). In that case, return the value of the first argument."

Question 1. ANSWER. Here are two reasonably distinct solutions that meet the specification, with tests. (You were not asked to write tests.)

```// com1204 sp01 midterm Problem 1
// Prof. Futrelle

class P1 {

public static void main(String[] args) {

// tests followed by outputs, as comments
// Three tests of method1():

System.out.println(method1(40.0, 50.0));
// 45.0 average
System.out.println(method1(40.0, 40.1));
// 40.0  first argument
System.out.println(method1(40.0, 39.9));
// 40.0  first argument
System.out.println(method1(40.0, 41.0));
// 40.0  first argument, exactly 1.0 difference
System.out.println(method1(40.0, 41.0025));
// 40.50125 average (arguments differ by 1/400 (prints neatly))

// Three tests of method2():

System.out.println(method2(40.0, 50.0));
// 45.0  average
System.out.println(method2(40.0, 40.1));
// 40.0 first argument
System.out.println(method2(40.0, 39.9));
// 40.0 first argument
System.out.println(method2(40.0, 39.0));
// 40.0  first argument, exactly -1.0 difference
System.out.println(method1(40.0, 41.0025));
// 40.50125 average (arguments differ by 1/400 (prints neatly))
}

// tests one expression and returns first, else
// reaches other return of average.
public static double method1(double a, double b) {
if( -1.0 <= (a - b)  && (a - b)  <= 1.0)
return a;
return ((a  + b)/2);
}

// precomputes the difference and the average
// and uses nested ifs
public static double method2(double a, double b) {
double diff = a - b;
double av = (a + b)/2.0;

if(diff <= 1.0)
if (diff >= -1.0)
return a;
return av;
}
}
```

Some thought that you could violate the spec with one or both of the functions. In fact, each function has to satisfy the entire specification, else it is not a member of the specificand set.

Comparators such as "less than or equal to" are always written in Java (and C++) as a pair of symbols, "<=", not as a single character (which isn't on any keyboard!).

Returning an int from the methods was not disallowed by the spec, but makes little sense. If such an unusual coercion were desired or allowed, it would be most likely noted in the spec.

Question 2.

Write two specifications, one more general than the one below and the other more specific.

"Given two integer arrays, possibly different in length, the function returns an integer which is the number of values in the first array that also appear in the second array."

Hint: You'll only need to write the Requires and Effects specifications for the two.

A more general (less restrictive) specification:

REQUIRES: Takes two arrays (unrestricted type).
EFFECTS: The function returns an integer which is the number of values in the first array that also appear in the second array.

Some thought that adding a restriction that the arrays be non-null was more general. In fact, it is a restriction, making such a specification more restrictive.

A more specific (more restrictive) specification:

REQUIRES: The integer arrays must be different in length (a restriction). They must be non-null (a restriction). Both must be sorted in ascending order (a restriction).
EFFECTS: The function returns an integer which is the number of values in the first array that also appear in the second array.
(Note: The algorithm can be designed to be quite efficient if the arrays are sorted, but there is a cost to sorting. In addition the less restrictive version might copy and sort the arrays internally or even sort them and modify the inputs, though that would need to be specified in a MODIFIES clause.

A number of people wrote operational specifications, which are hardly even mentioned in the book, and for good reasons. Operational specs typically place undue restrictions on the implementor, as well as forcing the reader to study the specification in order to understand what the final result will be. An operational specification is a half-step towards just giving the reader the source code, the very thing that specifications are designed to avoid.

The fact that the spec called for returning an integer which is the number of values in the first array that also appear in the second is fairly concise specification, though not everyone payed close attention to it.

You must always remember that the REQUIRES clause should never simply repeat what is already obvious from the arglist, e.g., that a function takes an integer as one of its arguments. But if, for example, the function required a an integer > 0, that should be mentioned, since it is not obvious from the arglist.

Question 3.

3A. Describe how you could do a black-box test of a function with the following specification. No code is required but you should list some typical arrays and values of n you would use and explain your choices.

"Given an integer array arr[] as one argument and an integer n as the other argument, the function fn1() returns the largest element of arr[] with index greater than or equal to n."

1. Use an array such as {3,7,2,9,4} with indexes 0...4.
• A simple test would use n values of 0, 1, 3 and 4, testing near both ends of the array with legal indices. The largest elements that should be found for this sequence should be 9, 9, 9 and 4.
• A more demanding test could use n values -10, -2, -1, 0, 1, 2, 3, 4, 5, 6 and 10. This tests indexes beyond both ends of the array, near the beginning, the middle, near the end and beyond the end. The largest elements that should be found for this sequence should be 9, 9, 9, 9, 9, 9, 9, 4, 4, 4 and 4. Or possibly, the function would raise run-time exceptions for indices outside the array limits.
2. You could also use arrays of all equal elements and sorted arrays or simply pass an array in which the largest element was the first or the last element -- special cases that an algorithm might get wrong.
3. You could pass null for the array argument.

Most people did fairly well on this question. There was some confusion about the difference between a null string and an empty string. A whose value is null is not a string and you cannot, for example, concatenate it with other strings, etc. An empty string is a String that has no characters in it. You can legally compute the length of an empty string using length() (which will return 0 for this case).

There are basically three things that can be varied in the tests: The array size, the arrangement of elements in the array, and the value of the integer argument n.

Some people suggested trying a null value for the integer argument. This is not allowed in the Java language -- an integer is a primitive, not an object. Only object values can be set to null (no object). Such errors are typically caught at compile-time.

3B. Given the following implementation of fn1(), describe in some detail how you could do a glass-box test of the function. No code is required but you should list some typical arrays and values of n you would use and explain your choices. In addition, describe how your choices of arrays and n values changed between parts A and B of the question due to the fact that you were now doing glass-box testing.

```    public int fn1(int[] arr, int n) {
if(n >= arr.length) {
System.out.println("Index too large");
return -1;
}
if(n == arr.length - 1) return arr[n];

int largest = arr[n];

for(int i = n + 1; i < arr.length; i++) {
if (arr[i] > largest) largest = arr[i];
}
return largest;
}
}```

Question 3B. ANSWER. The tests in the answer to 3A were so thorough, that there's little more you could do for a glass box test. You would, at least, want to test each special case handled by the code above, viz., n larger than the last legal array element and n equal to the largest array index. The reason that it is difficult in this case to come up with more specific tests for glass-box testing is that there are no complex private representations or operations that are not obvious from the original black-box, external specifications. This notwithstanding, if you had not thought to test the case of n being too large, the source code would suggest to you that you should. At the same time you might realize that you should test for the case of n too small (n < 0). If you created an array which -1 was the largest element in the array, {-20,-1,-7, -1} you could not distinguish this from the return that occurs when the index passed is too large. Notice that the specification does not discuss what happens for indices outside of the array bounds.

The testing can be thought through rather systematically by looking at every conditional in the code and making sure that your tests touch as many result cases as possible. For this code there are two tests involving n, one test of i and a test that compares arr[i] with the local variable largest. The other part of the systematic approach involves varying the length of the array as well as the data and arrangements of data in it.

Question 4. Assume that the five examples below all cause compile-time or run-time errors. For the compile-time errors, explain what types of problems they would lead to if they were compiled -- that is, what are the reasons that the statements should not be compiled? For the run-time errors, what types of errors will occur at run time?

``` 4A.  o2.length(), where o2 is of type Object.

4B.  ((String) o3).length(), where the actual type of o3 is Object.

4C.  s = o4, where s is of type String and o4 is of type Object.

4D.  Integer.parseInt("twohundredandfive")

4E.  v.add(17), where v is of type Vector.
```

A number of people failed to note whether the errors were compile-time or run-time errors. This is an important distinction which you must understand.

``` 4A.  o2.length(), where o2 is of type Object.
Compile-time error -- an Object has no length() method.
If it attempted to find such a method at run-time it would
be guaranteed to fail. Hence, it fails at compile-time.

4B.  ((String) o3).length(), where the actual (run-time) type of o3 is Object.
Run-time error.  The system discovers, at run time, that o3 is
an Object, not a String, so there is a class-cast exception raised.

4C.  s = o4, where s is of type String and o4 is of type Object.
Compile-time error.  If the assignment were attempted at run-time,
no String methods would succeed if s was used subsequently.

4D.  Integer.parseInt("twohundredandfive")
At run time, the function attempts to parse "twohundredandfive" and fails.
It  would succeed if the string  were "205".
See Sec. 2.6.1 of the textbook.

4E.  v.add(17), where v is of type Vector.
Compile-time error.  When the compiler does type-checking of
the argument types allowed by add() for Vector  it finds  that
ints are not  allowed, only objects, and 17 is an int, so compile fails.
```

Question 5.

Explain why the constructor in this class P5 "exposes its rep". Describe an example of how you could interfere with the operation of the class by manipulating the exposed object. You should explain your answer in English.

```class P5 {

SomeClass s;

P5(SomeClass s) {
this.s = s;
}
}
```

Question 5. ANSWER. If an object is created external to P5 and then passed to the constructor, P5 uses a reference to the object, not a copy of it. Therefore, whoever has the original reference to the object can change it, changing an object that is "inside" a class, and thus exposes the rep. Actually, the rep is exposed in a second way, since the instance variable s is not private, as it normally should be.

Some people thought that if an external variable, say sc, was set to a SomeClass instance and passed to the P5 constructor, that setting sc to null would set the internal member variable s to null. That does not happen, for reasons explained in the examples in Sec. 2.3 of the book.

Question 5: Extra Credit. Write code demonstrating how you could expose the rep of P5, assuming that SomeClass has a public method setVal(int) to set some value within an instance of SomeClass.

Question 5. Extra Credit. ANSWER. This shows how an object, sc can be created, given to P5 in a constructor with sc then altered and the value within P5 changed, since the rep was exposed through the reference and the reference to sc was maintained by the calling program in main().

```// com1204 sp01 midterm Problem 5
// Prof. Futrelle

class P5 {

SomeClass s;

P5(SomeClass s) {
this.s = s;
}

public void showHidden() {
System.out.println(s.showPriv());

public static void main(String[] args) {

SomeClass sc = new SomeClass();

P5 p = new P5(sc);

sc.setVal(33);
// has changed a value in a private member of P5

p.showHidden(); // Shows change to private object
} // prints 33

}

// com1204 sp01 midterm Problem 5
// Prof. Futrelle

class SomeClass {

private  int i;

public void setVal(int k) {
i = k;
}

public int showPriv() {
return i;
}
}

```

Question 6.

Write the REQUIRES, MODIFIES and EFFECTS specifications for the following method which finds largest value in the array that's less than closeTo. HINT: You'll need to examine the code closely to see what assumptions the code makes when finding the result.

```        public static int fn2(int[] arr, int closeTo) {

for(int i = 1; i < arr.length; i++) {
if(arr[i] > closeTo) return arr[i-1];
}
return arr[arr.length - 1];
}
```

Here are some observations that could lead to figuring out how the code works and therefore what the REQUIRES spec should be. The most interesting thing is that the loop stops the very first time it encounters an element that is greater than closeTo. If the spec holds, then the remaining values must be greater than or equal to closeTo. This is confirmed by the presence of the ">" test. The function then returns the value of the item preceding the one just tested, since the one just tested is greater than closeTo and would violate then spec. (There is one small error in the implementation. ">" should be ">=". For that Prof. Futrelle lost 2 points and all of you gained 2 points ;-)

A concrete way in which to think through the operation of this function is to imagine handing it a variety of arrays, such as {0, 5, 10} or {5, 10, 0}, etc. You would (hopefully) soon realize that an array in ascending order is needed.

You might then notice that an array of zero length will cause a run-time error, since the for loop will not run and the second return will attempt to access the array with index -1.

Some people discussed having "null ints" in the array. As was said earlier, an int is a primitive, not an object, so it can never be set to null.

In this problem, a definitional spec is definitely a better one, since another implementation of the algorithm might work differently, e.g., using binary search.

So here are appropriate specification clauses. There is no MODIFIES clause, since neither argument is altered by the method (no assignments to the array or to closeTo).

REQUIRES: The array sorted in ascending order. The array should not be null. (Note that nothing is said about any restrictions on the value of closeTo simply because there are no restrictions on it.)
EFFECTS: Returns the largest value in the array that's less than (or equal to) closeTo. If every value in the array is larger than closeTo, the smallest of these is returned. If the array is empty, an exception is thrown.