# Software Test

A

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
B

Implement JUnit test cases that test the string compare algorithm.

C

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 */
}
```