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

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