Communications of the ACM (CACM), Volume 16, 1973

Volume 16, Number 1, January 1973

Operating Systems

• 
  Gerald S. Shedler:
  A Queuing Model of a Multiprogrammed Computer with a Two-Level Storage System. 3-10

Programming Techniques

• 
  Carter Bays:
  The Reallocation of Hash-Coded Tables. 11-14

Programming Languages

• 
  James H. Morris Jr.:
  Protection in Programming Languages. 15-21
• 
  Yoichi Muraoka, David J. Kuck:
  On the Time Required for a Sequence of Matrix Products. 22-26
• 
  E. B. James, Derek Partridge:
  Adaptive Correction of Program Statements. 27-37

Numerical Mathematics

• 
  Paul L. Richman:
  Variable-Precision Exponentiation. 38-40
• 
  C. R. Crawford:
  Reduction of a Band-Symmetric Generalized Eigenvalue Problem. 41-44

Short Communications: Education

• 
  Sumner E. Blount, Louis Fein:
  The Practical Aspect of Computer Science Education-Discussion. 45-46

Short Communications: Information Retrieval

• 
  Carter Bays:
  A Note on When To Chain Overflow Items Within a Direct-Access Table. 46-47

Short Communications: Programming Techniques

• 
  M. Stella Atkins:
  Mutual Recursion in Algol 60 Using Restricted Compilers. 47-48

Algorithms

• 
  L. J. Gallaher:
  A Multidimensional Monte Carlo Quadrature with Adaptive Stratified Sampling [D1] (Algorithm 440). 49-50
• 
  Robert E. Knop:
  Random Deviates from the Dipole Distribution [G5] (Algorithm 441). 51
• 
  G. W. Hill, A. W. Davis:
  Normal Deviate [S14] (Algorithm 442). 51-52

Volume 16, Number 2, February 1973

Scientific Applications

• 
  Roy D. Merrill:
  Representation of Contours ad Regions for Efficient Computer Search. 69-82

Programming Languages

• 
  Stefano Crespi-Reghizzi, Michel A. Melkanoff, Larry Lichten:
  The Use of Grammatical Inference for Designing Programming Languages. 83-90
• 
  James F. Gimpel:
  A Theory of Discrete Patterns and Their Implementation in SNOBOL4. 91-100

Numerical Mathematics

• 
  Jon G. Rokne:
  Automatic Errorbounds for Simple Zeros of Analytic Functions. 101-104

Programming Techniques

• 
  Richard P. Brent:
  Reducing the Retrieval Time of Scatter Storage Techniques. 105-109

Operating Systems

• 
  Robert M. Graham, Gerald J. Clancy Jr., David B. DeVaney:
  A Software Design and Evaluation System. 110-116
• 
  Robert Balzer:
  An Overview of the ISPL Computer System Design. 117-122

Algorithms

• 
  Fred N. Fritsch, R. E. Shafer, W. P. Crowley:
  Solution of the Transcendental Equation w*exp(w)=x [C5] (Algorithm A443). 123-124

Volume 16, Number 3, March 1973

Education

• 
  Richard H. Austing, Gerald L. Engel:
  A Computer Science Course Program for Small Colleges. 139-147

Programming Techniques

• 
  Robert A. Wagner:
  Common Phrases and Minimum-Space Text Storage. 148-152

Computer Systems

• 
  Yeshiah Feinroth, Ed Franceschini, M. Goldstein:
  Telecommunications Using a Front-End Minicomputer. 153-160
• 
  Charles D. Pack:
  The Effects of Multiplexing on a Computer-Communications System. 161-168

Programming Languages

• 
  Richard W. Conway, Thomas R. Wilcox:
  Design and Implementation of a Diagnostic Compiler for PL/I. 169-179

Short Communications: Numerical Mathematics

• 
  Herbert E. Salzer:
  Gray Code and the +- Sign Sequence when +-f (+-f(+-f(...+-f(x)...))) Is Ordered. 180

Short Communications: Programming Techniques

• 
  Abraham Bookstein:
  On Harrison's Substring Testing Technique. 180-181

Short Communications: Education

• 
  William H. Payne:
  Graduate Education: The Ph.D. Glut. 181-182

Algorithms

• 
  Robert A. Wagner:
  An Algorithm for Extracting Phrases in a Space-Optimal Fashion [Z] (Algorithm 444). 183-185
