Software Quality

Assignment #3

Due: 11/28/22

public int search(int data[], int key) {

  1 int lower, upper, location;

  2 lower = 0;

  3 upper = data.length - 1;

  4 location = -1;

  5 while (location == -1 && lower <= upper) {

  6   if (data[lower] == key)

  7       location = lower;

  8   if(data[lower] > key)

  9       lower = upper;

  10   lower = lower + 1;

  }

11 return(location);

1: (30 points) For the function “search” given above, symbolically execute two paths: one that is infeasible and enters the loop only once and one that is feasible and returns having found the key, with “lower” equal to one.

2: (20 points) For the function “search”:

a) provide input and output assertions

b) provide a loop invariant and show where you would associate this assertion with the code

3: (20 points) Prove that the function “search” terminates or show that it does not terminate.

4: (30 points) Suppose a testing criterion used for derivation of test cases requires to form new test cases that create distinct call stacks. How could you use a state transition model of the methods in a class to help create these test cases?

Consider the UniqueTable example that maintains a table of unique entries:

class UniqueTable

  create();

  insert(entry);

  delete(entry);

  isEmpty() returns Boolean;

  isEntered(entry) returns Boolean;

end class;

Assume that “insert” throws an exception and then aborts if it is called with an entry that is already in the table and that “delete” throws an exception and then aborts if it is called with an empty table. How would the test cases differ if UniqueTable were defined such that “insert” and “delete” do nothing if the entry is already in the table or not in the table, respectively?