You can download the source code with test cases for all the exercises here. They are produced under Eclipse and can be easily imported there if desired (File -> Import; Existing projects into workspace; Select archive file;).

In relation to the spacification exercises, there are two extremes to specification: overspecification (when you disclose too much information about how things are implemented) and underspecification (being too vague on what the thing you are specifying does). What should drive you is mainly common sense. There can be different specifications to a method: whether they are good or not is a matter of context, and you should apply Occam's razor in order to guarantee precision and freedom for the implementors as well.

Exercise 1

Consider this method:

  public static Object[] reverse(Object[] a) {
    if (a == null) return null;
    Object[] b = new Object[a.length];
    for (int i = 0; i < a.length; i++) {
      b[i] = a[a.length - 1 - i];
    }
    return b;
  }

The method returns a new array where the order of the elements has been reversed. (Your specification should be more detailed than the previous sentence.)

1 a) What does this method do? Write it in a meaningful way, taking as example the slides about specification of the intro slides of the course.

1 b) Derive test cases which together have full statement coverage. Then add test cases if necessary to have full branch coverage.

Exercise 2

Consider this method:

  public static void vector_add(Float[] a, Float[] b) {
    for (int i = 0; i < a.length; i++) {
      a[i] += b[i];
    }
  }

The method computes the vector addition of a and b and stores the result in a.

2 a) What does this method do?

2 b) Derive test cases for the method.

Exercise 3

This exercise is about an implementation of a queue. We do this using the usual "rotating array" implementation. Furthermore, we are going to stress the fact that whether testing is successful or not depends on what we expect. Consider the following class for representing a queue:

  public class Queue {
    Object[] arr;
    int size;
    int first;
    int last;

    public Queue(int max) {
      arr = new Object[max];
      size = 0;
      first = 0;
      last = 0;
    }

    public int size() {
      return size;
    }

    public int max() {
      return arr.length;
    }

    public void enqueue(Object x) {
      arr[last] = x;
      last++;
      if (last == arr.length) last = 0;
      size++;
    }

    public Object dequeue() {
      if (size == 0) return null;
      Object x = arr[first];
      first++;
      if (first == arr.length) first = 0;
      size--;
      return x;
    }
  }

3 a) For each method in Queue, give a specification like in points 1a and 2a.

3 b) Derive test cases for each method. Analyse the failed tests and their relationship to what you were expecting.

Notes.

• Whenever you might have to test several things together, in designing tests you have a choice that must be driven by:
  • Traceability (from where did this defect came out?)
  • Readability (will any other programmer be able to read and understand the tests and their meaning in a reasonable amount of time?)
  among others. Bear also in mind that a test suite needs a proper design in the same way as a normal application does, so any time you write test code you should also keep an eye on how easy it will be to make it evolve together with the program it is testing.
• A good practice is to keep the number of assertions per test case as low as possible to enforce that what is said in the previous bullet. The ideal is to have one assertion per test case. Although this leads to lots of test methods, this is the ideal. Every test case tests a certain property, so if one case fails you know exactly which property failed.
• Scenarios in which multiple assertions are useful.
  • Logical expressions that are evaluated together. Imagine you have to assert that a&&b&&c is true. Then it makes sense to break

          assert(a&&b&&c);
          

    in

          assert(a);
          assert(b);
          assert(c);
          

    since this will make any defect more traceable.
  • Strong semantic coupling between expressions. You can have situations in which the multiple assertions make sense together because they prove a property. An example it could be proving that two queues have the same values with the exception of the last one in one of them: you can then factor the two assertion in a single method.

          public void myAssertion(Queue a, Queue b){
            assertEquals(a.size,b.size);
            a.dequeue();
            assertEquals(a,b);
          }
          

    Obviously, assuming that dequeue is bug free and Queue implements equals.
• Expected clauses. JUnit allows test-methods to fail with an exception, if it is explicitly is stated that this is expected to happen. So, if method m should throw a nullpointer exception if it gets the argument null as input, this can be tested with the test case:

  @Test(expected = NullPointerException.class)
  void testM() {
    m(null);
  }
  

3 c) Derive test cases which have full statement coverage.

3 d) Look at the specification you wrote so far and think about what they have in common.

Exercise 4

Consider this method:

  public static void f(Object x, Object[] arr) {
    int i;
    boolean exists = false;
    
    for (i = 0; i < arr.length; i++) {  // A1
      if (x.equals(arr[i])) {           // B1
        exists = true;
        break;
      }                                 // B2
    }                                   // A2
    if (!exists)                        // C1
    {
      for (i = 0;; i++) {               // D1
        if (arr[i] == null) {           // E1
          arr[i] = x;
          break;
        }                               // E2
      }                                 // D2
    }                                   // C2
  }

Someone wrote this specification for f:

4 a) The precondition (requires) can be made weaker. How?

4 b) The postconditions (ensures) can be made a bit stronger. How?

4 c) Derive test cases which together have full path coverage up to and including repeating for-loops twice.

Exercise 5

We are going to specify and test an implementation of an algorithm called "Dutch National Flag". The algorithm can sort arrays arr of integers coming from the set {1,2,3} in linear time.

Example: Given the array

arr = {2,3,3,3,1,1,2,3,2,2,1,1,1}

arr = {1,1,1,1,1,2,2,2,2,3,3,3,3}

Here is the code:

  public static void dnfsort(int[] arr) {
    int a = 0, b = 0, c = arr.length;
    
    while (b < c) {
      if (arr[b] == 1){
        arr[b] = arr[a];
        arr[a] = 1;
        a = a+1;
        b = b+1;
      } else {
        if (arr[b] == 2) {
          b = b+1;
        } else // arr[b] should be 3 here
        {
          c = c-1;
          arr[b] = arr[c];
          arr[c] = 3;
        }
      }
    }
  }

5 a) What would be a suitable precondition of this code?

5 b) Here is a proposed postcondition of the code, expressing the sortedness of the result:

5 c) Using the precondition and postcondition you have now expressed, systematically derive test cases.

5 d) Looking at the code, construct a set of test cases such that full statement coverage is reached.

5 e) What are the branching points in the program? Construct a set of test cases such that full branching coverage is reached.

5 f) Give an example of a path through the program that is not covered by any of the above test cases.