The Manuscripts of Edsger W. Dijkstra

496A: On-the-fly garbage collection: an exercise in cooperation (preliminary version) (with Leslie Lamport, A.J.Martin, C.S.Scholten, and E.F.M.Steffens)

496B: On-the-fly garbage collection: an exercise in cooperation (with Leslie Lamport, A.J.Martin, C.S.Scholten, and E.F.M.Steffens)

497: A challenge to memory designers?

498: How do we tell truths that might hurt?

499: [toespraak tot een student bij uitreiking ir-diploma]

05xx

500: After many a sobering experience

501: Variations on a theme: an open letter to C.A.R. Hoare

502: On a gauntlet thrown by David Gries

503: A post-scriptum to EWD501

504: Erratum and embellishments of EWD503

506: Tripreport E.W.Dijkstra: NATO Summer School Marktoberdorf 1975

507: On a gauntlet thrown by David Gries

508: A synthesis emerging?

509: Eerste toespraak, najaar 1975

511: Tripreport E.W.Dijkstra W.G.2.3, Baden, 1–5 September 1975

512: Comments at a symposium

513: Tripreport E.W.Dijkstra Newcastle, 8–12 September 1975

514: On a language proposal for the Department of Defense

515: Tweede toespraak, najaar 1975

516: Derde toespraak, najaar 1975

518: Vierde toespraak, najaar 1975

520: On-the-fly garbage collection: an exercise in cooperation (with Leslie Lamport, A.J.Martin, C.S.Scholten, E.F.M.Steffens)

521: Vijfde toespraak, najaar 1975

522: Zesde toespraak, najaar 1975

523: Zevende toespraak, najaar 1975

524: Review of “On the Feasibility of Software Certification”

525: On a warning from E.A.Hauck

526: Comments on “Woodenman” HOL Requirements for the DoD

527: On units of consistency

528: More on Hauck's warning

529: Achtste toespraak, najaar 1975

530: Negende toespraak, najaar 1975

531: Tiende toespraak, najaar 1975

532: An open letter to L.Bass

533: HOMO COGITANS

534: Elfde toespraak, najaar 1975

535: An answer to Jack Mazola

536: A sequel to EWD535

537: Twaalfde toespraak, najaar 1975

538: A collection of beautiful proofs

539: Mathematics Inc., a private letter from its chairman

540: Two views of programming

541: Dertiende en laatste toespraak, najaar 1975

542: [Toespraak tot twee afstudeerders]

543: Eerste toespraak tot mijn studenten, voorjaar 1976

544: An open letter to Ross Honsberger

547: Tripreport E.W.Dijkstra, England and USA, 3-26 January 1976

548: Tweede toespraak tot mijn studenten, voorjaar 1976

549: Derde toespraak tot mijn studenten, voorjaar 1976

550: A more formal treatment of a less simple example

551: Vierde toespraak tot mijn studenten, voorjaar 1976

552: Vijfde toespraak tot mijn studenten, voorjaar 1976

553: On a gauntlet thrown by David Gries

554: A personal summary of the Gries-Owicki theory

555: Aan de Raad van Advies

556: Zesde toespraak tot mijn studenten, voorjaar 1976

557: Zevende toespraak tot mijn studenten, voorjaar 1976

558: Achtste toespraak tot mijn studenten, voorjaar 1976

559: Negende toespraak tot mijn studenten, voorjaar 1976

560: Tiende toespraak tot mijn studenten, voorjaar 1976

561: A “non trip report” from E.W.Dijkstra

562: The effective arrangement of logical systems

563: Formal techniques and sizeable programs

564: A superficial book

564a: Aan de Raad van Advies, in tweede ronde.

565: Elfde toespraak tot mijn studenten, voorjaar 1976

566: Programming: from craft to scientific discipline

567: Twaalfde toespraak tot mijn studenten, voorjaar 1976

568: A programmer’s early memories

569: Dertiende en laatste toespraak tot mijn studenten, voorjaar 1976

570: An exercise for Dr.R.M.Burstall

571: A simple consideration with far-reaching consequences (DRAFT)

572: Tripreport E.W.Dijkstra, U.S.A. and U.K., 8 June - 10 July 1976

573: A great improvement

574: A letter to Professor Zohar Manna, 26 July 1976

575: To H.D.Mills, Chairman Software Methodology Panel

576: On subgoal induction

577: Tripreport E.W.Dijkstra, ECI-conference 9–12 August 1976, Amsterdam

578: More about the function “fusc” (A sequel to EWD570)

580: Waarom de onderafdeling der wiskunde zich met de informatica moet bezighouden

581: A somewhat open letter to Professor John McCarthy

582: A proof of a theorem communicated to us by S.Ghosh (with C.S.Scholten)

583: Eerste toespraak tot mijn studenten, najaar 1976

584: Tripreport E.W.Dijkstra, Poland and USSR, 4-25 September 1976

585: Tripreport E.W.Dijkstra, Tokyo, 28 Sep.—3 Oct. 1976

586: Tweede toespraak tot mijn studenten, najaar 1976

587: Derde toespraak tot mijn studenten, najaar 1976

588: Vierde toespraak tot mijn studenten, najaar 1976

589: Vijfde toespraak tot mijn studenten, najaar 1976

590: A first investigation of the crossflow computer

591: The problem of the maximum length of an ascending subsequence

592: A small note on the additive composition of variant functions

593: Zesde toespraak tot mijn studenten, najaar 1976

594: A parable

595: On-the-fly garbage collection: an exercise in cooperation (with Leslie Lamport, A.J.Martin, C.S.Scholten, E.F.M.Steffens)

596a: Tripreport E.W.Dijkstra, Copenhagen 10–12 Nov. 1976

597: Yet another note about termination

07xx

709: My hopes of computing science

710: When messages may crawl, II (A sequel to EWD708)

711: Trip report E.W.Dijkstra, Ithaca, Albany, Austin (Texas), 26/5 – 10/6 1979

712: Trip report E.W.Dijkstra, Antwerp, 24–29 June 1979

713: On a problem posed by W.H.J.Feijen

714: Trip report E.W.Dijkstra, Mission Viejo, Santa Cruz, Austin, 29 July – 8 September 1979

715: Trip report E.W.Dijkstra, Munich – London, 16–29 September 1979

716: A short talk to my students about money

717: An exercise in exposition

718: Assembly conventions for the EDSAC

719: On not duplicating volatile information

720: Why correctness must be a mathematical concern

721: The design of a state space with a useful structure (I)

722: A book review for the IBM Systems Journal

723: On W.H.J.Feijen’s solution for the lexicographic minimum of a circular list

724: Een gotspe

724E: A chutspa

725: Trip report E.W.Dijkstra, Liege, Nov.–Dec.1979

726: How Dutch Informatics fell between two chairs

727: Trip report E.W.Dijkstra, U.S.A. 12 Jan. – 2 Feb. 1980

728: A problem solved by Netty van Gasteren and me

729: On well-shaped mathematical arguments

730: On two types of infinite sets of infinite sequences (by the Tuesday Afternoon Club)

731: An experiment in mathematical exposition

732: The teachability of mathematical thinking (Draft contribution to “Mathematics Tomorrow”)

733: Naar aanleiding van Experimentele post-propadeuse opleiding voor informatica-ingenieur aan de THE” (Eindhoven februari 1980 SOO/jc/sdb)

734: The superfluity of the general semaphore

735: A mild variant of Combinatory Logic

736: Recording the structure of trees in their leaves

737: A notational alternative for quantification

738: More mathematical folklore

739: A somewhat open letter to the Editor-in-Chief of Acta Informatica

740: A short proof of one of Fermat’s theorems

741: Partitioning the edges of the complete graphs into trees or cycles (by the Tuesday Afternoon Club)

742: A sequel to EWD740

743: A new policy for Mathematics Inc.?

744: A short note on symmetric distributed arbitration

745: Trip report E.W.Dijkstra, Los Angeles, Austin (Texas), and Portland, 6–28 August 1980

746: Trip report E.W.Dijkstra, Newcastle-upon-Tyne, 1–5 Sep. 1980

747: Comments on MIL–STD–1862, 28 May 1980

748: A somewhat open letter to Wladislaw M.Turski

749: On the productivity of recursive definitions

750: American programming’s plight

751: Mainly on the omission of parentheses

752: Distributed Arbitration (DRAFT, with C.S.Scholten)

753: On a theorem by Lambek and Moser

754: An error in EWD744

755: Very elementary number theory redone

756: A postscript to EWD755

757: A misguided educational effort

758: An intriguing example

759: A somewhat open letter to D.A.Turner

760: A somewhat open letter to F.Kroeger

761: Een kanttekening

762: We mathematicians are losing the race

763: A proof by Rutger M.Dijkstra and me

764: Repaying our debts

765: A Hungarian problem

766: An educational stupidity

767: A.J.Martin’s solution of the Hungarian problem

768: Largely on nomenclature

770: D.A.Turner’s reply

771: About 2-coloured 6-graphs

772: A methodological sequel to EWD771

773: Trip report E.W.Dijkstra, Han-sur-Lesse, 7–12 Jan. 1981

774: Trip report E.W.Dijkstra, California, 17–31 January 1981

775: On Kleinrock’s Theorem

776: Lambek and Moser revisited

777: A word of welcome (Draft)

778: A somewhat open letter to Nils J.Nilsson

782: A stupid notation

783: The administration as social disease

786: Trip report E.W.Dijkstra, England, 23 April 1981

786a: Sets are Unibags

787: A (new?) proof of a theorem of Euler’s on partitions

788: What we seem to have learned (with A.J.M. van Gasteren)

790: Trip report E.W.Dijkstra, München, 19 May 1981

791: The psychology of the user

793: The analysis of a two-person game

796a: Smoothsort, an alternative for sorting in situ

797: Fibonacci numbers and Leonardo numbers

798: Trip report E.W.Dijkstra, Newcastle, 19–25 July 1981

799: Trip report E.W.Dijkstra, Marktoberdorf, 26/7–10/8/81

08xx

800: A bagatelle for the left hand

801: Distances from the root in skew trees (with C.S.Scholten)

802: Trip report E.W.Dijkstra, Scotland, Newcastle 31 Aug.–15 Sep. 1981

804: On equality of propositions

805: Trip report E.W.Dijkstra, Amsterdam, 26–29 Oct. 1981

806: Trip report E.W.Dijkstra, USA, 1–27 Nov. 1981

808: Canonical string reduction

810a: Fast image construction in computerized axial tomography (CAT) (with A.J.M. van Gasteren)

811: An alternative ending for AvG16/ EWD809

814: A review of a book on PEARL

818: A nice theorem on monotonic predicate sequences

819: Mathematical induction and computing science

821: From predicate transformers to predicates (Dedicated by the Tuesday Afternoon Club to C.A.R. Hoare at the occasion of his being elected Fellow of the Royal Society.)

824: Linearization of a two-dimensional search

826: Trip report E.W.Dijkstra, USA, 20 May 1982 – 14 June 1982

827: A very simple exercise in SASL

829: De software crisis, ontstaan en hardnekkigheid

831: Why numbering should start at zero

832: A theorem about infinite sequences of numbers

833: An In-Depth Seminar on Proven Tools & Techniques of Structured Methodology for Effective Software Configuration Management

837: Trip report E.W.Dijkstra, Newcastle-upon Tyne, 6–10 Sep. 1982

838: Trip report E.W.Dijkstra, Copenhagen, 10–16 Sep. 1982

839: Trip report E.W.Dijkstra, Utrecht 30 Sep.–1 Oct. 1982

841: “There is no ‘royal road’ to geometry”

845: McCarthy’s 91–function: an unfortunate paradigm

847: Trip report E.W.Dijkstra, Australia, 19 Jan.1983 – 12 Feb.1983

850: Trip report E.W.Dijkstra, Helsinki, 1–4 March 1983

852: Judging “HOS” from a distance

853a: Ingenieur Ebergen, Weledelgetrenge Heer

854: The fruits of misunderstanding

855: Trip report E.W.Dijkstra, Barcelona 5–7 June 1983

856: On maximizing a product

857: Generalizing an old formula

858: Trip report E.W.Dijkstra, USA, 10 June–3 July 1983

861: Research proposal: Our plans for the years to come (with A.J.M. van Gasteren)

862: A sequence with |x[n]| = x[n–1] + x[n+1] has period 9

864: The distributed snapshot of Chandy/Lamport/Misra

864a: The Distributed Snapshot of K.M.Chandy and L. Lamport

865: Trip report E.W.Dijkstra, Brasil & USA, 17 Oct.– 6 Nov. 1983

866: An analytical proof of the Butterfly Theorem

868: Computers and General Education: a position paper

869: Ter afsluiting van de “Inleiding tot de Kunst van het Programmeren”

870: My mother’s proof of the Butterfly Theorem (see EWD866)

872: The little essay I could not write

873: Trip report E.W.Dijkstra, London and Colchester, 16–20 Jan. 1984

876: De microprocessor als lollie

877: Some useful formulae (with A.J.M. van Gasteren)

878: A monotonicity argument (with A.J.M. van Gasteren)

879: Trip report E.W.Dijkstra, London, 14–17 February 1984

881: A review of “The Evolution of Programs”

885: Trip report E.W.Dijkstra, Muenchen, 12–14 April 1984

887: Trip report E.W.Dijkstra, USA, 23 April –10 May 1984

888: Trip report E.W.Dijkstra, Zürich, 22–24 May 1984

889: User-friendly Mathematics

892: Trip report E.W.Dijkstra, London, 12–14 June 1984

893: Trip report E.W.Dijkstra, USA, 17–26 June 1984

895: Trip report E.W.Dijkstra, Marktoberdorf, 30 July – 12 Aug. 1984

896: On the nature of computing science

898: The threats to computing science

09xx

903: A short sequel to EWD863

904: A problem solved by my nephew Sybrand L. Dijkstra

906: Trip report E.W.Dijkstra, Nuenen & London, 10 Dec.’84 – 10 Jan.’85

907: Trip report E.W.Dijkstra, Netherlands, Austria, 23–31 Jan. 1985

909: Trip report E.W.Dijkstra, Westboro-Boston, 14–17 Feb. 1985

911: Trip report E.W.Dijkstra, Tulsa, 1–6 March 1985

913: On a cultural gap (Draft)

917: Another misguided effort

918: A summary of a year’s impressions

920: Can computing science save the computer industry?

921: A correction of EWD914–15

923: Trip report E.W.Dijkstra, Ithaca, Newport, 30 May – 13 June 1985

923a: Where is Russell’s “Paradox”?

924: On a cultural gap

925: Trip report E.W.Dijkstra, London, 25–27 June 1985

926: A computer to think about

927: The ATAC ( = Austin Tuesday Afternoon Club)

930: For the record: the Linear Search

932c: The streamlining of the mathematical argument

936: On anthropomorphism in science

947: A letter to a typewriter manufacturer

951: Trip report E.W.Dijkstra, Europe, 13.12.1985 – 10.1.1986

952: Science fiction and science reality in computing

956: Address to my students

958: On naming (with A.J.M. van Gasteren)

960: On a proof I learned from prof. dr. J. Haantjes

962: Introducing a course on mathematical methodology

963: Visuals for BP’s Venture Research Conference

966: Management and Mathematics

968: Trip report E.W.Dijkstra, Marktoberdorf, 29 July – 10 Aug l986

973: The cosine rule

974: The longer side is opposite to the greater angle

975: On the theorem of Pythagoras

976: Who is your “target audience”?

977: An address to my students (16.9.1986)

978: A sequel to EWD977 (18.9.1986)

979: A solution designed by A. Blokhuis

980: The strange case of The Pigeon-hole Principle

981: Address to my students (23.9.1986)

983: How do we contribute? (30.9.1986)

987: On a class of graphs with modest diameter

987a: On a class of graphs with modest diameter

988: On the phenomenon of scientific disciplines

988a: How experimental is computing science?

989: Proving Gupta’s Theorem

991: Why Johnny can’t understand

992: Difficult is easy

993: The nature of my research and why I do it

996: Courtesy A.J.M. van Gasteren, C.S.Scholten and J.G.Wiltink

997: Computing Science in the United Kingdom

10xx

1000: Twenty-eight years

1003: Graphs of modest diameter and degrees

1006: Trip report E.W.Dijkstra, Stanford/Palo Alto, 26–29 March l987

1008: What computing science is about

1009: On a somewhat disappointing correspondence

1011: Introducing my fall 1987 course on Mathematical Methodology

1012: “Real mathematicians don’t prove”

1013: Position paper on “fairness”

1014: A monotonicity argument revisited

1016: A computing scientist’s approach to a once-deep theorem of Sylvester’s

1018: To the members of the Budget Council

1019: Another filler of the YoP Institute

1024: A new science, from birth to maturity

1026: Trip report E.W.Dijkstra, Marktoberdorf 1988

1027: My methodological blunder with grid polygons

1028: Euclid, Netty, and the prime numbers

1033: Trip report E.W.Dijkstra, Zürich, 15–20 Oct. 1988

1035: On long-range planning for the CS department

1036: On the cruelty of really teaching computing science

1039: Seemingly on a problem transmitted by Bengt Jonsson

1041: By way of introduction

1041a: Factorizing the factorial

1043: A few comments on “Computing as a discipline”

1044: To hell with “meaningful identifiers”!

1046: A tale of two winters

1049: A somewhat open letter to Uri Leron

1050: On the design of a simple proof for Morley’s Theorem

1051: The next forty years

1053: Monochrome pairs in the three-coloured plane

1054: On hygiene, intellectual and otherwise

1055: On the problem of the calissons

1055A: untitled (advice to a young scientist)

1055c: On covering a figure with diamonds

1056: Hoe onbelangrijk het is of duikboten kunnen zwemmen

1057: Andrei P. Ershov in Nuenen

1058: In reply to comments

1059: 0 Preface (Mathematical Methodology)

1060: “Predicate Calculus and Program Semantics”, fall 1989

1066: Hungry? Have a byte ....

1067: A very first introductory example (Mathematical Methodology)

1068: On the quality criteria for mathematical writing (Mathematical Methodology)

1069: Fair gambling with a biased coin

1070: For brevity’s sake (Mathematical Methodology)

1071: Making a fair roulette from a possibly biased coin

1071a: Making a fair roulette from a possibly biased coin

1072: On covering a figure with diamonds

1073: How Computing Science created a new mathematical style

1076: From “Discrete Mathematics with Applications” by Susanna S. Epp

1083: The balance and the coins

1085: Proving the theorem of Menelaos

1092: Two ways of determining an expectation value

1094: The undeserved status of the pigeon-hole principle (Mathematical Methodology)

1095: Are “systems people” really necessary?

1096: Potter’s proof of disjunction’s symmetry

11xx

1100: The computing habit

1101: Triangles in graphs: a sharp bound

1103: For the record: ETAC and the couples

1104: So much for scientific visualization

1105: For Bill Walker a sequel to EWD1099

1108: Too much PSST in Texas

1109: Simplifying a proof in our book

1110: To the members of the budget council (Confidential)

1112: Why “up to equivalence”

1113: A somewhat open letter to Ben Kuipers

1117: Monotonic demonstranda and dummy introduction

1121: Covering rectangles with bars of length 3

1126: Who failed?

1129: Why “heavy-weight” bits are unavoidable

1131: Bulterman’s theorem on shortest tree

1132: Introducing a course on the design and use of calculi

1134: The checkers problem told to me by M.O. Rabin

1135: The knight’s tour

1137: Computing the future?

1140: The arithmetic mean and the geometric mean

1142: It is all distributivity

1145: A somewhat open letter to Cathleen Synge Morawetz

1151: A terrible Thursday

1152: Het intellectuele gehalte van informatica

1155: A prime is in at most 1 way the sum of 2 squares

1155a: A prime is in at most 1 way the sum of 2 squares

1156: Voorwoord (voor jaarboek studievereniging UT)

1157: Introducing a course on program design and presentation

1161: How promiscuous are the French ?

1165: There is still a war going on

1166: “From my Life”

1170: Equilateral triangles and rectangular grids

1171: The argument about the arithmetic mean and the geometric mean, heuristics included

1175: The strengths of the academic enterprise

1177: In Memoriam Jan L.A. van de Snepscheut

1179: A sorry parade

1180: Heuristics for a very simple Euclidean proof

1181: Don’t mix unary pre- and postfix operators

1188: A problem from Zhendong Patrick Su (including an alternative solution by R.Boute

1190: Problem 10406 from The American Mathematical Monthly, Volume 101, Number 8 / October 1994

1193: On arcs and angles

1194: Z.P. Su’s second problem

1198: Jan van de Snepscheut’s tiling problem

1199: A supplement to EWD1140 and EWD1171

12xx

1200: Only a matter of style?

1202: The complete (n + 1)-graph in n-dimensional space

1203: Primes once more (re Kac & Ulam)

1204: Complete DAGs

1205: A trip to Harvard Law School, 10–11 April 1995

1206: An unfortunate use of symbols

1207: A theorem about “factors” perhaps worth recording

1209: Why American Computing Science seems incurable

1210: The non-unique node multiplicity

1211a: On some very binary patterns (dedicated to F.E.J. Kruseman Aretz)

1212: For the record: painting the squared plane

1213: Introducing a course on calculi

1214: The marriage agency

1215: Courtesy Dr. Birgit Schieder

1216: The equation x: [x]

1217: Comments on a Review of the Department

1219: “I have a proof that ....”

1220: Honors course “Mathematical Methodology”, Spring 1996

1224: Hm++, a new Professional Standard (From the desk of the chairman of the Board of Mathematics Inc.)

1226: A simple geometrical theorem I did not know

1227: A somewhat open letter to David Gries

1228: Sylvester’s theorem used (see EWD1016)

1229: Nondeterministic construction of an arbitrary witness

1231: The arithmetic and geometric means once more

1232: My simplest theorem

1235: Een scheve schaats

1237: Elegance and effective reasoning (Fall 1996)

1238: Foreword

1239: A first exploration of effective reasoning

1243: The next fifty years

1243a: The next fifty years

1245: A kind of converse of Leibniz’s Principle

1248: Homework #1 (See EWD996)

1250: The couples, the river, and the little boat

1251: Two problems derived from Hugo Steinhaus

1252: Convocation speech, December 8, 1996

1253: Mathematical induction’s fixpoint

1255: Pruning the search tree

1256: Mathematical Methodology, Spring 1997

1258a: The ladder theorem

1260: The marked coins and the scale

1261: The angle bisectors of a triangle

1268: The Mathematical Divide

1273: On Dijkstra’s Lemma and Kruskal’s Algorithm

1277: Society’s role in mathematics

1282: On graphs whose nodes are Black or White

1283: How “they” try to corrupt “us”

1284: Computing Science: Achievements and Challenges

1285: To Cambridge by mistake (13–18 April 1999)

1287: Dear Tony, dearest Jill, and other people, dear or not

1288: Ulrich Berger’s argument rephrased

1290: Eliminating cascading carries

1292: When a symmetric operator distributes over (up) and (down)

1297: Triggered by a high-school exercise

1298: Under the spell of Leibniz’s Dream

13xx

1300: The notational conventions I adopted, and why

1301: The river, the isles and the bridges

1302: Once more bichrome triangles in complete graphs

1303: My recollections of operating system design

1304: The end of computing science?

1305: Answers to questions from students of Software Engineering

1306: The chessboard covered with dominoes

1306a: The chessboard covered with dominoes

1307: An unavoidable case analysis

1308: What led to “Notes on Structured Programming”

1309a: Zuckerman’s problem and the ETAC

1310: Three trip reports rolled into one: 2001.04.16 – 2001.07.06

1311: Another look at a problem from Hugo Steinhaus

1312: On disjoint binary numbers

1313: The GCD and the minimum

1315: Indirect equality enriched (and a proof by Netty)

1316: Philips and I: a few snapshots

1317: From van IJzeren’s correspondence to my aunt & uncle

1318: Coxeter’s rabbit