Communications of the ACM (CACM), Volume 15, 1972

Volume 15, Number 1, January 1972

Scientific Applications

• 
  Arthur M. Lesk:
  Pictorial Pattern Recognition and the Phase Problem of X-ray Crystallography. 3-6

Graphics and Image Processing

• 
  Stefano Levialdi:
  On Shrinking Binary Picture Patterns. 7-10
• 
  Richard O. Duda, Peter E. Hart:
  Use of the Hough Transformation to Detect Lines and Curves in Pictures. 11-15

Computer Systems

• 
  Edgar T. Irons, Frans M. Djorup:
  A CRT Editing System. 16-20

Education

• 
  Thomas A. Dwyer:
  Teacher/Student Authored CAI Using the NEWBASIC System. 21-28

Computational Linguistics

• 
  Gordon I. McCalla, Jeffrey R. Sampson:
  MUSE: A Model To Understand Simple English. 29-40

Numerical Mathematics

• 
  Richard I. Shrager:
  Quadratic Programming for Nonlinear Regression. 41-45
• 
  Herbert E. Salzer:
  Ordering +-f(+-f(+-f(...+-f(x)..))) When f(x) Is Positive Monotonic. Commun. ACM 15(1): 45-46 (1972)

Algorithms

• 
  Bo Einarsson:
  Calculation of Fourier Integrals [D1] (Algorithm 418). Commun. ACM 15(1): 47-48 (1972)
• 
  Iain D. G. Macleod:
  In-Situ Transposition of a Rectangular Matrix [F1] (Certification of Algorithm 380). Commun. ACM 15(1): 49 (1972)
• 
  Günther F. Schrack:
  Unitary Symmetric Polynomials [Z] (Remark on Algorithm 391). Commun. ACM 15(1): 49 (1972)

Volume 15, Number 2, February 1972

Scientific Applications

• 
  David Pager:
  A Proposal for a Computer-Based Interactive Scientific Community. 71-75
• 
  Charles M. Eastman:
  Preliminary Report on a System for General Space Planning. 76-87

Management / Data Base Systems

• 
  William A. Martin, David N. Ness:
  Optimizing Binary Trees Grown with a Sorting Algorithm. 88-93

Computer Systems

• 
  Arthur E. Oldehoeft, Maurice H. Halstead:
  Maximum Computing Power and Cost Factors in the Centralization Problem. 94-96

Algorithms

• 
  Michael A. Jenkins, Joseph F. Traub:
  Zeros of a Complex Polynomial [C2] (Algorithm 419). 97-99
• 
  Hugh Williamson:
  Hidden-Line Plotting Program [J6] (Algorithm 420). 100-103

Computational Linguistics

• 
  James Anderson Moorer:
  Music and Computer Composition. 104-113

Volume 15, Number 3, March 1972

Papers from the Third ACM Symposium on Operating System Principles (SOSP 1971)

• 
  Daniel G. Bobrow, Jerry D. Burchfiel, Daniel L. Murphy, Raymond S. Tomlinson:
  TENEX, a Paged Time Sharing System for the PDP-10. 135-143
• 
  Barbara H. Liskov:
  The Design of the Venus Operating System. 144-149
• 
  R. Stockton Gaines:
  An Operating System Based on the Concept of a Supervisory Computer. 150-156
• 
  Michael D. Schroeder, Jerome H. Saltzer:
  A Hardware Architecture for Implementing Protection Rings. 157-170
• 
  A. Nico Habermann:
  Synchronization of Communicating Processes. 171-176
• 
  Toby J. Teorey, Tad B. Pinkerton:
  A Comparative Analysis of Disk Scheduling Policies. 177-184
• 
  Edward G. Coffman Jr., T. A. Ryan:
  A Study of Storage Partitioning Using a Mathematical Model of Locality. 185-190
• 
  Peter J. Denning, Stuart C. Schwartz:
  Properties of the Working Set Model. 191-198

Volume 15, Number 4, April 1972

Management / Data Base Systems

• 
  Richard W. Conway, William L. Maxwell, Howard L. Morgan:
  On the Implementation of Security Measures in Information Systems. 211-220

Computer Systems

• 
  David C. Walden:
  A System for Interprocess Communication in a Resource Sharing Computer Network. 221-230
• 
  Noel M. Herbst, Peter M. Will:
  An Experimental Laboratory for Pattern Recognition and Signal Processing. 231-244

Scientific Applications

• 
  Yutaka Matsushita:
  Hidden Lines Elimination for a Rotating Object. 245-252
