Communications of the ACM (CACM), Volume 17, 1974

Volume 17, Number 1, January 1974

Programming Languages

• 
  Gordon Lyon:
  Syntax-Directed Least-Errors Analysis for Context-Free Languages: A Practical Approach. 3-14

Numerical Mathematics

• 
  Michael A. Malcolm, John Palmer:
  A Fast Method for Solving a Class of Tridiagonal Linear Systems. 14-17
• 
  Hiroshi Akima:
  A Method of Bivariate Interpolation and Smooth Surface Fitting Based on Local Procedures. 18-20
• 
  Norman E. Gibbs, William G. Poole Jr.:
  Tridiagonalization by Permutations. 20-24

Algorithms

• 
  Robert Piessens:
  Computation of Legendre Series Coefficients [C6] (Algorithm 473). 25
• 
  Hiroshi Akima:
  Bivariate Interpolation and Smooth Surface Fitting Based on Local Procedures [E2] (Algorithm 474). 26-31

Graphics and Image Processing

• 
  Ivan E. Sutherland, G. W. Hodgman:
  Reentrant Polygon Clipping. 32-42

Short Communications: Programming Techniques

• 
  Peter J. H. King, Roger G. Johnson:
  Comments on the Algorithms of Verhelst for the Conversion of Limited-Entry Decision Tables to Flowcharts. 43-45
• 
  Gary D. Knott:
  A Numbering Systems for Combinations. 45-46

Short Communications: Computer Systems

• 
  Henry C. Lucas Jr.:
  A CRT Report Generating System. 47-48

Volume 17, Number 2, February 1974

Information Retrieval and Language Processing

• 
  James B. Rothnie Jr., Tomás Lozano-Pérez:
  Attribute Based File Organization in a Paged Memory Environment. 63-69

Graphics and Image Processing

• 
  B. W. Jordan Jr., Ronald Curtis Barrett:
  A Cell Organized Raster Display for Line Drawings. 70-77

Management Science / Operations Research

• 
  John S. Ramberg, Bruce W. Schmeiser:
  An Approximate Method for Generating Asymmetric Random Variables. 78-82

Programming Techniques

• 
  Leslie Lamport:
  The Parallel Execution of DO Loops. 83-93

Programming Languages

• 
  Henry F. Ledgard:
  Production Systems: or Can We Do Better than BNF? 93-102
• 
  Ben Wegbreit:
  The Synthesis of Loop Predicates. 102-112

Volume 17, Number 3, March 1974

Computer Systems

• 
  K. Sreenivasan, A. J. Kleinman:
  On the Construction of a Representative Synthetic Workload. 127-133
• 
  E. Balkovich, W. Chiu, Leon Presser, R. Wood:
  Dynamic Memory Repacking. 133-138
• 
  Howard L. Morgan:
  Optimal Space Allocation on Disk Storage Devices. 139-142

Algorithms

• 
  Rudolf Loeser:
  Some Performance Tests of "Quicksort" and Descendants. 143-152
• 
  Thomas J. Wright:
  Visible Surface Plotting Program [J6] (Algorithm 475). 152-255
• 
  Nancy E. Bosten, E. L. Battiste:
  Incomplete Beta Ratio (Remark on Algorithm 179). Commun. ACM 17(3): 156-157 (1974)
• 
  David H. Withers:
  Zeros of a Complex Polynomial (Remark on Algorithm 419). Commun. ACM 17(3): 157 (1974)
• 
  Arunachalam Ravindran:
  A Computer Routine for Quadratic and Linear Programming Problems (Remark on Algorithm 431). Commun. ACM 17(3): 157 (1974)

Graphics and Image Processing

• 
  Ronald Curtis Barrett, B. W. Jordan Jr.:
  Scan Conversion Algorithms for a Cell Organized Raster Display. 157-163

Short Communications: Numerical Mathematics

• 
  A. F. Ackerman:
  Quadratic Search for Hash Tables of Size p^n. 164

Scientific Applications

• 
  Stephen W. Smoliar:
  Emotional Content Considered Dangerous. 164-165

Computer Systems

• 
  Harold S. Stone:
  A Note on a Combinatorial Problem of Burnett and Coffman. 165-166

Numerical Mathematics

• 
  Fred T. Krogh:
  Efficient Implementation of a Variable Projection Algorithm for Nonlinear Least Squares Problems. 167-169

Volume 17, Number 4, April 1974

Operating Systems

• 
  Jerome H. Saltzer:
  A Simple Linear Model of Demand Paging Performance. 181-186
• 
  Mark A. Franklin, Ram K. Gupta:
  Computation of Page Fault Probability from Program Transition Diagram. 186-191

Computer Systems

• 
  John W. Boyse:
  Execution Characteristics of Programs in a Page-on-Demand System. 192-196

Management Science / Operations Research

• 
  Graham Smith, Ian M. Sefton:
  On Lions' Counter Example for Gotlieb's Method for the Construction of School Timetables. 196-197

Programming Techniques

• 
  Gary Lindstrom:
  Copying List Structures Using Bounded Workspace. 198-202
• 
  Shimon Even:
  Parallelism in Tape-Sorting. 202-204

Short Communications: Education

• 
  Henry C. Lucas Jr., David B. Montgomery, Jean Claude Larreche:
  A Study of Computer Use in a Graduate School of Business. 205-206
• 
  Peter Freeman, Michael A. Malcolm, William H. Payne:
  Graduate Education: The Ph.D. Glut: Response and Rebuttal. 206-207
• 
  Theodor D. Sterling, Seymour V. Pollack:
  Ideal Teaching Machines-A Solution to the Pedagogic Language Problem. 207-208

Short Communications: Numerical Mathematics

• 
  Grover C. Simmons:
  Addendum to M. L. Patrick Paper. 209

Short Communications: Programming Languages

• 
  Paul W. Abrahams:
  Some Remarks on Lookup of Structured Variables. 209-210
• 
  A. Balfour:
  An Alternative Approach to Mutual Recursion in Algol 60 Using Restricted Compilers. 210

Programming Languages

• 
  Richard C. T. Lee, Chin-Liang Chang, Richard J. Waldinger:
  An Improved Program-Synthesizing Algorithm and Its Correctness. 211-217

Numerical Mathematics

• 
  A. K. Cline:
  Scalar- and Planar- Valued Curve Fitting Using Splines Under Tension. 218-220

Algorithms

• 
  A. K. Cline:
  Six Subprograms for Curve Fitting Using Splines Under Tension [E2] (Algorithm 476). 220-223
• 
  Gideon Ehrlich:
  Generator of Set-Partitions to Exactly R Subsets [G7] (Algorithm 477). 224-225
• 
  Bo Einarsson:
  Solution of the Transcendental Equation w*exp(x)=x (Remark on Algorithm 443). Commun. ACM 17(4): 225 (1974)

Volume 17, Number 5, May 1974

Programming Languages

• 
  Mary Shaw:
  Reduction of Compilation Costs Through Language Contraction. 245-250
• 
  Ben Wegbreit:
  The Treatment of Data Types in EL1. 251-264
• 
  Robert A. Wagner:
  Order-n Correction for Regular Languages. 265-268

Numerical Mathematics

• 
  Nai-Kuan Tsao:
  On the Distributions of Significant Digits and Roundoff Errors. 269-271
• 
  Marvin C. Wunderlich, John L. Selfridge:
  A Design for a Number Theory Package with an Optimized Trial Division Routine. 272-276

Short Communications: Numerical Mathematics

• 
  W. Morven Gentleman, Scott B. Marovich:
  More on Algorithms that Reveal Properties of Floating Point Arithmetic Units. 276-277

Operating Systems

• 
  David Earl Gold, David J. Kuck:
  A Model for Masking Rotational Latency by Dynamic Disk Allocation. 278-288

Volume 17, Number 6, June 1974

