CS100A, Fall 1998, Review of Loops and Loop Invariants
Some students are still having trouble understanding loop invariants and developing a loop when the desired result and loop invariant are given. This handout is aimed at removing that trouble. Read it carefully and do the exer-cises in this handout. If there is anything you don’t un-derstand, see an instructor or TA or consultant immedi-ately.
Important. Remember: a loop invariant is nothing more than a definition of the variables that are used in the loop, which shows the relationship between them. This defin-ition holds before and after each iteration of the loop.
Checklist: We give a checklist for understanding a loop. Memorize it. It shows you how to understand loops, and it is also used to develop loops. The nice thing about the loop invariant is that it allows us to develop the initi-alization, the loop condition, and the loop body basically independently of each other. For the following loop with precondition Q and postcondition R to be correct,
1. The initialization should truthify P.
2. If B is false, then with the help of P we see that result R is true.
3. Each iteration makes progress toward termination (gets closer to the point where B is false).
4. Each iteration keeps P true.
Example: Linear search looks for x in b[0..m-1]. The result postcondition R is
x is not in b[0..h-1] and
Initialization: To make P true, store in h to make the
first section empty: h= 0;
Loop condition: The loop should continue as long as the second array section is not empty and x doesn’t equal b[h]:
Get closer to termination: h= h+1;
Keep P true: nothing to do.
while (h != m && x != b[h])
Important hint! Memorize:
* Array section b[h..k] has one element if h = k.
* Array section b[h..k] is empty if h = k+1.
Important point. Practise!!
Some of you have difficulty determining when some of the four array sections given below are empty:
In order to determine whether a section is empty, first put it in the form b[a..b] and then use the important hint given above. Example: The right most section is b[n+1..m-1].
It is empty when n+1 = m-1+1, i.e. when n= m-1.
Practice determining when a section is empty and when it
has one element until your can do it in your sleep.
How to study this material on loops.
1. Study the previous page and memorize everything that it says to memorize.
2. Memorize the following definitions (you have to know them for the final, anyway) that concern a loop