• 
  Stephen M. Chase:
  An Implemented Graph Algorithm for Winning Shannon Switching Games. 253-256

Education

• 
  Ellis Horowitz, Howard L. Morgan, Alan C. Shaw:
  Computers and Society: A Proposed Course for Computer Scientists. 257-261

Numerical Mathematics

• 
  Hirondo Kuki:
  Complex Gamma Function with Error Control. 262-267
• 
  Cleve B. Moler:
  Matrix Computations with Fortran and Paging. 268-270

Algorithms

• 
  Hirondo Kuki:
  Complex Gamma Function with Error Control [S14] (Algorithm 421). 271-272
• 
  V. Kevin M. Whitney:
  Minimal Spanning Tree [H] (Algorithm 422). 273-274
• 
  Cleve B. Moler:
  Linear Equation Solver [F4] (Algorithm 423). Commun. ACM 15(4): 274 (1972)

Programming Techniques

• 
  David C. Walden:
  A Note on Cheney's Nonrecursive List-Compacting Algorithm. 275

Information Retrieval

• 
  T. C. Hu:
  A Comment on the Double-Chained Tree. 276

Volume 15, Number 5, May 1972

Management / Data Base Systems

• 
  James K. Mullin:
  An Improved Index Sequential Access Method Using Hashed Overflow. 301-307

Operating Systems

• 
  A. Bensoussan, C. T. Clingen, Robert C. Daley:
  The Multics Virtual Memory: Concepts and Design. 308-318
• 
  Ronald D. Christman:
  MUX, a Simple Approach to On-Line Computing. 319-329

Programming Techniques

• 
  David Lorge Parnas:
  A Technique for Software Module Specification with Examples. 330-336

Numerical Mathematics

• 
  W. Morven Gentleman:
  Implementing Clenshaw-Curtis Quadrature, I Methodology and Experience. 337-342
• 
  W. Morven Gentleman:
  Implementing Clenshaw-Curtis Quadrature, II Computing the Cosine Transformation. 343-346
• 
  Donald Greenspan, D. Schultz:
  Fast Finite-Difference Solution of Biharmonic Problems. 347-350
• 
  Charles B. Dunham:
  Minimax Nonlinear Approximation by Approximation on Subsets. 351
• 
  Richard Harter:
  The Optimality of Winograd's Formula. 352

Algorithms

• 
  W. Morven Gentleman:
  Clenshaw-Curtis Quadrature [D1] (Algorithm 424). 353-355
• 
  Rex L. Hurst, Robert E. Knop:
  Generation of Random Correlated Normal Variables [G5] (Algorithm 425). 355-357
• 
  Coenraad Bron:
  Merge Sort Algorithm [M1] (Algorithm 426). 357-358
• 
  Peter Linz:
  Fourier Cosine Integral [D1] (Algorithm 427). 358-360
• 
  J. Michael Yohe:
  Hu-Tucker Minimum Redundancy Alphabetic Coding Method [Z] (Algorithm 428). 360-362

Report

• 
  Robert L. Ashenhurst:
  Curriculum Recommendations for Graduate Professional Programs in Information Systems. 363-398

Volume 15, Number 6, June 1972

Computer Systems

• 
  J. Blatny, S. R. Clark, T. A. Rourke:
  On the Optimization of Performance of Time-Sharing Systems by Simulation. 411-420

Operating Systems

• 
  Thomas R. Spacek:
  A Proposal To Establish a Pseudo Virtual Memory via Writable Overlays. 421-426
• 
  Philip Gilbert, W. J. Chandler:
  Interference Between Communicating Parallel Processes. 427-437

Programming Languages

• 
  James F. Gimpel:
  Blocks - A New Data type for SNOBOL4. 438-447
• 
  David F. Martin:
  A Boolean Matrix Method for the Computation of Linear Precedence Functions. 448-454

Scientific Applications

• 
  Robert T. O'Reagan:
  Computer-Assigned Codes from Verbal Responses. 455-459

Numerical Mathematics

• 
  Ken Iguchi:
  A Starting Method for Solving Nonlinear Volterra Integral Equations of the Second Kind. 460-461

Programming Techniques

• 
  Ira Pohl:
  A Sorting Problem and Its Complexity. 462-464

Algorithms

• 
  Kurt Siegfried Kölbig:
  Complex Error Function (Certification of Algorithm 363). 465-466
• 
  Herbert Niessner:
  Eigenvalues and Eigenvectors of a Real General Matrix (Remark on Algorithm 343). 466
