Software Test

A brute force algorithm for testing in a string X is a substring of another string Y is the following.

    public static boolean stringCompare(String x, String y){
        boolean result = false;
        int m = x.length();
        int n = y.length();
        int i, j;
        
        /* Searching */
        for (j = 0; j <= n - m; ++j) {
            for (i = 0; i < m && x.charAt(i) == y.charAt(i + j); ++i);
            if (i >= m)
              result = true;
       }
       return result;
    }

• Understand what the algorithm does (what is the worst-case complexity of the algorithm?)
• Draw the basis path coverage graph for the above algorithm
• Determine the cyclomatic complexity of the graph

Implement JUnit test cases that test the string compare algorithm.

Your business partner has developed a function that can determine if two intervals overlap, e.g., the interval [12,25] overlaps the interval [15,20] but the interval [6,9] does not overlap with the interval [14,23]. The source code for the overlap function is not available (we are assuming closed integer intervals, e.g., both 6 and 9 are in the interval [6,9]. You think that the function is not working properly. Describe the minimal input to black-box test this overlap function. Assume that the function header is like the following.

    public boolean overlap(int startA, int stopA, int startB, int stopB) { 
      /* body */
    }