Communications of the ACM (CACM), Volume 18, 1975

Volume 18, Number 1, January 1975

Special Issue Honoring Alston S. Householder

• 
  Ralph A. Willoughby:
  Special Issue Honoring Alston S. Householder - Editor's Foreword. Commun. ACM 18(1): 3 (1975)
• 
  Aaron Finerman:
  Professionalism in the Computing Field. 4-9
• 
  Friedrich L. Bauer:
  Positivity and Norms. 9-13
• 
  John Todd:
  The Lemniscate Constants. 14-19
• 
  G. Peters, James Hardy Wilkinson:
  On the Stability of Gauss-Jordan Elimination with Pivoting. 20-24
• 
  Garrett Birkhoff:
  Two Hadamard Numbers for Matrices. 25-29
• 
  A. van der Sluis:
  Perturbations of Eigenvalues of Non-normal Matrices. 30-36
• 
  Marvin Marcus, Herbert Robinson:
  Elementary Divisors of Tensor Products. 36-39
• 
  Magnus R. Hestenes:
  Pseudoinverses and Conjugate Gradients. 40-43
• 
  Harlan D. Mills:
  The New Math of Computer Programming. 43-48
• 
  Tien Chi Chen, Irving T. Ho:
  Storage-Efficient Representation of Decimal Data. 49-52
• 
  Werner Liniger:
  Connections Between Accuracy and Stability Properties of Linear Multistep Formulas. 53-56
• 
  Richard J. Hanson:
  Stably Updating Mean and Standard Deviation of Data. 57-58

Volume 18, Number 2, February 1975

Computer Systems

• 
  G. J. Burnett, Edward G. Coffman Jr.:
  Analysis of Interleaved Memory Systems Using Blockage Buffers. 91-95

Information Retrieval and Language Processing

• 
  Neil M. Goldman:
  Sentence Paraphrasing from a Conceptual Base. 96-106
• 
  Gordon J. van der Brug, Jack Minker:
  State-Space, Problem-Reduction, and Theorem Proving-Some Relationships. 107-115

Algorithms

• 
  William J. Knight:
  Chi-Square Quantiles (Certification of Algorithm 451). Commun. ACM 18(2): 116 (1975)
• 
  Ove Skovgaard:
  Jacobi Polynomials (Remark on Algorithm 332). Commun. ACM 18(2): 116-117 (1975)
• 
  T. W. Hancock:
  Exact Probabilities for R x C Contingency Tables (Remark on Algorithm 434). Commun. ACM 18(2): 117-119 (1975)
• 
  Maciej M. Syslo:
  The Elementary Circuits of a Graph (Remark on Algorithm 459). Commun. ACM 18(2): 119 (1975)
• 
  H. S. Magnuski:
  A Minimal Spanning Tree Clustering Method (Remark on Algorithm 479). Commun. ACM 18(2): 119 (1975)

Short Communication: Graphics and Image Processing

• 
  Caolyn Kimme, Dana Balard, Jack Sklansky:
  Finding Circles by an Array of Accumulators. 120-122

Volume 18, Number 3, March 1975

Scientific Applications

• 
  H. C. Johnston, C. A. R. Hoare:
  Matrix Reduction - An Efficient Method. 141-150
• 
  Brian W. Kernighan, Lorinda L. Cherry:
  A System for Typesetting Mathematics. 151-156

Programming Languages

• 
  Duncan H. Lawrie, T. Layman, D. Baer, J. M. Randal:
  Glypnir-A Programming Language for Illiac IV. 157-164

Programming techniques

• 
  Robert W. Floyd, Ronald L. Rivest:
  Expected Time Bounds for Selection. 165-172
• 
  Robert W. Floyd, Ronald L. Rivest:
  The Algorithm SELECT - for Finding the ith Smallest of n Elements [M1] (Algorithm 489). 173

Short Communications: Numerical Mathematics

• 
  Richard Alan Karp:
  A Reply to Gentleman and Marovich. 174

Short Communications: Management / Data Base Systems

• 
  Jerry D. Whitt, A. Gale Sullenberger:
  The Algorithm Sequential Access Method: An Alternative to Index Sequential. 174-176

Numerical Mathematics

• 
  A. M. Erisman, W. F. Tinney:
  On Computing Certain Elements of the Inverse of a Sparse Matrix. 177-179
• 
  Lawrence F. Shampine:
  Discrete Least Squares Polynomial Fits. 179-180

Operating Systems

• 
  David Lorge Parnas:
  On a Solution to the Cigarette Smoker's Problem (Without Conditional Statements). 181-183

Volume 18, Number 4, April 1975

Education

• 
  Jack A. Chambers, Ray V. Poore:
  Computer Networks in Higher Education: Socio-Economic-Political Factors. 193-199

Algorithms

• 
  E. S. Ginsberg, Dorothy Zaborowski:
  The Dilogarithm Function of a Real Argument [S22] (Algorithm 490). 200-202
• 
  Lawrence W. Frederick:
  Remark on Algorithm 475. 202

Management Science / Operations research

• 
  Graham Smith:
  On Maintenance of the Opportunity List for Class-Teacher Timetable Problems. 203-208

Graphics and Image Processing

• 
  I. C. Braid:
  The Synthesis of Solids Bounded by Many Faces. 209-216

Programming Techniques

• 
  Vladimir Batagelj:
  The Quadratic Hash Method When the Table Size Is Not a Prime Number. 216-217
• 
  Henry S. Warren Jr.:
  A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations. 218-220
• 
  James A. Hinds:
  An Algorithm for Locating Adjacent Storage Blocks in the Buddy System. 221-222
• 
  Jean G. Vaucher, Pierre Duval:
  A Comparison of Simulation Event List Algorithms. 223-230

Volume 18, Number 5, May 1975

Programming Techniques

• 
  David A. Fisher:
  Copying Cyclic List Structures in Linear Time Using Bounded Workspace. 251-252

Management / Data Base Systems

• 
  Alfonso F. Cardenas:
  Analysis and Performance of Inverted Data Base Structures. 253-263

Information Retrieval and Language Processing

• 
  Yorick Wilks:
  An Intelligent Analyzer and Understander of English. 264-274

Algorithms

• 
  Norman E. Gibbs:
  Basic Cycle Generation [H] (Algorithm 491). 275-276
• 
  Robert Piessens, Irene Mertens:
  Ten Subroutines for the Manipulation of Chebyshev Series (Remark and Certification on Algorithm 446). 276
• 
  R. G. Mashburn:
  Visible Surface Plotting Program (Remark on Algorithm 475). 276-277
• 
  C. J. Doran:
  Visible Surface Plotting Program (Remark on Algorithm 475). 277
• 
  Fred N. Fritsch, Alan C. Hindmarsh:
  Solution of an Overdetermined System of Equations in the L1 Norm (Remark on Algorithm 478). Commun. ACM 18(5): 277 (1975)

Short Communications: Numerical Mathematics

• 
  David J. Evans, Michael Hatzopoulos:
  A Note on the LU Factorization of a Symmetric Matrix. 278-279

Short Communications: Management Science / Operations Research

• 
  Bennett L. Fox:
  More on kth Shortest Paths. 279

Short Communications: Reports and Articles

• 
  Anthony I. Wasserman:
  A Problem-List of Public Policy Issues Concerning Computers and Health Care. 279-280

Scientific Applications

• 
  Steven L. Horowitz:
  A Syntactic Algorithm for Peak Detection in Waveforms with Applications to Cardiography. 281-285
• 
  Charles E. Pfefferkorn:
  A Heuristic Problem Solving Design System for Equipment or Furniture Layouts. 286-297

Volume 18, Number 6, June 1975

Algorithms

• 
  Norman E. Gibbs:
  Generation of All the Cycles of a Graph from a Set of Basic Cycles [H] (Algorithm 492). 310

Grapics and Image Processing

• 
  Bui Tuong Phong:
  Illumination for Computer Generated Pictures. 311-317

Computer Systems

• 
  Vincent Y. Lum, Michael E. Senko, C. P. Wang, Huei Ling:
  A Cost Oriented Algorithm for Data Set Allocation in Storage Hierarchies. 318-322

Programming Techniques

• 
  Alan F. Babich, John Grason, David Lorge Parnas:
  Significant Event Simulation. 323-329
• 
  Robert B. K. Dewar:
  Indirect Threaded Code. 330-331
• 
  Ben Cranston, Rick Thomas:
  A Simplified Recombination Scheme for the Fibonacci Buddy System. 331-332
• 
  Alfred V. Aho, Margaret J. Corasick:
  Efficient String Matching: An Aid to Bibliographic Search. 333-340
• 
  Daniel S. Hirschberg:
  A Linear Space Algorithm for Computing Maximal Common Subsequences. 341-343
• 
  Stephen Soule:
  Addition in an Arbitrary Base Without Radix Conversion. 344-346

Short Communications: Numerical Mathematics

• 
  L. H. Harper, Thomas H. Payne, John E. Savage, Ernst G. Straus:
  Sorting X + Y. 347-349

Management Science / Operations Research

• 
  F. Paul Wyman:
  Improved Event-Scanning Mechanisms for Discrete Event Simulation. 350-353

Volume 18, Number 7, July 1975

Operating Systems

• 
  Pierre-Jacques Courtois:
  Decomposability, Instabilities, and Saturation in Multiprogramming Systems. 371-377
• 
  Søren Lauesen:
  A Large Semaphore Based Operating System. 377-389

Information Retrieval and Language Processing

• 
  Naomi Sager, Ralph Grishman:
  The Restriction Language for Computer Grammars of Natural Language. 390-400

programming Techniques

• 
  David Lorge Parnas, Daniel P. Siewiorek:
  Use of the Concept of Transparency in the Design of Hierarchically Structured Systems. 401-408

Management Science / Operations Research

• 
  Herbert Freeman, Ruth Shapira:
  Determining the Minimum-Area Encasing Rectangle for an Arbitrary Closed Curve. 409-413

Short Communication: Programming Techniques

• 
  Daniel G. Bobrow:
  A Note on Hash Linking. 413-415

Reports and Articles

• 
  Richard E. Weber, Bruce Gilchrist:
  Discrimination in the Employment of Women in the Computer Industry. 416-418

Volume 18, Number 8, August 1975

Operating Systems

• 
  John E. Shore:
  On the External Storage Fragmentation Produced by First-Fit and Best-Fit Allocation Strategies. 433-440

Programming Languages

• 
  Alfred V. Aho, Stephen C. Johnson, Jeffrey D. Ullman:
  Deterministic Parsing of Ambiguous Grammars. 441-452
• 
  Edsger W. Dijkstra:
  Guarded Commands, Nondeterminacy and Formal Derivation of Programs. 453-457

Short Communication: Numerical Mathematics

• 
  Ira W. Cotton:
  Remark on Stably Updating Mean and Standard Deviation of Data. 458

Short Communication: Information Retrieval and Language Processing

• 
  Stuart C. Sharo, Stanley C. Kwasny:
  Interactive Consulting via Natural Language. 459-462

Short Communication: Numerical Mathematics

• 
  Alan Jay Smith:
  Comments on a Paper by T. C. Chen and I. T. Ho. 463

Information Retrieval and Language Processing

• 
  Sakti P. Ghosh:
  Consecutive Storage of Relevant Records with Redundancy. 464-471

Programming Techniques

• 
  Leslie Lamport:
  Multiple Byte Processing with Full-Word Instructions. 471-475
• 
  Keith Shwayder:
  Combining Decision Rules in a Decision Table. 476-480

Volume 18, Number 9, September 1975

ACM 1975 George E. Forsythe Student Paper Competition Award

• 
  Guy L. Steele Jr.:
  Multiprocessing Compactifying Garbage Collection. 495-508
• 
  Jon Louis Bentley:
  Multidimensional Binary Search Trees Used for Associative Searching. 509-517
• 
  R. Mark Claudson:
  The Digital Simulation of River Plankton Population Dynamics. 517-523
• 
  William F. Piepmeier:
  Optimal Balancing of I/O Requests to Disks. 524-527

Programming Languages

• 
  Ben Wegbreit:
  Mechanical Program Analysis. 528-539

Volume 18, Number 10, October 1975

Selected Papers from ACM SIGMOD Conference 1975

• 
  Rob Gerritsen:
  A Preliminary System for the Design of DBTG Data Structures. 551-557
• 
  Nan C. Shu, Barron C. Housel, Vincent Y. Lum:
  CONVERT: A High Level Translation Definition Language for Data Conversion. 557-567
• 
  John Miles Smith, Philip Yen-Tang Chang:
  Optimizing the Performance of a Relational Algebra Database Interface. 568-579
• 
  Morton M. Astrahan, Donald D. Chamberlin:
  Implementation of a Structured English Query Language. 580-588

Programming Techniques

• 
  Fanica Gavril:
  Merging with Parallel Processors. 588-591

Management Science / Operations Research

• 
  Martin Reiser, Hisashi Kobayashi:
  Horner's Rule for the Evaluation of General Closed Queueing Networks. 592-593

Volume 18, Number 11, November 1975

Information Retrieval and Language Processing

• 
  Gerard Salton, Anita Wong, Chung-Shu Yang:
  A Vector Space Model for Automatic Indexing. 613-620
• 
  Raymond F. Boyce, Donald D. Chamberlin, W. Frank King III, Michael Hammer:
  Specifying Queries as Relational Expressions: The SQUARE Data Sublanguage. 621-628

Programming Languages

• 
  Henry F. Ledgard, Michael Marcotty:
  A Genealogy of Control Structures. 629-639
• 
  Susan L. Graham, Steven P. Rhodes:
  Practical Syntactic Error Recovery. 639-650

Programming Techniques

• 
  James R. Bitner, Edward M. Reingold:
  Backtrack Programming Techniques. 651-656
• 
  Lawrence T. Kou, C. K. Wong:
  A Note on the Set Basis Problem Related to the Compaction of Character Sets. 656-557

Volume 18, Number 12, December 1975

Papers from the Second ACM Symposium on Principles of Programming Languages, January 20-22, 1975, Palo Alto, California

• 
  Peter Naur:
  Programming Languages, Natural Languages, and Mathematics. 676-683
• 
  John B. Goodenough:
  Exception Handling: Issues and a Proposed Notation. 683-696
• 
  Mehdi Jazayeri, William F. Ogden, William C. Rounds:
  The Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars. 697-706
• 
  Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman:
  On the Complexity of LR(k) Testing. 707-716
• 
  Susan L. Graham, Mark N. Wegman:
  A Fast and Usually Linear Algorithm for Global Flow Analysis (Abstract). 716
• 
  Richard J. Lipton:
  Reduction: A Method of Proving Properties of Parallel Programs. 717-721
• 
  Jacob T. Schwartz:
  Automatic Data Structure Choice in a Language of Very High Level. 722-728