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