Archive for September, 2013

There is less than a 1% chance that your program is correct … program contains 500 components and each component has a 99% chance of being correct

September 28, 2013

As we build ever larger and more powerful systems it becomes ever more important that those systems, and the components of which they are made, should be transparently simple and self-evidently correct. As Professor Dijkstra points out (Structured Programming, Academic Press 1972):

                If the chance of correctness of an individual
                component equals p, the chance of correctness
                of a whole program, composed of N such
                components, is something like

                                P = pN

                As N will be very large, p should be very, very
                close to 1 if we desire P to differ significantly
                from zero!

The purpose of this book is to present a coherent method and procedure for designing systems, programs and components which are transparently simple and self-evidently correct.

                Principles of Program Design
                by M.A. Jackson

Example: Suppose the chance of correctness of an individual component is 99% (p=0.99) and the program is composed of 500 such components (N=500). The chance of correctness of the program is

                                P=(0.99)500
                                               
P = 0.007

There is less than a 1% chance that the program is correct!

Learning for the sheer love of it … determining the number of edges in a complete graph

September 7, 2013

As I noted in an earlier blog, even little discoveries makes one feel wonderful. Today I solved a small problem (i.e., made a little discovery) and I feel wonderful.

I am reading a wonderful book, Introduction to Graph Theory. I am at the part where it describes complete graphs. A complete graph is one where each vertex is connected to every other vertex. The author asks, How many edges are in a complete graph with N vertices? I took this as a challenge to use my reasoning skills to figure it out.

Here are three examples of complete graphs and the number of edges in each graph:

Three examples of complete graphs and the number of edges in each graph

Let’s arbitrarily choose one vertex. It must connect to the other (n-1) vertices. For example, in the complete graph with 4 vertices, the vertex will connect to the other 3 vertices:

A vertex connects to n-1 other vertices

The remaining vertices must form a complete graph amongst themselves. Ah Ha! Now we have a simpler problem: find the number of edges in a complete graph of n-1 vertices.

I now switch on my programmer hat. I smell recursion (which I love):

numEdges (N) {
    if (N == 2) then return 1
    else return (N-1) + numEdges (N-1)

Let’s check that program:

if N = 2, then num edges = 2
if N = 3, then num edges = 2 + 1 = 3
if N = 4, then num edges = 3 + 3 = 6
if N = 5, then num edges = 4 + 6 = 10
if N = 6, then num edges = 5 + 10 = 15
if N = 7, then num edges = 6 + 15 = 21
if N = 8, then num edges = 7 + 21 = 28

Wow! That is cool.

One problem, however. What are the number of edges when, say, N = 1000?

I could implement the above program and set it to solve N=1000. But I know the mathematicians would tell me: Find a formula.

Okay, let’s see … to find the number of edges in a complete graph with N vertices, I must add these numbers:

(N-1) + (N-2) + (N-3) + … + 1

or equivalently:

1 + 2 + … + (N-1)

I remember from school days a formula for the sum of the first N integers:

n(n+1)/2

Of course, I want the sum of the first N-1 integers, so I substitute “n” with N-1:

(N-1)((N-1)+1)/2
= (N-1)(N-1+1)/2
= (N-1)(N)/2
= N(N-1)/2

Let’s check:

if N = 2, then 2(1)/2 = 1
if N = 3, then num edges = 3(2)/2 = 6
if N = 4, then num edges = 4(3)/2 = 6
if N = 5, then num edges = 5(4)/2 = 10
if N = 6, then num edges = 6(5)/2 = 15
if N = 7, then num edges = 7(6)/2 = 21
if N = 8, then num edges = 8(7)/2 = 28

Yea!

I am pretty proud of myself. I solved it, not because it was a homework problem or a work problem. I solved it purely for the love of learning. I figured it out by simple reasoning.

I feel wonderful.

Body temperature after a hard workout and body temperature after soaking in a cold bath

September 7, 2013

Lately I have been taking a cold bath each evening. As the weather gets cooler it is becoming more and more difficult to motivate myself to continue taking the cold baths, even though I feel fantastic after taking them.

So today I decided to take a different tact: I would take a cold bath immediately after working out.

I did a hard workout and by the time that I was done I was sweating pretty good; then I immediately jumped into a cold bath that I had previously prepared, and soaked in it for 15 minutes. Ah, I felt wonderful.

Now this is really interesting: I took my body temperature immediately after working out (before jumping into the cold bath) and it was 94.1 degrees. Then I took my body temperature immediately after soaking in the cold bath for 15 minutes and it was 97.1 degrees. Isn’t that fascinating? Apparently, when one works up a sweat, the body responds by cooling down the inside; and when one cools the outer body, the body responds by heating up the inside.

There is discovery in solving every problem

September 2, 2013

A great discovery solves a great problem,
but there is a grain of discovery in the solution
of every problem. Your problem may be modest,
but if it challenges your curiosity and brings into
play your inventive facilities, and if you solve it
by your own means, you may experience the
tension and enjoy the triumph of discovery.

George Pólya, How To Solve It

Think better and deeper thoughts while walking

September 1, 2013

Today (Sunday morning) I went for a 90 minute walk through a nice nature trail with a friend.

During the walk we discussed varied topics, such as the three theories of aging and the moving blueberry harvest season.

It was a wonderful walk and a delicious discussion.

While walking it occurred to me that, “This is an ideal environment for discussing and exchanging ideas. Everyone is relaxed. The mild exercise makes my brain sharp.”

Contrast with sitting in a room, staring at each other across a table. That is a very uncomfortable environment. It puts pressure on everyone to try to be profound and sound intelligent.

I propose that all meetings be turned into walking meetings. The entire group should go outside and walk and talk. I suspect that meetings would be more productive that way.

I suggest that researchers could better explore deep problems if they spent more time discussing while walking.

I want to find someone interested in deep discussions on various topics in Computer Science, such as computability, complexity theory, parsing, XML. Actually, anything math- and science-related would be great. If you enjoy walking, deep thoughts, and live in the Boston to southern New Hampshire area please drop me a note.

From Mark Twain’s “A Tramp Abroad”:

“Now, the true charm of pedestrianism does not lie in the walking, or in the scenery, but in the talking. The walking is good to time the movement of the tongue by, and to keep the blood and the brain stirred up and active; the scenery and the woodsy smells are good to bear in upon a man an unconscious and unobtrusive charm and solace to eye and soul and sense; but the supreme pleasure comes from the talk. It is no matter whether one talks wisdom or nonsense, the case is the same, the bulk of the enjoyment lies in the wagging of the gladsome jaw and the flapping of the sympathetic ear.

And what motley variety of subjects a couple of people will casually rake over in the course of a day’s tramp! There being no constraint, a change of subject is always in order, and so a body is not likely to keep pegging at a single topic until it grows tiresome. We discussed everything we knew, during the first fifteen or twenty minutes, that morning, and then branched out into the glad, free, boundless realm of the things we were not certain about.”