• 
  Shi-Kuo Chang:
  Binary Pattern Reconstruction from Projections [Z] (Algorithm 445). 185-186
• 
  John Lau:
  Binary Pattern Reconstruction from Projections [Z] (Remark on Algorithm 445). Commun. ACM 16(3): 186 (1973)

Volume 16, Number 4, April 1973

Computer Systems

• 
  Anthony Hassitt, J. W. Lageschulte, Leonard E. Lyon:
  Implementation of High Level Language Machine. 199-212
• 
  John G. Williams:
  Asymmetric Memory Hierarchies. 213-222

Numerical Mathematics

• 
  Hirondo Kuki, William J. Cody:
  A Statistical Study of the Accuracy of Floating Point Number Systems. 223-230

Information Retrieval

• 
  Walter A. Burkhard, Robert M. Keller:
  Some Approaches to Best-Match File Searching. 230-236

Graphics and Image Processing

• 
  James P. Strong III, Azriel Rosenfeld:
  A Region Coloring Technique for Scene Analysis. 237-246

Operating Systems

• 
  Juan Rodriguez-Rosell, Jean-Pierre Dupuy:
  The Design, Implementation, and Evaluation of a Working Set Dispatcher. 247-253

Algorithms

• 
  R. Broucke:
  Ten Subroutines for the Manipulation of Chebyshev Series [C1] (Algorithm 446). 254-256
• 
  Larry C. Ragland, Donald I. Good:
  Greatest Common Divisor of n Integers and Multipliers (Certification of Algorithm 386). 257

Volume 16, Number 5, May 1973

Scientific Applications

• 
  David Pager:
  On the Problem of Communicating Complex Information. 275-281

Programming Languages

• 
  David W. Low:
  Programming by Questionnaire: An Effective Way To Use Decision Tables. 282-286

Management / Data Base Systems

• 
  Peter J. H. King, Roger G. Johnson:
  Some Comments on the Use of Ambiguous Decision Tables and Their Conversion to Computer Programs. 287-290
• 
  John Salasin:
  Hierarchical Storage in Information Retrieval. 291-295

Management Science / Operations Research

• 
  Derek G. Corneil, C. C. Gotlieb, Y. M. Lee:
  Minimal Event-Node Network of Project Precedence Relations. 296-298

Graphics and Image Processing

• 
  Andrew Mercer, Azriel Rosenfeld:
  An Array Grammar Programming System. 299-305

Programming Techniques

• 
  Edward M. Reingold:
  A Nonrecursive List Moving Algorithm. 305-307

Algorithms

• 
  H. Vos:
  Coulomb Wave Functions (Remark on Algorithm 300). 308-309
• 
  G. Bayer:
  Maxflow (Remark on Algorithm 324). 309
• 
  D. Obradovic:
  Minit Algorithm for Linear Programming (Remark on Algorithm 333). 310
• 
  B. Holmgren, D. Obradovic, Å. Kolm:
  Minit Algorithm for Linear Programming (Remark on Algorithm 333). 310
• 
  Robert E. Wheeler:
  Increasing the Efficiency of Quicksort (Remark on Algorithm 402). 311
• 
  Jo Ann Howell:
  Exact Solution of Linear Equations Using Residue Arithmetic (Remark on Algorithm 406). 311
• 
  Arthur H. J. Sale:
  A Sparse Matrix Package (Remark on Algorithm 408). 311

Short Communications: Management Science / Operations Research

• 
  Mohit Kumar Roy:
  Reflection-Free Permutations, Rosary Permutations, and Adjacent Transposition Algorithms. 312-313

Short Communications: Scientific Applications

• 
  Clyde H. McMorrow:
  Concerning Music and Computer Composition in Computational Linguistics. 313
• 
  Richard L. Wexelblat:
  Another Comment on Computer Music. 313-314

Short Communications: Education

• 
  Robert G. Estell:
  A Comment on the Practical Aspects of Computer Science Education. 314

Operating Systems

• 
  Roger Fajman, John Borgelt:
  WYLBUR: An Interactive Text Editing and Remote Job Entry System. 314-322
• 
  Dennis J. Frailey:
  A Practical Approach to Managing Resources and Avoiding Deadlocks. 323-329

Volume 16, Number 6, June 1973

Operating Systems

• 
  Richard G. Hamlet:
  Efficient Multiprogramming Resource Allocation and Accounting. 337-343
• 
  Erol Gelenbe:
  Minimizing Wasted Space in Partitioned Segmentation. 343-349

