Results 1 to 6 of 6

Thread: Invariant?

  1. #1
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default Invariant?

    I was doing some practice problems on Linked Lists and I saw this question: "Which of the following does not satisfy the loop invariant for the while loop?"

    My question is, what does invariant mean? I know it means constant in English, but what does it mean in math/computer science? I googled it and all this crap about predicate in mathematics came up. Wikipedia isn't really noob-friendly so I thought I post it here. Any help is appreciated and thanks in advance!

    P.S. Let me know if posting the whole question will be beneficial.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

  3. #3
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    5

    Default

    Yes, seeing the whole question would help.

    But I can elaborate on the definition of loop invariant for you; basically, it's a condition that's true when entering into a loop and remains constant through an entire loop.

    Java Code:
    int i = 1;
    while (x < 5) {
         x++;
    }

    Here's a list of loop invariants:
    • true
    • x < 5
    • x > 0

    Here are some examples of loop variants (things that are NOT loop invariants; that is, they change during execution):
    • x == 3
    • x == 4
    • x < 2


    Remember to note: the conditions for a while loop (in the code above, "x < 5") are ALWAYS loop invariants, as the loop terminates once their value has changed.

    I hope this helps a bit, Wikipedia actually has an entry on loop invariants you can find here. (I know you mentioned that Wikipedia isn't noob-friendly, but ignore the formulae and such and you'll get down to the actual concept beneath them.)

    Good luck!

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by Zack View Post
    But I can elaborate on the definition of loop invariant for you; basically, it's a condition that's true when entering into a loop and remains constant through an entire loop.
    Yep. Listen to Zack, not my answer. In fact, I'm going to delete it.

  5. #5
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    So a loop invariant is basically like a boundary on a variable before and after execution? Like what is the worse and best case scenario of a variable after it goes through some loop. Also, why is true in the list of invariants?

    lol Fubarable I didn't even get a chance to read it. It's the thought that counts so thanks! :)
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  6. #6
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    5

    Default

    Quote Originally Posted by Lil_Aziz1 View Post
    So a loop invariant is basically like a boundary on a variable before and after execution? Like what is the worse and best case scenario of a variable after it goes through some loop. Also, why is true in the list of invariants?
    true is in the list because its value never changes. I could also put 7, false, 13.3f, and so on, because they have constant values. 7 will be 7 before the loop and after the loop, no matter what you do. ;)

    Think of it like this:

    (Top row is the iteration; left column is the statement evaluated for each iteration.)
    Here I've put in red the loop variants, and the blue lines are loop invariants. Notice that in the red lines, you will see more than one value (i.e. it's not all true or all false). Hence, the value of that boolean statement is variant.

    I hope that helps explain it a bit; if not I'll give it another whack. ;)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •