CS 1110 Introduction to Computing using Java    Fall 2010  
9367 TR 09:05 Hollister B14 Instructors: David Gries and Lillian Lee  
9369 TR 11:15 Hollister B14 Grade: letter or S/U.   Credits: 4
 

 

Quiz 3

Answer to Quiz 3

// Set x to the sum of the primes in 2..n-1
x= 0;

// invariant inv: x is sum of primes in 2..k-1
for (int k= 2; k <= n; k= k+1) {
      if (k is a prime)
          x= x + k;
}
// post: x is sum of primes in 2.. n-1

A: initialization doesn’t make inv true
B: Postcondition not true at end
C: Not always progress toward termination
D: Repetend doesn’t keep inv true
E: All 4 loopy questions satisfied

The answer is B. The loop terminates with k = n+1, and with k = n+1, the invariant indicates that

      x is the sum of primes in 2..n.

The loop condition should be k < n .



// Set x to the sum of the primes in 2..n-1

k= 2; x= 0;
// invariant inv: x is sum of primes in 2..k-1
while (k < n) {
     if (k is a prime) {
          x= x + k;
          k= k + 1;
    }
}
// post: x is sum of primes in 2.. n-1

A: initialization doesn’t make inv true
B: Postcondition not true at end
C: Not always progress toward termination
D: Repetend doesn’t keep inv true
E: All 4 loopy questions satisfied

The answer is C. If k is not a prime, the statement k= k+1 is not executed, so k is not incremented in that iteration, and progress toward termination is not made. This is an infinite loop if 3 < n.