CSE331 Autumn 2011
Software Design and Implementation


 Assignment 2 (10%): Due in two parts (a) 11:59PM Monday October 10 and (b) 11:59PM Friday October 14, 2011

There are two objectives for this assignment: to improve your effectiveness at black-box unit testing and to help you get back up to speed a little bit on Java collections and generics.

Part (a): Black-box testing of binary search. (Due Monday October 10, 2011, 11:59PM.)

Binary search is an elegant but simple algorithm that many of you have seen.  The basic idea is to start with two inputs: a sorted array and a key to search for.  If the key is found in the array, the index of the key is returned.  Otherwise, an indication that the search failed is returned.  What binary search does is to look first at the element in the middle of the array: if it is equal to the key, return the index; if it is less than the key, perform binary search on the "top half" of the array (not including the middle element); and if it is greater than the key, perform binary search on the "bottom half" of the array (not including the middle element).  Correct implementations of the algorithm run in O(lg2N), which means that the worst case for running the program will take time proportional to the (base 2) logarithm of N, where N is the length of the sorted array.

As a simple example, consider the following integer array (indexed from 0 to 8, as shown), sorted in non-decreasing order:

0
 1
 2
 3
 4
 5
 6
 7
 8
4
 9
 17
 18
 39
 1024
 2222
 4321
 12345





1024
 2222
 4321
 12345





1024



Considering searching the array for the key 1024.  Start comparing 1024 to the middle element, 39.  1024 is greater than 39, so search for 1024 in the "top half" subarray shown in the second row.  Pick (one of the) middle elements, say 2222.  1024 is less than 2222, so search for 1024 in the "bottom half" of the remaining subarray.  That subarray contains only one element, 1024, so the search will succeed and return 5, the index at which the key was finally found.  For an example of a failure, use the same example but search for the key 1023.  It will work identically until the final comparison, which fails (1024 > 1023) and there is no remaining "bottom half" subarray to search in, so the key is not found.

Even though the basic notion of binary search is relatively straightforward, there are a ton of details to get right, such as:
Some questions like these are answered by the program's specification.  Here is a specification for binary search (a slight variation from the second lecture):

/**
 * @param data is a sorted int array in which to search for the key
 * @param size is the size of data
 * @param key the key to search for in data
 * @returns some i such that data[i] = key if such an i exists, otherwise -1
 * @requires data is sorted in non-decreasing order 
 * @requires size >= 0 and size <= a.length-1
 * 
 */
public static int binarySearch(int[] data,int size,int key)

This answers the first question above as "return -1" and the third question "non-deterministically," which means that any index for which the key matches the value at that index can be returned.  The specification is silent on the second point, which means that the programmer can make any decision (as long as the resulting program satisfies the specification, that is).

For this part of the assignment you will write (black-box) JUnit tests for an implementation of this specification that we provide.  The implementation works properly in many cases, but it has at least two bugs in it. Your tests should identify (at least) two bugs and should also build confidence that the bugs you find are the only ones in the implementation. That is, a test suite with k tests to demonstrate k bugs isn't much of a test suite. It should help build confidence in the parts of the input for which the program works properly. Also, the tests that do demonstrate bugs should be refined to give as precise information about the bug as possible. (If you think a bit about it, this last sentence conveys precisely the same point as the previous sentence.)

You can and should assume that there is no malicious code in the implementation; the bugs are legitimate mistakes that people often make when writing binary search. (The implementation consists of 15-16 quite conventional Java source lines.) This part of the assignment should take more brainpower than computing—thinking hard about binary search and the specification will surely be the best first step.

Here is an executable jar file with the binarySearch code. And here is the basic javadoc for BinarySearch. The jar also contains a simple main method that executes the method twice:

public static void main(String[] args) {
  int a1[] = {0, 10, 20, 30, 30, 45, 60, 90, 100};
  System.out.println(BinarySearch.binarySearch(a1,a1.length,10));
  System.out.println(BinarySearch.binarySearch(a1,a1.length,17));
}
Running main prints 1 on one line and -1 on the next line. But test binarySearch directly, of course.

Part (b): Fixing and extended binary search

FYI: After finishing part A, you might be interested in reading the following about a bug in the historical binary search algorithms. It should exist in the code I provided, although I couldn't set up the environment to tickle it. There are a couple of points to take away from the post: (a) there is a long history of bugs in binary search, despite its abstract simplicity; and (b) scale and size introduce previously unforeseen errors.

This is the second part of the assignment, which focuses on taking the flawed source code and modifying it (1) to fix the errors and (2) to enhance it to take more complex inputs than an array of ints. Here is the code and its (corrected) specification:

/**
 * @param a a sorted int array in which to search for the key
 * @param size the size of a
 * @param key the key to search for in a
 * @returns some i such that a[i] = key if such an i exists, otherwise -1
 * @requires a is sorted in non-decreasing order (no element with a smaller
 *        index is greater than an element with a larger index)
 * @requires size >= 0 and size <= a.length
 *
 */

public static int binarySearch(int[] a,int size,int key) {
  int low = 0;
  int high = size-1;
  int index;
  do {
    index = (low+high) / 2;
    if (key < a[index])
      high = index-1;
    else
      low = index+1;
  } while (low <= high && key != a[index]);
  if (low <= high)
    return index;
  else
    return -1;
}

Java 1.6 includes the following method: binarySearch(T[], T, java.util.Comparator). You are basically to reimplement this by fixing the above code (that is, removing the bugs in part A) and by incorporating the use of generics, Comparator, etc. Since the object is for you to get more comfortable with generics and such, do not use or look at the Java code for this method. (But there are lots of other examples for using generics, comparator/comparable, etc.)

You are to:

  1. Rewrite the specification above (which is indeed slightly different from the binarySearch in Java) to represent the change to generics
  2. Update your test suite to both ensure that the existing bugs are removed and that there is increased confidence that your code works for arbitrary generic types.
  3. Finally, look at the Java 1.4.2 equivalent of the above 1.6 binarySearch method. Write one or two paragraphs (no more!) describing the difference between the two and the consequences that this difference has in terms of the ways in which the client uses the method -- what would Java 1.4.2 clients have to do differently than 1.6 clients, and what pitfalls might arise in 1.4.2 clients because of these differences.