Programming Languages

• 
  Jacques Cohen, Carl Zuckerman:
  Two Languages for Estimating Program Efficiency. 301-308
• 
  Lawrence J. Henschen, Ross A. Overbeek, Larry Wos:
  A Theorem-Proving Language for Experimentation. 308-314

Programming Techniques

• 
  James F. Gimpel:
  The Minimization of Spatially-Multiplexed Character Sets. 315-318

Algorithms

• 
  Ian Barrodale, F. D. K. Roberts:
  Solution of an Overdetermined System of Equations in the L1 Norm [F4] (Algorithm 478). 319-320
• 
  Rex L. Page:
  A Minimal Spanning Tree clustering Method [Z] (Algorithm 479). 321-323
• 
  Robert Piessens:
  Modified Havie Integration (Remark on Algorithm 400). Commun. ACM 17(6): 324 (1974)
• 
  Robert Piessens:
  Calculation of Fourier Integrals (Remark on Algorithm 418). Commun. ACM 17(6): 324 (1974)
• 
  Blaine Gaither:
  Hidden-Line Plotting Program (Remark on Algorithm 420). Commun. ACM 17(6): 324 (1974)
• 
  T. M. R. Ellis:
  Hidden-Line Plotting Program (Remark on Algorithm 420). Commun. ACM 17(6): 324-325 (1974)
• 
  Rex L. Page:
  Generation of Random Correlated Normal Variables (Remark on Algorithm 425). 325
• 
  D. M. Boulton:
  Exact Probabilities for R x C Contingency Tables (Remark on Algorithm 434). 326

Scientific Applications

• 
  William D. Slysz:
  An Evaluation of Statistical Software in the Social Sciences. 326-332
• 
  John Adams, John Gary:
  Compact Representation of Contour Plots for Phone Line Transmission. 333-336

Operating Systems

• 
  William A. Wulf, Ellis S. Cohen, William M. Corwin, Anita K. Jones, Roy Levin, C. Pierson, Fred J. Pollack:
  HYDRA: The Kernel of a Multiprocessor Operating System. 337-345

Information Retrieval and Language Processing

• 
  Ian J. Barton, Susan E. Creasey, Michael F. Lynch, Michael J. Snell:
  An Information-Theoretic Approach to Text Searching in Direct Access Systems. 345-350

Management Science / Operations Research

• 
  Edward Minieka:
  On Computing Sets of Shortest Paths in a Graph. 351-353

Volume 17, Number 7, July 1974

Papers

from the Fourth ACM Symposium on Operation System Principles, October 15-17, 1973, Yorktown Heights, New York

• 
  Dennis Ritchie, Ken Thompson:
  The UNIX Time-Sharing System. 365-375
• 
  Samuel H. Fuller:
  Minimal-Total-Processing Time Drum and Disk Scheduling Disciplines. 376-381
• 
  John L. Bruno, Edward G. Coffman Jr., Ravi Sethi:
  Scheduling Independent Tasks to Reduce Mean Finishing Time. 382-387
• 
  Jerome H. Saltzer:
  Protection and the Control of Information Sharing in Multics. 388-402
• 
  Robert S. Fabry:
  Capability-Based Addressing. 403-412
• 
  Gerald J. Popek, Robert P. Goldberg:
  Formal Requirements for Virtualizable Third Generation Architectures. 412-421

Volume 17, Number 8, August 1974

1973-74 George E. Forsythe Student Paper Competition Awards

• 
  Bruce Hahn:
  A New Technique for Compression and Storage of Data. 434-436

Operating Systems

• 
  Arthur Evans Jr., William Kantrowitz, Edwin Weiss:
  A User Authentication Scheme Not Requiring Secrecy in the Computer. 437-442
• 
  George B. Purdy:
  A High Security Log-in Procedure. 442-445
• 
  Theodore D. Friedman, Lance J. Hoffman:
  Execution Time Requirements for Encipherment Programs. 445-449

Management Science / Operations Research

• 
  G. A. Neufeld, John Tartar:
  Graph Coloring Conditions for the Existence of Solutions to the Timetable Problem. 450-453

Computer Systems

• 
  Leslie Lamport:
  A New Solution of Dijkstra's Concurrent Programming Problem. 453-455

Programming Techniques

• 
  John C. Cavouras:
  On the Conversion of Programs to Decision Tables: Method and Objectives. 456-462

Algorithms

• 
  Tom Lyche, Larry L. Schumaker:
  Procedures for computing Smoothing and Interpolating Natural Splines [E1] (Algorithm 480). 463-467
• 
  Keith C. Crandall:
  Arrow to Precedence Network Transformation [H] (Algorithm 481). 467-469
• 
  John McKay, Eric Regener:
  Transitivity Sets [G7] (Algorithm 482). Commun. ACM 17(8): 470 (1974)
• 
  Adhemar Bultheel:
  Rosenbrock Function Minimization (Remark on Algorithm 450). 470
• 
  Kenneth D. Shere:
  The Complex Method for Constrained Optimization (Remark on Algorithm 454). 471

Numerical Mathematics

• 
  A. H. Stroud:
  Gauss Harmonic Interpolation Formulas. 471-475
• 
  Rolf O. E. Lagerlof:
  Interpolation with Rounded Ramp Functions. 476-497
• 
  Forman S. Acton:
  Recurrence Relations for the Fresnel Integral xxx and Similar Integrals. 480-481

Volume 17, Number 9, September 1974

Report

• 
  Daniel D. McCracken:
  A Problem-List of Issues Concerning Computers and Public Policy - A Report of the ACM Commitee on Computers and Public Policy. Commun. ACM 17(9): 495-503 (1974)

Numerical Mathematics

• 
  I. M. Willers:
  A New Integration Algorithm for Ordinary Differential Equations Based on Continued Fraction Approximations. 504-508
• 
  Oliver Aberth:
  A Precise Numerical Analysis Program. 509-513

Scientific Applications

• 
  To-Yat Cheung:
  An Interactive Graphic Display for Region Partitioning by Linear Programming. 513-516

Programming Languages

• 
  Mario Schkolnick:
  The Equivalence of Reducing Transition Languages and Deterministic Languages. 517-519

Algorithms

• 
  Steven L. Watkins:
  Masked Three-Dimensional Plot Program with Rotations [J6] (Algorithm 483). 520-523
• 
  Keith H. Burrell:
  Evaluation of the Modified Bessel Functions K0(Z) and K1(Z) for Complex Arguments [S17] (Algorithm 484). 524-525
• 
  Harold D. Eidson, Larry L. Schumaker:
  Computation of g-Splines via a Factorization Method [E2] (Algorithm 485). 526-530

Short Communications: Computer Systems

• 
  John W. Young:
  A First Order Approximation to the Optimal Checkpoint Interval. 530-531

Programming Techniques

• 
  Keith Shwayder:
  Extending the Information Theory Approach to Converting Limited-Entry Decision Tables to Computer Programs. 532-537

Volume 17, Number 10, October 1974

Operating Systems

• 
  C. A. R. Hoare:
  Monitors: An Operating System Structuring Concept. 549-557
• 
  Kenneth K. Shen, James L. Peterson:
  A Weighted Buddy Method for Dynamic Storage Allocation. 558-562
• 
  Donald R. Slutz, Irving L. Traiger:
  A Note on the Calculation Working Set Size. 563-565

Management / Data Base Systems

• 
  Ben Shneiderman, Peter Scheuermann:
  Structured Data Structures. 566-574
• 
  Rudd H. Canaday, R. D. Harrison, Evan L. Ivie, J. L. Ryder, L. A. Wehr:
  A Back-end Computer for Data Base Management. 575-582

Management Science / Operations Research

• 
  Abraham Charnes, William M. Raike, Joel David Stutz, Anthony S. Walters:
  On Generation of Test Problems for Linear Programming Codes. 583-586