• 
  Les G. Proll:
  General Random Number Generator (Remark on Algorithm 370). 467-468
• 
  Günther F. Schrack:
  Random Vectors Uniform is Solid Angle (Remark on Algorithm 381). 468
• 
  Arthur H. J. Sale:
  Special Series Summation with Arbitrary Precision (Remark on Algorithm 393). 468-469
• 
  Stephen C. Johnson, Brian W. Kernighan:
  An Integer Programming Problem (Remark on Algorithm 397). 469
• 
  Bo Einarsson:
  Calculation of Fourier Integrals (Remark on Algorithm 418). 469

Education

• 
  Abraham Kandel:
  Computer Science - A Vicious Circle. 470-471
• 
  Elliot B. Koffman:
  Individualizing Instruction in a Generative CAI Tutor. 472-473

Volume 15, Number 7, July 1972

25 Years ACM

• 
  Lee Revens:
  The First Twenty-Five Years. 485-490
• 
  Eric A. Weiss:
  Publications in Computing: An Informal Review. 491-497
• 
  Anthony Ralston:
  The Next Two Years (ACM President's Letter). 499-500
• 
  Andrei P. Ershov:
  Aestetics and Human Factor in Programming. 501-505
• 
  G. G. Probst, Robert S. Oelman, Sam Wyly, C. Lester Hogan, F. T. Cary, Gordon Bell, Donald P. Kircher:
  As the Industry Sees It. 506-517

Fundamentals

• 
  Michael A. Arbib:
  Toward an Automata Theory of Brains. 521-527
• 
  Zohar Manna, Jean Vuillemin:
  Fix Point Approach to the Theory of Computation. 528-536
• 
  Joseph F. Traub:
  Numerical Mathematics and Computer Science. 537-541
• 
  David F. Shanno, Roman L. Weil:
  Management Science: A View from Nonlinear Programming. 542-549
• 
  Joel Moses:
  Toward a General Theory of Special Functions. 550-554

Computerware

• 
  Caxton C. Foster:
  A View of Computer Architecture. 557-565
• 
  Alexander G. Fraser:
  On the Interface Between Computers and Data Communications Systems. 566-573
• 
  Per Brinch Hansen:
  Structured Multiprogramming. 574-578
• 
  William C. Lynch:
  Operating System Performance. 579-585
• 
  Stephen R. Kimbleton:
  The Role of Computer System Models in Performance Evaluation. 586-590
• 
  Saul Rosen:
  Programming Systems and Languages 1965-1975. 591-600
• 
  Jean E. Sammet:
  Programming Languages: History and Future. 601-610
• 
  Lloyd D. Fosdick:
  The Production of Better Mathematical Software. 611-617
• 
  Daniel G. Bobrow:
  Requirements for Advanced Programming Systems for List Processing. 618-627
• 
  Charles W. Bachman:
  The Evolution of Storage Structures. 628-634

Applications

• 
  John R. Rice:
  On the Present and Future of Scientific Computation. 637-639
• 
  Robert I. Benjamin:
  A Generational Perspective of Information System Development. 640-647
• 
  Sally Yeates Sedelow:
  Language Analysis in the Humanities. 644-647
• 
  Karl L. Zinn:
  Computers in the Instructional Process: Directions for Research and Development. 648-651
• 
  Gerald M. Sturman:
  Computers and Urban Society. 652-657
• 
  Gerard Salton:
  Dynamic Document Processing. 658-668

Perspectives

• 
  Donald E. Knuth:
  Ancient Babylonian Algorithms. 671-677
• 
  Friedrich L. Bauer, Hans Wössner:
  The "Plankalkül" of Konrad Zuse: A Forerunner of Today's Programming Languages. 679-685
• 
  Richard E. Sprague:
  A Western View of Computer History. 686-692
• 
  Franz L. Alt:
  Archaeology of Computers - Reminiscences, 1945-1947. 693-694
• 
  Allan Borodin, C. C. Gotlieb:
  Computers and Employment. 695-702

Volume 15, Number 8, August 1972

George E. Forsythe Student Paper Competition

• 
  John G. Herrit:
  In Memory of George E. Forsythe. 719-720
• 
  Donald E. Knuth:
  George Forsythe and the Development of Computer Science. 721-726
• 
  David Crowe:
  Generating Parsers for Affix Grammars. 728-734
• 
  Robert E. Helbig, Patrick K. Orr, Robert R. Roediger:
  Political Redistricting by Computer. 735-741
• 
  Arthur J. Benjamin:
  An Extensible Editor for a Small Machine with Disk Storage. 742-747

Computer Systems

• 
  Robert F. Rosin, Gideon Frieder, Richard H. Eckhouse Jr.:
  An Environment for Research in Microprogramming and Emulation. 748-760

Operating Systems

• 
  Peter H. Oden, Gerald S. Shedler:
  A Model of Memory Contention in a Paging Machine. 761-771

Short Communications

• 
  Herbert J. Bernstein:
  Compiling Fixed-Point Multiplications. 772
• 
  W. L. van der Poel:
  Comment on the Composition of Semantics in Algol 68. 772
• 
  James H. Morris Jr.:
  A Bonus from van Wijngaarden's Device. 773
• 
  Peter R. Jones:
  Comment on Average Binary Search Length. 774
• 
  Ronald C. Read:
  A Note on the Generation of Rosary Permutations. 775

Algorithms

• 
  William Squire:
  Localization of the Roots of a Polynomial [C2] (Algorithm 429). 776-777
• 
  Paul Walton Purdom Jr., Edward F. Moore:
  Immediate Predominators in a Directed Graph [H] (Algorithm 430). 777-778

Volume 15, Number 9, September 1972

Computer Systems

• 
  Karl N. Levitt, William H. Kautz:
  Cellular Arrays for the Solution of Graph Problems. 789-801

Information Retrieval

• 
  Sakti P. Ghosh:
  File Organization: The Consecutive Retrieval Property. 802-808

Graphics and Image Processing

• 
  Moshe Mor, T. Lamdan:
  A New Approach to Automatic Scanning of Contour Maps. 809-812

Numerical Mathematics

• 
  Paul L. Richman:
  Automatic Error Analysis for Determining Precision. 813-817

Algorithms

• 
  Arunachalam Ravindran:
  Computer Routine for Quadratic and Linear Programming Problems [H] (Algorithm 431). 818-820
• 
  Richard H. Bartels, G. W. Stewart:
  Solution of the Matrix Equation AX+XB=C [F4] (Algorithm 432). 820-826

Scientific Applications

• 
  Edward S. Deutsch:
  Thinning Algorithms on Rectangular, Hexagonal, and Triangular Arrays. 827-837

Short Communications: Numerical Mathematics

• 
  James Gregory:
  A Comparison of Floating Point Summation Methods. 838
• 
  Hatem M. Khalil:
  The Eigenproblem of Block Tridiagonal Matrices. 839

Short Communications: Operating Systems

• 
  David Lorge Parnas, A. Nico Habermann:
  Comment on Deadlock Prevention Method. 840-841

Short Communications: Scientific Applications

• 
  Richard Rubinstein, Julian Feldman:
  A Controller for a Braille Terminal. 841-842

Short Communications: Information Retrieval

• 
  Kay Chen Tan:
  On Foster's Information Storage and Retrieval Using AVL Trees. 843

Volume 15, Number 10, October 1972

1972 Turing Award Lecture

• 
  Edsger W. Dijkstra:
  The Humble Programmer. 859-866

Computer Systems

• 
  James B. Morris:
  Demand Paging Through Utilization of Working Sets on the MANIAC II. 867-872

Management / Data Base Systems

• 
  Joachim H. Ahrens, Ulrich Dieter:
  Computer Methods for Sampling from the Exponential and Normal Distributions. 873-882

Scientific Applications

• 
  Richard J. Hanson:
  Integral Equations of Immunology. 883-890
• 
  Robert F. Simmons, Jonathan Slocum:
  Generating English Discourse from Semantic Networks. 891-905

Programming Techniques

• 
  Gert Dathe:
  Conversion of Decision Tables By Rule Mask Method Without Rule Mask. 906-909
• 
  W. Donald Frazer, C. K. Wong:
  Sorting by Natural Selection. 910-913

Algorithms

• 
  Hiroshi Akima:
  Interpolation and Smooth Curve Fitting Based on Local Procedures [E2] (Algorithm A433). 914-918
• 
  J. Douglas Robertson:
  Tableless Date Conversion (Remark on Algorithm 398). Commun. ACM 15(10): 918 (1972)

Volume 15, Number 11, November 1972

Numerical Mathematics

• 
  Phyllis Fox:
  A Comparative Study of Computer Programs for Integrating Differential Equations. 941-948
• 
  Michael A. Malcolm:
  Algorithms To Reveal Properties of Floating-Point Arithmetic. 949-951
• 
  Merrell L. Patrick:
  A Highly Parallel Algorithm for Approximating All Zeros of a Polynomial with Only Real Zeros. 952-955

Programming Languages

• 
  Henry F. Ledgard:
  A Model for Type Checking - with an Application to ALGOL 60. 956-966
• 
  Peter Henderson:
  Derived Semantics for Some Programming Language Constructs. 967-973

Programming Techniques

• 
  Maurice Verhelst:
  The Conversion of Limited-Entry Decision Tables to Optimal and Near-Optimal Flowcharts: Two New Algorithms. 974-980

Operating Systems

• 
  H. D. Baecker:
  Garbage Collection for Virtual Memory Computer Systems. 981-986

Management Science / Operations Research

• 
  John S. Ramberg, Bruce W. Schmeiser:
  An Approximate Method for Generating Symmetric Random Variables. 987-990

Algorithms

• 
  David L. March:
  Exact Probabilities for R x C Contingency Tables [G2] (Algorithm 434). 991-992
• 
  Wayne Fullerton:
  Modified Incomplete Gamma Function [S14] (Algorithm 435). 993-995

Short Communications: Information Retrieval

• 
  Vincent Y. Lum, Pasteur S. T. Yuen:
  Additional Results on Key-to-Address Transform Techniques: A Fundamental Performance Study on Large Existing Formatted Files. 996-997
• 
  Steve Kennedy:
  A Note on Optimal Doubly-Chained Trees. 997-998

Short Communications: Computer Systems

• 
  Murray A. Eisenberg, Michael R. McGuire:
  Further Comments on Dijkstra's Concurrent Programming Control Problem. 999

Short Communications: Computational Linguistics

• 
  Stephen W. Smoliar:
  Comments on Moorer's Music and Computer Composition. 1000-1001

Volume 15, Number 12, December 1972

Programming Languages

• 
  J. Richard Phillips, H. C. Adams:
  Dynamic Partitioning for Array Languages. 1023-1032
• 
  Rudolf Bayer, Christoph Witzgall:
  Index Ranges for Matrix Calculi. 1033-1039
• 
  Jay Earley, Paul Caizergues:
  A Method for Incrementally Compiling Languages with Nested Statement Structure. 1040-1044

Information Retrieval

• 
  Fabrizio Luccio:
  Weighted Increment Linear Search for Scatter Tables. 1045-1047

Numerical Mathematics

• 
  Donald R. Barr, Norman L. Sezak:
  A Comparison of Multivariate Normal Generators. 1048-1049
• 
  John Moore, Prentiss Robinson:
  A New Method for the Solution of the Cauchy Problem for Parabolic Equations. 1050-1052

Programming Techniques

• 
  David Lorge Parnas:
  On the Criteria To Be Used in Decomposing Systems into Modules. 1053-1058
• 
  P. J. Brown:
  Levels of Language for Portable Software. 1059-1062

Operating Systems

• 
  Stephen W. Sherman, Forest Baskett, James C. Browne:
  Trace-Driven Modeling and Analysis of CPU Scheduling in Multiprogramming System. 1063-1069

Algorithms

• 
  W. Robert Boland:
  Product Type Trapezoidal Integration (Algorithm 436). 1070
• 
  W. Robert Boland:
  Product Type Simpson's Integration [D1] (Algorithm 437). 1070-1071
• 
  W. Robert Boland:
  Product Type Two-Point Gauss-Legendre-Simpson's Integration [D1] (Algorithm A438). 1071
• 
  W. Robert Boland:
  Product Type Three-point Gauss-Legendre-Simpson's Integration [D1] (Algorithm 439). 1072
• 
  Walter L. Sullins:
  Pseudo-Random Numbers [G5] (Certification of Algorithm 266). 1072-1073
• 
  P. Hallet, E. Mund:
  Squank (Certification of Algorithm 379). 1073
• 
  Ernst J. Schuegraf:
  Least Squares Surface Fit (Remark on Algorithm 176). 1073
• 
  Ernst J. Schuegraf:
  BANDSOLVE (Remark on Algorithm 195). 1074
• 
  D. R. T. Marshall:
  Decision Table Translation (Remark on Algorithm 394). 1074
• 
  Michael J. Frisch:
  Remarks on Characteristic Values and Associated Solutions of Mathieus Differential Equation, Exponential Integral, and Systems of Hyperbolic P.D.E. (Remark on Algorithms 352, 385, 392). 1074
• 
  Richard M. Heiberger:
  Roots of Matrix Pencils (Remark on Algorithm 405). 1075