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.”
The problem statement is:
In a river lie 6 isles, connected by 13 bridges to each other and the shores as follows:
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.
Copyright © 2002 Brian Hetrick
Page last updated 10 April 2006.