CSci 151: Foundations of computer science II
Home Syllabus Assignments Tests

printable version

Quiz 2

[1] [2] [3]

Problem Q2.1.

[10 pts] Below is a fragment for computing the first factor of a number n. The loop maintains the invariant that p = i ⋅ j. Suppose that at the beginning of one iteration, the invariant holds at that instant, with a representing the value of i, b the value of i, and q the value of p; thus, we know q = a ⋅ b. Argue for why the invariant will still be true at the end of that iteration.

int i = 2;
int j = n - 1;
int p = j + j;
while(p != n && i <= j) {
  if(p < n) { i++; p += j; }
  else      { j--; p -= i; }
}