-----------------------------------

raptors892004

Tue Dec 19, 2006 9:54 pm


stacks and invariants

-----------------------------------

In the info i got from a slideshow it says:


the link member in the bottom (last) node of the stack is set to null to indicate the bottom of the stack

From searching on the wikipedia website:
record Node {
    data // The data being stored in the node
    next // A reference to the next node; null for last node
 }


,and before that comparing to a linked list, I think it should be that the pointer to the next node of that last (bottom) node is set to null, right? Or am I wrong? :D

My other question is what are invariants and what are they used for? I hope you respond by tmr because I gotta know this before the quiz because it wasn't explained very well in the provided information.

Thanks for any replies in advance.


-----------------------------------

OneOffDriveByPoster

Tue Dec 19, 2006 11:23 pm


Re: stacks and invariants

-----------------------------------

,and before that comparing to a linked list, I think it should be that the pointer to the next node of that last (bottom) node is set to null, right? Or am I wrong? :D

Sounds right.  The slideshow said as much though (okay, maybe you had a stack of pointers...).

My other question is what are invariants and what are they used for?
Invariants are things that do not change (where they are invariant).  You could use them in assertions to check things.

There are other things you could do with them (any more specific ways to describe an invariant), but I think you need to give more info.  Any links to the information you got?


-----------------------------------

raptors892004

Tue Dec 19, 2006 11:42 pm



-----------------------------------

I had some info on loop invariants and four steps to develop a loop from a loop invariant which didn't seem to connect very much (except step 4) to the loop invariant concept i think, but oh well.. 

1.Set initial values for any loop control variables.
2. Determine the condition that causes the loop to terminate.
3. Modify the control variable(s) so the loop progresses toward termination.
4. Check that the invariant remains true at the end of each iteration.

Another thing the slideshow said is that invariants  should be used to test programs thoroughly.


-----------------------------------

OneOffDriveByPoster

Wed Dec 20, 2006 9:06 am



-----------------------------------

... four steps to develop a loop from a loop invariant...
Interesting.  So you are saying that given a loop invariant, you want to develop/implement a loop that satifies the invariant?

1.Set initial values for any loop control variables.
2. Determine the condition that causes the loop to terminate.
3. Modify the control variable(s) so the loop progresses toward termination.
4. Check that the invariant remains true at the end of each iteration.
Assuming a response in the affirmative to the above question, these steps are probably okay--but they are less steps, but more things you have to consider.  In fact, you need the first three for practically any loop.

"Step 4" is actually much more than it can appear to be.  The key could be to consider what side-effects the loop should have (if any) such that the invariant will be true at the end of each iteration.  (As far as I know, it should also be true going into the loop--that is, true before the loop starts).

Another thing the slideshow said is that invariants  should be used to test programs thoroughly.
That is where the bit about the "assertions" comes from in my previous response.