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]

Originally Posted by arpsmack

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)

Hmm... the thought occurred to me then that K would have to be a floating point variable. That's how I eventually ended up interpreting the pseudo code.

However its a well known fact that no division operation results in zero except when the dividend is 0 itself. So this means the comparison never turns out to be 0 in most languages we know and work with. It's probably safe to assume the pseudo-code means at first iteration where K < 1. But why not just write that and avoid the confusion?

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

Excellent. That was always a point of some confusion to me. Thanks.

Originally Posted by arpsmack

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

Yes. Clearly. I always hated it when my professors used that on us

Originally Posted by tabstop

m/n is 0 whenever m < n (well, it's 0 remainder m, but you didn't ask for the remainder part).

Yeah. Never occurred to me that was an acceptable practice in pseudo-code.

Originally Posted by DavidP

I should have skipped a lot of the questions I knew I didn't know, but I wanted to give an honest effort to each question...so I answered all of them. To be fair, if I had skipped questions that I knowingly didn't know (does that make sense?), I could have pushed myself up in the rankings a bit.

Originally Posted by tabstop

[If you let me skip, it ends up being +44 -9 =12, which gets me the exact same 820. Hooray guessing!]

The test is designed so that random guessing gives you 0 points on average. You should try to answer all questions because you can often rule out at least one option and then guessing will give you a higher score on average.