Computer Systems

• 
  J. Carver Hill:
  Synchronizing Processors with Memory-Content-Generated Interrupts. 350-351
• 
  Harold S. Stone, Samuel H. Fuller:
  On the Near-Optimality of the Shortest-Latency-Time-First Drum Scheduling Discipline. 352-353
• 
  Peter F. Stockhausen:
  Adapting Optimal Code Generation for Arithmetic Expressions to the Instruction Sets Available on Present-Day Computers. 353-354

Management Science / Operations Research

• 
  Robert F. Ling:
  A Computer Generated Aid for Cluster Analysis. 355-361

Management / Data Bases

• 
  Ben Shneiderman:
  Optimum Data Base Reorganization Points. 362-365

Programming Techniques

• 
  Horst Strunz:
  The Development of Decision Tables via Parsing of Complex Decision Situations. 366-369
• 
  James R. Bell:
  Threaded Code. 370-372

Algorithms

• 
  John E. Hopcroft, Robert Endre Tarjan:
  Efficient Algorithms for Graph Manipulation [H] (Algorithm 447). 372-378
• 
  Terry Beyer, D. F. Swinehart:
  Number of Multiply-Restricted Partitions [A1] (Algorithm 448). 379

Numerical Mathematics

• 
  J. Ferguson, P. A. Staley:
  Least Squares Piecewise Cubic Curve Fitting. 380-383
• 
  W. D. Hoskins:
  Cubic Spline Solutions to Fourth-order Boundary Value Problems. 382-385

Scientific Applications

• 
  Franz L. Alt, Judith Yuni Kirk:
  Computer Photocomposition of Technical Text. 386-391

Volume 16, Number 7, July 1973

Management / Data Base Systems

• 
  Richard L. Nolan:
  Managing the Computer Resource: A Stage Hypothesis. 399-405

Information Retrieval & Language Processing

• 
  J. C. Huang:
  A Note on Information Organization and Storage. 406-410

Applications

• 
  Edward W. Kozdrowicki, Dennis W. Cooper:
  COKO III: The Cooper-Koz Chess Program. 411-427

Operating Systems

• 
  John H. Howard Jr.:
  Mixed Solutions for the Deadlock Problem. 427-430
• 
  Erol Gelenbe:
  The Distribution of a Program in Primary and Fast Buffer Storage. 431-434

Education

• 
  Robert F. Rosin:
  Teaching "About Programming". 435-438
• 
  F. Warren McFarlan, Richard L. Nolan:
  Curriculum Recommendations for Graduate Professional Programs in Information Systems: Recommended Addendum on Information Systems Administration. 439-441
• 
  Abraham Kandel:
  Computer Science-Seminars for Undergraduates. 442

Programming Languages

• 
  Gregor von Bochmann:
  Multiple Exits from a Loop Without the GOTO. 443-444
• 
  Patrick A. V. Hall:
  Equivalence Between AND/OR Graphs and Context-Free Grammars. 444-445

Algorithms

• 
  Frantisek Fiala:
  Solution of Linear Programming Problems in 0-1 Variables [H1] (Algorithm 449). 445-447
• 
  Paul J. Nikolai:
  DIFSUB for Solution of Ordinary Differential Equations (Certification of Algorithm 407). 448
• 
  Iain D. G. Macleod, Allan M. Collins:
  Hidden-Line Plotting Program (Remark on Algorithm 420). 448
• 
  Brian W. Kernighan:
  Minimal Spanning Tree (Remarks on Algorithm 422). Commun. ACM 16(7): 448 (1973)

Volume 16, Number 8, August 1973

1972-73 George E. Forsythe Student Paper Competition Award

• 
  Michael H. Smith:
  A Learning Program Which Plays Partnership Dominoes. 462-467
• 
  Bruce J. MacLennan:
  Fen-An Axiomatic Basis for Program Semantics. 468-474
• 
  David Misunas:
  Petri Nets and Speed Independent Design. 474-481

Algorithms

• 
  Marek Machura, Andrzej Mulawa:
  Rosenbrock Function Minimization [E4] (Algorithm 450). 482-483
• 
  Richard B. Goldstein:
  Chi-Square Quantiles [G1] (Algorithm 451). 483-485
• 
  C. N. Liu, Donald T. Tang:
  Enumerating Combinations of m Out of n Objects [G6] (Algorithm 452). 485
• 
  Robert Piessens:
  Gaussian Quadrature Formulas for Bromwich's Integral [D1] (Algorithm 453). 486-487
• 
  Joel A. Richardson, J. L. Kuester:
  The Complex Method for Constrained Optimization [E4] (Algorithm 454). 487-489
• 
  Gabriela Andrejková, J. Vinar:
  Complex Gamma Function (Remark and Certification on Algorithm 404). 489
• 
  Richara M. De Morgan:
  An Efficient Prime Number Generator (Remark on Algorithm 357). 489
• 
  Richard P. Watkins:
  Graph Plotter (Remark on Algorithm 412). 489-490
• 
  Albert J. Good:
  Clenshaw-Curtis Quadrature (Remark on Algorithm 424). 490
• 
  J. G. Byrne:
  Hu-Tucker Minimum Redundancy Alphabetic Coding Method (Remark on Algorithm 428). 490
• 
  Edward J. Williams:
  Localization of the Roots of a Polynomial (Remark on Algorithm 429). 490

Programming Languages

• 
  Zohar Manna, Stephen Nes, Jean Vuillemin:
  Inductive Methods for Proving Properties of Programs. 491-502
• 
  W. Wesley Peterson, Tadao Kasami, Nobuki Tokura:
  On the Capabilities of While, Repeat, and Exit Statements. 503-512

Information Retrieval and Language Processing

• 
  Caxton C. Foster:
  A Generalization of AVL Trees. 513-517

Volume 16, Number 9, September 1973

Management Science / Operations Research

• 
  Jeffrey P. Buzen:
  Computational Algorithms for Closed Queueing Networks with Exponential Servers. 527-531

Special Paper

• 
  S. Ganapathy, V. Rajaraman:
  Information Theory Applied to the Conversion of Decision Tables to Computer Programs. 532-539

Management / Data Base Systems

• 
  Alfonso F. Cardenas:
  Evaluation and Selection of File Organization - A Model and System. 540-548

Information Retrieval and Language Processing

• 
  Richard G. Casey:
  Design of Tree Structures for Efficient Querying. 549-556

Operating Systems

• 
  Juan Rodriguez-Rosell:
  Empirical Working Set Behavior. 556-560

Programming Languages

• 
  Geoffrey W. Gates, David A. Poplawski:
  A Simple Technique for Structured Variable Lookup. 561-565
• 
  Marvin V. Zelkowitz:
  Reversible Execution. 566

Numerical Mathematics

• 
  Robert E. Barnhill, David T. Pilcher:
  Sard Kernels for Certain Bivariate Cubatures. 567-570

Algorithms

• 
  D. B. Hunter, Julia M. Williams:
  Analysis of Skew Representations of the Symmetric Group (Algorithm 455). 571-572
• 
  Zdenek Fencl:
  Routing Problem (Algorithm 456). Commun. ACM 16(9): 572-574 (1973)
• 
  Coenraad Bron, Joep Kerbosch:
  Finding All Cliques of an Undirected Graph (Algorithm 457). Commun. ACM 16(9): 575-576 (1973)
• 
  Mohit Kumar Roy:
  Generation of Permutations in Lexicographic Order (Remark on Algorithm 323). Commun. ACM 16(9): 577 (1973)
• 
  E. E. Lawrence:
  A Sparse Matrix Package (Remark on Algorithm 408). 578
• 
  Hugh Williamson:
  Hidden-Line Plotting Program (Remark on Algorithm 420). 578-579
• 
  H. B. Driessen, E. W. LeM. Hunt:
  Localization of the Roots of a Polynomial (Remark on Algorithm 429). Commun. ACM 16(9): 579 (1973)

Volume 16, Number 10, October 1973

Computer Systems

• 
  John S. McGeachie:
  Multiple Terminals Under User Program Control in a Time-Sharing Environment. 587-590

Programming Techniques

• 
  Daniel G. Bobrow, Ben Wegbreit:
  A Model and Stack Implementation of Multiple Environments. 591-603

Management / Data Base Systems

• 
  Vincent Y. Lum:
  General Performance Analysis of Key-to-Address Transformation Methods Using an Abstract File Concept. 603-612

Operating Systems

• 
  Butler W. Lampson:
  A Note on the Confinement Problem. 613-615
• 
  Daniel S. Hirschberg:
  A Class of Dynamic Memory Allocation Algorithms. 615-618
• 
  Barton G. Prieve:
  Using Page Residency To Select the Working Set Parameter. 619-620

Programming Languages

• 
  Robert E. Millstein:
  Control Structures in Illiac IV Fortran. 621-627

Short Communications: Numerical Mathematics

• 
  Charles J. Mifsud, Michael J. Bohlen:
  Addendum to a Multiple-Precision Division Algorithm. 628

Algorithms

• 
  P. D. Robers, S. S. Robers:
  Discrete Linear L1 Approximation by Interval Linear Programming [E2] (Algorithm 458). 629-631
• 
  Maciej M. Syslo:
  The Elementary Circuits of a Graph [H] (Algorithm 459). 632-633
• 
  Paul E. Saylor, James D. Sebastian:
  Calculation of Optimum Parameters for Alternating Direction Implicit Procedures [D3] (Algorithm 460). 633-635
• 
  Forbes J. Burkowski, W. D. Hoskins:
  Cubic Spline Solutions to a Class of Functional Differential Equations [D2] (Algorithm 461). 635-637
• 
  Thomas G. Donnelly:
  Bivariate Normal Distribution [S15] (Algorithm 462). 638
• 
  C. R. Lewart:
  Algorithms SCALE1, SCALE2, and SCALE3 for Determination of Scales on Computer Generated Plots [J6] (Algorithm 463). 639-640

Volume 16, Number 11, November 1973

1973 ACM Turing Award Lecture

• 
  Charles W. Bachman:
  The Programmer as Navigator. 635-658

Operating Systems

• 
  Robert S. Fabry:
  Dynamic Verification of Operating System Decisions. 659-668

Programming Languages

• 
  M. D. Mikunas, Victor B. Schneider:
  A Parser-Generating System for Constructing Compressed Compilers. 669-676

Graphics and Image Processing

• 
  B. W. Jordan Jr., Ronald Curtis Barrett:
  A Scan Conversion Algorithm with Reduced Storage Requirements. 676-682

Scientific Applications

• 
  James R. Slagle, Lewis M. Norton:
  Experiments with an Automatic Theorem-Prover Having Partial Ordering Inference Rules. 682-688

Algorithms

• 
  Christian H. Reinsch:
  Eigenvalues of a Real, Symmetric, Tridiagonal Matrix [F2] (Algorithm 464). 689
• 
  G. W. Hill:
  Student's t Frequency [S14] (Algorithm 465). 690
• 
  Gideon Ehrlich:
  Four Combinatorial Algorithms [G6] (Algorithm 466). 690-691
• 
  Norman Brenner:
  Matrix Transposition in Place [F1] (Algorithm 467). 692-694
• 
  Thomas N. L. Patterson:
  Algorithm for Automatic Numerical Integration Over a Finite Interval [D1] (Algorithm 468). 694-699
• 
  Clement Wing Hong Lam, John McKay:
  Arithmetic Overa Finite Field [A1] (Algorithm 469). Commun. ACM 16(11): 699 (1973)

Computer Systems

• 
  Peter J. Denning, G. Scott Graham:
  A Note on Subexpression Ordering in the Evaluation of Arithmetic Expressions. 700-702

Short Communications: Programming Techniques

• 
  Jerome A. Feldman, James R. Low:
  Comment on Brent's Scatter Storage Algorithm. 703

Short Communications: Programming Languages

• 
  Eberhard Wegner:
  Tree-Structured Programs. 704-705

Numerical Mathematics

• 
  Herbert E. Salzer:
  A Recurrence Scheme for Converting from One Orthogonal Expansion into Another. 705-707
• 
  Frank Stenger:
  An Algorithm for the Approximate Solution of Wiener-Hopf Integral Equations. 708-710
• 
  Louis W. Ehrlich:
  Solving the Biharmonic Equation in a Square: A Direct Versus a Semidirect Method. 711-714

Volume 16, Number 12, December 1973

Report

• 
  J. Daniel Couger:
  Curriculum Recommendations for Undergraduate Programs in Information Systems. 727-749

Management / Data Base Systems

• 
  Edgar H. Sibley, Robert W. Taylor:
  A Data Definition and Mapping Language. 750-759

Algorithms

• 
  Milan Kubicek:
  Linear Systems with Almost Tridiagonal Matrix [F4] (Algorithm 470). 760-761
• 
  Walter Gautschi:
  Exponential Integrals [S13] (Algorithm 471). 761-763
• 
  John G. Herriot:
  Procedures for Natural Spline Interpolation [E1] (Algorithm 472). 763-768