Previous page Next page Navigation bar

Puzzles

In memoriam: Edsger W. Dijkstra

Introduction

Edsger Wybe Dijkstra died on 6 August 2002. He was one of the brightest luminaries of the computer science cosmos. The University of Texas at Austin has placed a number of his writings on the web. Perusing these writings, or any of Dijkstra’s articles or several books, gives one a sense of the magnitude of the loss experienced by the computer science world.

Dijkstra is perhaps most famous among practitioners for one of his shortest works. His letter to the editor, “Go To statement considered harmful,” in the Communications of the ACM, was at the time highly controversial. This letter crystallized the disputes among practitioners that eventually resulted in the widespread adoption of structured programming. Structured programming in turn led to current techniques such as abstract data types, object based programming, and object oriented design.

Dijkstra famously said, “Computer Science is no more about computers than astronomy is about telescopes.” Despite this, the thought processes we go through to use our tools are shaped by the tools themselves. It is only fair that we acknowledge those who created the conceptual frameworks we use. Just as we call a sequential stored program computer a “von Neumann” machine, we should call our block-structured computer languages “Dijkstra-Wirth languages” in honor of ALGOL and Pascal, and perhaps our programming methods “Dijkstra methods.”

In honor of Dijkstra, and in memory of his contributions, this section considers a mathematical puzzle posed in one of his famous “EWD” series of papers. The puzzle is derived from EWD1301, “The river, the isles and the bridges.”

Problem Statement

The problem statement is:

In a river lie 6 isles, connected by 13 bridges to each other and the shores as follows:

Diagram of 13 bridges connecting 2 shores and 6 islands

When in a storm each bridge has a probability ½ of being swept away, what is the probability that the shores remain connected?

Dijkstra elegantly proved the probability the shores remain connected is ½. This site has a computational focus: we will compute the answer to this question. We will also address Dijkstra’s dislike of his solution as an “isolated ingenuity” by answering a family of similar questions.

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
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

Your Privacy

Site Map

E-mail

Site Technical Data