View Poll Results: What was your scaled score?

Voters
5. You may not vote on this poll
  • 850 <= score < infinity

    1 20.00%
  • 800 <= score < 850

    1 20.00%
  • 750 <= score < 800

    1 20.00%
  • 700 <= score < 750

    1 20.00%
  • 650 <= score < 700

    1 20.00%
  • 600 <= score < 650

    0 0%
  • 550 <= score < 600

    0 0%
  • 500 <= score < 550

    0 0%

Computer Science GRE subject exam

This is a discussion on Computer Science GRE subject exam within the General Discussions forums, part of the Community Boards category; How on earth does the loop terminate in question 15? k = floor(k / 2), when repeated, will cause k ...

  1. #16
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    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]
    Last edited by arpsmack; 04-08-2010 at 07:46 PM.

  2. #17
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,510
    Quote Originally Posted by arpsmack View Post
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #18
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    Quote Originally Posted by arpsmack View Post
    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
    My Website

    "Circular logic is good because it is."

  4. #19
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Mario F. View Post
    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).

  5. #20
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    Quote Originally Posted by DavidP View Post
    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!!!!!!

  6. #21
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,510
    Quote Originally Posted by tabstop View Post
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  7. #22
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by DavidP View Post
    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 View Post
    [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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Computer Science Exam Tomorrow!!!
    By cozman in forum C++ Programming
    Replies: 14
    Last Post: 05-23-2002, 08:23 AM
  2. The best university for computer science
    By Unregistered in forum A Brief History of Cprogramming.com
    Replies: 19
    Last Post: 04-18-2002, 12:42 AM
  3. computer science or computer engineering??
    By pkananen in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 02-26-2002, 11:10 AM
  4. computer science rant
    By cozman in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-10-2001, 11:02 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21