Thread: Computer Science GRE subject exam

How on earth does the loop terminate in question 15?

k = floor(k / 2), when repeated, will cause k to become 0, thus terminating the loop. (Unless of course k is negative, but you can rule this out due to the explicitly stated invariant k >= 0)

Question 15 is very simple if you just ignore all the unnecessary information. All you need to know is:

Code:

Invariant:  z*x^k = b^n  and  k >= 0
...
while (k != 0)
...

Clearly the only way this loop terminates is when k is zero. Substitute 0 for k in the invariant, and you get the answer.

Code:

z*x^0 = b^n
z*1 = b^n
z = b^n

Also:

Think of a the loop invariant as any condition that must remain true on entry and during all iterations of the loops.

Using the terminology from question 14 of this practice GRE: "A loop invariant for a while statement is an assertion that is true each time the guard is evaluated during the execution of the while statement." The invariant does NOT have to be true at any arbitrary point in the body of the while loop, only before the body begins and after the body ends. I'm pretty sure you already know this, but I felt that statement needed some more exactificationness.

[edit]
Also, a loop can certainly have more than one invariant. In fact, I believe all loops have an infinite number of invariants.
[/edit]