# Puzzles

## In memoriam: Edsger W. Dijkstra

### Program Extension 1

Suppose we wanted to determine the probability of the two shores being connected, when the probability each bridge remains standing is some probability other than ½.

Suppose the probability each bridge remains standing is p. Then the probability each bridge has been removed is 1-p. The probability associated with a particular set of bridges remaining standing is the product of a p for each bridge that remains standing, and a 1-p for each bridge that has been removed. If we say k is the number of bridges remaining standing out of n bridges, then the probability is:

Now, this probability does not depend on which bridges remain standing, just on the number of bridges that remain standing.

Currently, the program increments a single counter whenever it discovers a subset of bridges which leave the two shores connected. Suppose that instead of a single counter, there were a vector of counters, M = (mk), indexed by the number of bridges k in the subset. Then the probability P of the shores remaining connected is a function of the probability p of a given bridge remaining, as follows:

As with a previous “mathematical diversions” note (you did read those, didn’t you?), the capital sigma means to take the sum of the quantities expressed; the “i=0” and “n” limits on the sigma indicate that the index variable i is taken to vary from 0 to n. The sigma notation is just mathematical notation to indicate accumulating a sum with an iteration.

Note that the mi values do not depend on the value of p. This means we can compute the vector M once, then use it to compute P(p) for any value of p.

There are two questions that arise here. The first question is how we determine the number of bridges standing, so that we can increment the correct element of the vector of counters M. The second question is how we should display a result that is a function, rather than a value.

List 2 has a set of boolean values that indicate which bridges are standing in the set of bridges being considered. These boolean values are 0 to indicate bridges which have been removed, and 1 to indicate bridges that are present. Therefore, the sum of the elements in List 2 is a count of the number of bridges present in the subset of bridges being considered. Fortunately, the calculator lets us form the sum of the elements of a list simply, with the Sum operator.

The obvious way to display a function is to graph it. The domain of the function is a probability in the range 0 to 1. The range of the function is similarly a probability in the range 0 to 1. The program can graph the function by evaluating P(p) at each of an increasing (for example) sequence of p values, plotting each (p, P(p)) point, and drawing a line between the points corresponding to each adjacent pair of p values. Fortunately, the calculator has Plot and Line commands that do much of the work for us.

In order to plot the function, however, we need to compute it. Looking at the equation of P(p) above, we see it is a sum of a number of terms. So we have a collection of items, and we want to determine a property (the sum) of the collection as a whole. We can use the trick of the trade about properties of collections as a whole to have the program iterate through the collection of terms, accumulating a “sum of terms seen so far” value; when the program reaches the end, the “sum of terms seen so far” will be the “sum of all terms.” This computation follows the following flowchart:

The variables referenced in this flowchart are named for mnemonic reasons: i is an index of terms, s is a sum of terms, and t is a term. The value n is, as before, the number of bridges present before the storm..

There is one potential problem with this computation: the calculator refuses to compute 00. All of p, 1-p, i, and n-i are at some point or another zero. By convention, x0 has the value 1 for all values of x, including 0; and 1 is the multiplicative identity. So we can compute the term t by the following somewhat cumbersome process:

Now we are ready to modify the program. First, we use List 4 to hold the vector M, and initialize all the elements to 0:

Seq(0,A,1,Dim List 1, 1)→List 4

We need to add this statement at the front of the program with all the other list initialization. We can also delete the statements

0→D
0→E

as the program will not be using a ratio for a probability.

Note that our M vector is actually 0-indexed, while the List is 1-indexed. As it happens, though, m0 is always zero: if no bridges remain standing, there is no way to get across the river. As long as we do not attempt to access m0 — and knowing it is always 0, there is no reason to access it — we should not get into trouble.

Now, we need to replace the statement

D+1→D

This was incrementing the number of combinations of bridges that connected the two shores. We change the program to keep a vector of counts.

Sum List 2→D
List 4[D]+1→List 4[D]

We also delete the statement

E+1→E

Finally, we need to replace the last statement of the program. Formerly, it computed the (single) value of the probability and had the calculator produce it. What we would like to do instead is produce a graph of the probability function P as a function of p.

First, we initialize the graph view window.

ViewWindow 0,1,.25,0,1,.25

We will arbitrarily use 50 steps to graph the probability, and put the step index into A.

For 0→A To 50

The probability value p being considered is the step index, divided by the number of steps. Note that we started the step index (variable A) at 0, so the values of the probability value p will be 0, 0.02, 0.04, ..., 0.98, 1. We put the probability value p into B.

A÷50→B

We will compute the probability P as the sum of a set of terms; the program has yet to see any terms, so the sum is 0. We put the sum into C.

0→C

Now we compute each term, using D as the summation index and E as the term value.

For 1→D To Dim List 1
List 4[D]→E
(B^D)E→E
If D≠Dim List 1
Then ((1-B)^(Dim List 1-D))E→E
IfEnd
E+C→C
Next

The code has only one conditional inside the loop, rather than two. This is because the flowchart assumed we were adding terms with indices from 0 to n, as we should. However, the code is written with the count vector M being 1-based, rather than 0 based; m0 is zero. Therefore the index of terms starts at 1, rather than 0, and so p0 cannot occur. As it cannot occur, we omit the test guarding against it.

Now we plot this P value against the p value.

Plot B,C

Unless this is the first P value, we connect this new point to the previous point with a line.

If A≠0
Then Line
IfEnd

That is all we need to do for this value of p.

Next

We run this modified program, and after several hours the program produces the following graph:

This is what we wanted.

But wait! We can do more!

Page last updated 10 April 2006.

# Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

In memoriam: Dijkstra

Introduction

Interpretation

Plan, part 1

Plan, part 2

Code

Extension 1

Extension 2

Final Modification

Bridge Collections

Site Information