CPSC 333: Lab Exercise #9: Unit Testing

Location: [CPSC 333] [Lab Exercise] [Previous Exercise] [Next Exercise] Exercise #09

The following exercise will be taken up in labs during the week of March 31 - April 4. If at all possible, you should try to solve these problems ahead of time, so that you can compare your own solutions to the ones presented during labs, or have questions ready to ask in case you had trouble solving them.

This is based on material presented in class on March 26-31.

Consider the following "binary search" algorithm.

Inputs:

• n, the length of the following array.
• A, an integer array with entries A[1], ..., A[n] such that A[i] < A[i+1] for i between 1 and n-1
• key, an integer

Outputs: index, an integer between 0 and n such that

• if index = 0 then key does not equal any entry of the array A
• if index is between 1 and n then A[index] = key

Local Variables:

• low, medium, high: integers
• found: boolean

    1.     found := false
    2.     low := 1
    3.     high := n
    4.     while ((low is less than or equal to high) and not found) do
    5.       medium := floor((low + high)/2)
    6.       if A[medium] = key then
    7.          index := medium
    8.          found := true
    9.       else
   10.          if A[medium] < key then
   11.            low := medium + 1
   12.          else
   13.            high := medium - 1
   14.          end if
   15.       end if
   16.     end while
   17.     if not found then
   18.       index := 0
   19.     end if

1. Construct a flow graph for this program. What is the cyclomatic complexity of this program (and its flow graph)?
2. Use the guidelines for path testing, condition testing, and loop testing, to design a set of test cases for this program. For loop testing, you may assume the program will be run in practice using arrays of size between 1 and 1000.

Location: [CPSC333] [Lab Exercises] [Previous Exercise] [Next Exercise] [Exercise #9]