Great
Papers in Computer Science
Phillip Laplante
Burlington County
College
West Publishing
Company, 1996
ISBN: 0-314-06365
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
3.2 A
Symbolic Analysis of Relay and Switching Circuits 219
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
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
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
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
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
9.1 Programming Considered as a Human Activity 648
By Edsger W. Dijkstra
Section 10 History
10.1 Programming in
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