Testing, Debugging, and Verification | TDA567/DIT082, LP2, HT2018 |
Exercises week 1 and 2 - Testing | |
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.
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:
specification for method f
requires: x and arr are non-null and there is an element in arr which is null ensures: when f returns there is an element in arr which is equal to x 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
Example: Given the array arr = {2,3,3,3,1,1,2,3,2,2,1,1,1}the algorithm sorts the array, producing: arr = {1,1,1,1,1,2,2,2,2,3,3,3,3}When the array contains other numbers than 1, 2 or 3, the result is unpredictable. 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:
ensures:
What part of the behaviour of the algorithm does this postcondition not express?
when dnfsort returns then for all pairs of adjecent elements, say arr[i] and arr[i+1], it holds that arr[i] is less than or equal to arr[i+1]. 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. | |
Home | Course | Schedule | Exam | Exercises | Labs | Evaluation | Tools | Links | Srinivas Pinisetty, Nov 9, 2018 |