Quiz

Question

If the do-od loop, below, solves a problem then does the while loop, below, also solve the same problem? Why?

do-od loop

do
   g0 -> c0
   g1 -> c1
od

while loop

while (g0 OR g1):
   if g0 then c0
   if g1 then c1

or in Python notation:

while (g0 OR g1):
   if g0: c0
   if g1: c1

Answer

Yes, the while loop also solves the problem. Let the statements in the while loop be s0 and s1. The sequence of statements executed in the while loop are

s0; s1; s0; s1; s0; s1; ....

until not(g0 or g1).

In this sequence, drop the statements for which the if clause is False; the resulting sequence is a possible sequence of statement executions for the do-od loop. Since all possible statement executions of the do-od loop solves the problem, the while loop also solve the problem.

Question

Does the following loop always, sometimes, or never terminate? Explain.

x = 2
do
   x >= 1   ->  x = x - 1
   x == 1   ->  x = x + 1
od

Answer

The loop terminates for some, but not all, executions.

Let the statements in the loop be s0 and s1, in order. Here is a sequence that does not terminate: repeat s0;s1 forever.

{x = 2} s0 {x = 1} s1 {x = 2} s0 {x = 1} s1 {x = 2}..

And here is a sequence that does terminate: s0; s0

{x = 2} s0 {x = 1} s0 {x = -1}

---

K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology