---

Contents
Section 1     Algorithms and Data Structures

1.1       The Complexity of Theorem Proving Procedures                                                   2
By Stephen A. Cook

1.2      On the Conceptual Complexity of Algorithms                                                          10
By J. Hartmanis and R. E. Stearns

1.3      Quicksort                                                                                                                                31
By C. A. R. Hoare

1.4      Finite Automata and Their Decision Problems                                                      40
By M. O. Rabin and D. Scott

Section 2     Programming Languages

2.1       The FORTRAN Automatic Coding System                                                              62
By J. W. Backus, et al.

2.2      An Axiomatic Basis for Computer Programming                                                   80
By C. A. R. Hoare

2.3      An Axiomatic Definition of the Programming Language Pascal                     90

By C. A. R. Hoare and N. Wirth

2.4      The Contour Model of Block Structured Processes                                               111
By John B. Johnston

2.5      On the Translation of Languages from Left to Right                                               150
By Donald E. Knuth

2.6      Revised Report on the Algorithmic Language ALGOL 60                                 174
By Peter Naur, et al.

Section 3      Architecture

  3.1       First Draft of a Report on the EFVAC                                                                          208

By John von Neumann

                                  3.2       A Symbolic Analysis of Relay and Switching Circuits                                          219

By Claude E. Shannon

3.3      Alto: A Personal Computer                                                                                         246
By C. P. Thacker, E. M. McCreight, B. W. Lampson,
R. F. Sproull, and D. R Boggs

3.4       The Best Way to Design an Automatic Calculating Machine                           279
By M. V. Wilkes

Section 4     Numerical and Scientific Computing

4.1      On Computable Numbers, with an Application                                                       287
to the Entscheidungsproblem
By A. M. Turing

4.2      On Computable Numbers, with an Application                                                       317
to the Entscheidungsproblem. A Correction
By A. M.Turing

Section 5     Operating Systems

5.1      Cooperating Sequential Processes                                                                           321
By Edsger W. Dijkstra

5.2     Solution of a Problem in Concurrent Process Control                            378
By Edsger W. Dijkstra

5.3        A Formal System for Information Retrieval from Files                                      381
By David Hsiao and Frank Harary

Section 6     Software Methodology and Engineering

6.1      No Silver Bullet — Essence and Accidents of                                                        397
Software Engineering

By Frederick P. Brooks

6.2      Guarded Commands, Nondeterminancy, and                                                         412
Formal Derivation of Programs
By Edsger W. Dijkstra

6.3      Go To Statement Considered Harmful                                                                     420
By Edsger W. Dijkstra

6.4      Proof of Correctness of Data Representations                                                        423
By C. A. R. Hoare

6.5      On the Criteria to be Used in Decomposing Systems                                         433
into Modules

By David L. Parnas

6.6      A Rational Design Process: How and Why to Fake It                                          442
By David L. Parnas and Paul C. Clements

6.7      Global Variables Considered Harmful                                                                      452
By W. Wulf and M. Shaw

Section 7    Databases

7.1       The Theory of Joins in Relational Databases                                                        460
By A. V. Aho, C. Beeri, and J. D. Ullman

7.2      Organization and Maintenance of Large Ordered Indexes                                478
By R. Bayer and E. Mccreight

7.3      The Entity Relationship Model - Toward A Unified View of Data           494

By Peter Pin-Shan Chen

7.4      A Relational Model of Data for Large Shared Data Banks                                519
By E. F. Codd

Section 8    Artificial Intelligence and Robotics

8.1      Steps Toward Artificial Intelligence                                                                              541
By Marvin L. Minsky

8.2    Matter, Mind, and Models                                                                             580
By Marvin L. Minsky

8.3      Fusion, Propagation, and Structuring in Belief Networks                                     586
By Judea Pearl

8.4        Computing Machinery and intelligence                                                                 628
By A. M.Turing

Section 9     Human-Computer Communications

9.1      Programming Considered as a Human Activity                                   648
By Edsger W. Dijkstra

Section 10   History

10.1    Programming in America in the 1950s-                                               665
Some Personal Impressions
            By John Backus

10.2    The Evolution of Data-Base Management Systems                           663
By James P. Fry and Edgar H. Sibley

10.3    The Evolution of the UNIX Time-Sharing System                               707
By Dennis M. Ritchie