Algorithms

• 
  Francoise Veillon:
  Numerical Inversion of Laplace Transform (Algorithm 486). 587-589
• 
  Henk Koppelaar:
  Hypergeometric (Certification and Remark on Algorithm 191). Commun. ACM 17(10): 589-590 (1974)
• 
  Les G. Proll:
  A Computer Routine for Quadratic and Linear Programming Problems (Remark on Algorithm 431). 590
• 
  Jiri Klemes, Jaroslav Klemsa:
  Rosenbrock Function Minimization (Remark on Algorithm 450). Commun. ACM 17(10): 590-591 (1974)

Reports and Articles

• 
  Bruce Gilchrist, Richard E. Weber:
  Enumerating Full-Time Programmers. 592-593

Volume 17, Number 11, November 1974

Reports and Articles

• 
  Theodor D. Sterling:
  Guidelines for Humanizing Computerized Information Systems: A Report from Stanley House. 609-613

Operating Systems

• 
  Domenico Ferrari:
  Improving Locality by Critical Working Sets. 614-620

Information Retrieval and Language Processing

• 
  Perry Lowell Miller:
  A Locally-Organized Parser for Spoken Input. 621-630
• 
  Gary M. Rader:
  A Method for Composing Simple Traditional Music by Computer. 631-638

Programming Techniques

• 
  Robert A. Freiburghouse:
  Register Allocation Via Usage Counts. 638-642

Short Communications: Operating Systems

• 
  Edsger W. Dijkstra:
  Self-stabilizing Systems in Spite of Distributed Control. 643-644

Short Communications: Scientific Applications

• 
  James A. Brown, Bernard Werner:
  An On-Site Data Management System Application in Field Archaeology. 644-646

Short Communications: Programming Techniques

• 
  David R. Hanson:
  A Simple Technique for Representing Strings in Fortran IV. 646-647

Short Communications: Information Retrieval and Language Processing

• 
  C. J. van Rijsbergen:
  The Best-Match Problem in Document Retrieval. 648-649

Short Communications: Programming Languages

• 
  R. V. Evans:
  Multiple Exists from a Loop Using Neither GO TO nor Labels. 650

Volume 17, Number 12, December 1974

1974 ACM Turing Award Lecture

• 
  Donald E. Knuth:
  Computer Programming as an Art. 667-673

Reports and Articles

• 
  Larry Press:
  Arguments for a Moratorium on the Construction of a Community Information Utility. 674-678

Computer Systems

• 
  Jon C. Strauss:
  An Analytic Model of the Hasp Execution Task Monitor. 679-685
• 
  Thomas L. Adam, K. Mani Chandy, J. R. Dickson:
  A Comparison of List Schedules for Parallel Processing Systems. 685-690

Management Science / Operations Research

• 
  N. D. Wallace:
  Computer Generation of Gamma Random Variates with Non-integral Shape Parameters. 691-695
• 
  Arturo Salazar, R. V. Oakford:
  A Graph Formulation of a School Scheduling Algorithm. 696-698
• 
  Sherwood C. Chu, Mones Berman:
  An Exponential Method for the Solution of Systems of Ordinary Differential Equations. 699-702

Algorithms

• 
  John Pomeranz:
  Exact Cumulative Distribution of the Kolmogorov-Smirnov Statistic for Small Samples (Algorithm 487). 703-704
• 
  Richard P. Brent:
  A Gaussian Pseudo-Random Number Generator (Algorithm 488). 704-706
• 
  T. M. R. Ellis:
  Hidden-Line Plotting Program (Remark on Algorithm 420). 706
• 
  Coenraad Bron:
  Merge Sort Algorithm (Remark on Algorithm 426). 706
• 
  Gerhard Tesch:
  Routing Problem (Remark on Algorithm 456). 706

Information Retrieval and Language Processing

• 
  C. William Skinner:
  A Heuristic Approach to Inductive Inference in Fact Retrieval Systems. 707-712