1. For the following program:
public int kcl(int x, int y){ int a;
int b;
while(𝑦 ≤ 10){
a = x*y; b = y-x; y++;
}
return a; }
7CCSMASE
Tutorial 4
• Draw the control flow graph (you can take the one you drew in the previous tutorial) and annotate the nodes of the CFG to indicate the definitions/uses of variables a, x and y.
• Draw the data dependence graph for this program.
• Draw the control-dependence graph for this program.
2. Consider the following simple program (in no particular language) to find the smallest prime factor of a number:
smallest(int p) /* precondition p > 1 */ {
int q = 2;
while(p mod q > 0 AND q < sqrt(p) )
q := q+1
;
if (p mod q = 0)
then
print(q,''is the smallest factor'') else
print(p, ``is prime'')
;
}
• Draw the control flow graph for this program and annotate the nodes to indicate the definitions/uses of variables p and q.
• Label the nodes and give All DU Paths for p and q. (A du-path from node x to node y for a variable v is a simple path from x to y which is definition clear for v and which assigns to v at x and uses v at y)
3. Suppose test suite A satisfies adequacy criterion C1. Test suite B satisfies adequacy criterion C2, and C2 subsumes C1. Can we be certain that faults revealed by A will also be revealed by B?
4. Consider the program below:
1 /** Find the two roots of ax^2 + bx + c,
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 a)
b) c)
* that is, the values of x for which the result is 0. */
class Roots {
double root one, root two; int num roots;
public roots(double a, double b, double c) { double q;
double r;
// Apply the textbook quadratic formula: // Roots = -b +- sqrt(b^2 - 4ac) / 2a
q = b*b - 4*a*c; if (q > 0&&a!=0) {
// If b^2 > 4ac, there are two distinct roots num roots = 2;
r=(double) Math.sqrt(q) ; root one = ((0-b) + r)/(2*a); root two = ((0-b) – r)/(2*a);
} else if(q==0) { // (BUG HERE)
// The equation has exactly one root
num roots = 1;
root one = (0-b)/(2*a);
root two = root one; } else {
// The equation has no roots if b^2 < 4ac num roots = 0;
root one = -1;
root two = -1;
num roots() { return num roots; } public double first root() { return root one; }
The program crashes at line 22 - what are its pre and post dominators? What can be the source of the fault?
For the program above, compute the probability of selecting a test case that reveals the fault in line 19 of program Root by randomly sampling the input domain, assuming that type double has range −231 ... 231 − 1.
For the program above, compute the probability of randomly selecting a test case that reveals a fault if lines 13 and 19 were both missing the condition a ≠ 0.
} }
public int