# Computer Science GRE subject exam

Printable View

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 04-08-2010
arpsmack
Quote:

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:
Quote:

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.

Also, a loop can certainly have more than one invariant. In fact, I believe all loops have an infinite number of invariants.
[/edit]
• 04-08-2010
Mario F.
Quote:

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?

Quote:

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.
• 04-08-2010
DavidP
Quote:

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 :)
• 04-08-2010
tabstop
Quote:

Originally Posted by Mario F.
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?

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

m/n is 0 whenever m < n (well, it's 0 remainder m, but you didn't ask for the remainder part).
• 04-09-2010
arpsmack
Quote:

Originally Posted by DavidP
Yes. Clearly. :) I always hated it when my professors used that on us :)

Heh good point. Stupid unnecessary fluff words. And even worse is that in this particular instance I'm pretty sure my subconscious added "clearly" to give off that "OH MY GOD I'M SO SMART LOOK AT THE SIZE OF MY E-PENIS" vibe. I'm such a dick.

My personal pet peeve in that area is "note". Good god do some people overuse it.

Note that a > b in this situation.
Note that integers are numbers.
Note: errors are bad.
Note that I have a lot of notes.
Note that I'm a douche.

FFFFFFFFUUUUUUUUUUU!!!!!!
• 04-09-2010
Mario F.
Quote:

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.
• 04-09-2010
Sang-drax
Quote:

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.

Quote:

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.
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12