Communications of the ACM (CACM), Volume 21, 1978

Volume 21, Number 1, January 1978

Computer Architecture

• 
  Gordon Bell, Samuel H. Fuller, Daniel P. Siewiorek:
  Forword to the Special Issue on Computer Architecture. Commun. ACM 21(1): 3 (1978)
• 
  Simon H. Lavington:
  The Manchester Mark I and Atlas: A Historical Perspective. 4-12
• 
  Roland N. Ibbett, P. C. Capon:
  The Development of the MU5 Computer System. 13-24
• 
  Barry R. Borgerson, Merlin L. Hanson, P. A. Hartley:
  The Evolution of the Sperry Univac 1100 Series: A History, Analysis, and Projection. 25-43
• 
  Gordon Bell, Alan Kotok, Thomas N. Hastings, Richard Hill:
  The Evolution of the DECsystem 10. 44-63
• 
  Richard M. Russell:
  The Cray-1 Computer System. 63-72
• 
  Richard P. Case, Andris Padegs:
  Architecture of the IBM System/370. 73-96

Volume 21, Number 2, February 1978

Reports and Articles

• 
  Sandra A. Mamrak, Richard G. Montanelli Jr.:
  Computer Science Faculties: The Current Status of Minorities and Woman. 115-119

Programming Techniques

• 
  Ronald L. Rivest, Adi Shamir, Leonard M. Adleman:
  A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. 120-126
• 
  Marc A. Auslander, H. Raymond Strong:
  Systematic Recursion Removal. 127-134
• 
  Lawrence T. Kou, Larry J. Stockmeyer, C. K. Wong:
  Covering Edges by Cliques with Regard to Keyword Conflicts and Intersection Graphs. 135-139

Management Applications

• 
  Gerald Held, Michael Stonebraker:
  B-trees Re-examined. 139-143

Management Science / Operations Research

• 
  William J. Stewart:
  A Comparison of Numerical Techniques in Markov Modeling. 144-152

Scientific Applications

• 
  Gabor T. Herman, Arnold Lent, Peter H. Lutz:
  Relaxation Method for Image Reconstruction. 152-158

Programming Languages

• 
  Zohar Manna, Richard J. Waldinger:
  Is "Sometime" Sometimes Better Than "Always"? (Intermittent Assertions in Proving Program Correctness). 159-172

Graphics and Image Processing

• 
  Bruce J. Schachter, Azriel Rosenfeld:
  Some New Methods of Detecting Step Edges in Digital Pictures. 172-176

Volume 21, Number 3, March 1978

Social Impacts of Computing

• 
  Henry C. Lucas Jr.:
  The Use of an Interactive Information Storage and Retrieval System in Medical Research. 197-205
• 
  William H. Dutton, Kenneth L. Kraemer:
  Management Utilization of Computers in American Local Governments. 206-218
• 
  Ronald E. Anderson:
  Value Orientation of Computer Science Students. 219-225

Programming Techniques

• 
  S. Rao Kosaraju:
  Insertions and Deletions In One-Sided Height-Balanced Trees. 226-227
• 
  Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton:
  Preserving Average Proximity in Arrays. 218-231

Operating Systems

• 
  Mark A. Franklin, G. Scott Graham, Ram K. Gupta:
  Anomalies with Variable Partition Paging Algorithms. 232-236

Computer Systems

• 
  Andrew S. Tanenbaum:
  Implications of Structured Programming for Machine Architecture. 237-246

Volume 21, Number 4, April 1978

Scientific Applications

• 
  William H. Payne, K. L. McMillen:
  Orderly Enumeration of Nonsingular Binary Matrices Applied to Text Encryption. 259-263

Programming Techniques

• 
  Paul Heckel:
  A Technique for Isolating Differences Between Files. 264-268
• 
  Art Lew:
  Optimal Conversion of Extended-Entry Decision Tables with General Cost Criteria. 269-279
• 
  Henry G. Baker Jr.:
  List Processing in Real Time on a Serial Computer. 280-294
• 
  Ralph C. Merkle:
  Secure Communications Over Insecure Channels. 294-299
• 
  Thomas G. Szymanski:
  Assembling Code for Machines with Span-Dependent Instructions. 300-308
• 
  Jean Vuillemin:
  A Data Structure for Manipulating Priority Queues. 309-315
• 
  Shimon Even, Michael Rodeh:
  Economical Encoding of Commas Between Strings. 315-317

Management Science / Operations Research

• 
  Russell C. H. Cheng:
  Generating Beta Variates with Nonintegral Shape Parameters. 317-322

Volume 21, Number 5, May 1978

Programming Techniques

• 
  Douglas W. Clark:
  A Fast Algorithm for Copying List Structures. 351-357

Programming Languages

• 
  Anita K. Jones, Barbara H. Liskov:
  A Language Extension for Expressing Constraints on Data Access. 358-367
• 
  Matthew M. Geller:
  Test Data as an Aid in Proving Program Correctness. 368-375
• 
  James R. Low:
  Automatic Data Structure Selection: An Example and Overview. 376-385
• 
  Michael Karr, David B. Loveman:
  Incorporation of Units into Programming Languages. 385-391
• 
  David R. Hanson, Ralph E. Griswold:
  The SL5 Procedure Mechanism. 392-400

Artificial Intelligence / Language Processing

• 
  Frederick Hayes-Roth, John P. McDermott:
  An Interference Matching Technique for Inducing Abstractions. 401-410

Management Science / Operations Research

• 
  J. M. Fleisher, Robert R. Meyer:
  New Sufficient Optimality Conditions for Integer Programming and their Application. 411-418
• 
  Pandu R. Tadikamalla:
  Computer Generation of Gamma Random Variables. 419-422

Computer Systems

• 
  Richard L. Sites:
  Optimal Shift Strategy for a Block-Transfer CCD Memory. 423-425

Volume 21, Number 6, June 1978

Programming Techniques

• 
  Stuart H. Zweben, M. A. McDonald:
  An Optimal Method for Deletion in One-Sided Height-Balanced Trees. 441-445
• 
  James R. Driscoll, Y. Edmund Lien:
  A Selective Traversal Algorithm for Binary Search Trees. 445-447

Programming Languages

• 
  Jacques Cohen, Martin A. Roth:
  Analyses of Deterministic Parsing Algorithms. 448-458
• 
  M. Dennis Mickunas, John A. Modry:
  Automatic Error Recovery for LR Parsers. 459-465

Management Applications

• 
  Bennet P. Lientz, E. Burton Swanson, G. E. Tompkins:
  Characteristics of Applications Software Maintenance. 466-471
• 
  Earl Chrysler:
  Some Basic Determinants of Computer Programming Productivity. 472-483
• 
  Rob Kling:
  Automated Welfare Client-Tracking and Service Integration: The Political Economy of Computing. 484-493

Operating Systems

• 
  Erol Gelenbe, D. Derochette:
  Performance of Rollback Recovery Systems under Intermittent Failures. 493-499

Computer Systems

• 
  Toby J. Teorey:
  General Equations for Idealized CPU-I/O Overlap Configurations. 500-507

Volume 21, Number 7, July 1978

Artificial Intelligence / Language Processing

• 
  David L. Waltz:
  An English Language Query Answering System for a Large Relational Data Base. 526-539

Programming Techniques

• 
  Michael L. Fredman, Bruce W. Weide:
  On the Complexity of Computing the Measure of U[ai, bi]. 540-544
• 
  Francis Y. L. Chin:
  An O(n) Algorithm for Determining a Near-Optimal Computation Order of Matrix Chain Products. 544-549
• 
  Yehoshua Perl, Alon Itai, Haim Avni:
  Interpolation Search - A Log Log N Search. 550-553
• 
  Constantine Halatsis, George Philokyprou:
  Pseudochaining in Hash Tables. 554-557

Operating Systems

• 
  Leslie Lamport:
  Time, Clocks, and the Ordering of Events in a Distributed System. 558-565

Programming Languages

• 
  Henry G. Baker:
  Shallow Binding in LISP 1.5. 565-569
• 
  Hanan Samet:
  Proving the Correctness of Heuristically Optimized Code. 570-582
• 
  Robert E. Shostak:
  An Algorithm for Reasoning About Equality. 583-585

Computer Systems

• 
  Rahul Chattergy, Udo W. Pooch:
  Analysis of the Availability of Computer Systems Using Computer-Aided Algebra. 586-591

Technical Correspondence

• 
  Arne Maus:
  Interlude on signals and semephores revisited. 592
• 
  Niklaus Wirth:
  Interlude on signals and semphores revisited. author's response. 592
• 
  Duane Sand:
  Thoughtless programming. 592-593
• 
  Marc A. Auslander:
  Thoughtless programming? author's response. 593
• 
  Percy Tzelnic:
  On LRU stack model suitability. 593
• 
  Rollins Turner:
  On LRU stack model suitability. author's response. 594
• 
  Lawrence Snyder:
  On B-trees Re-examined. 594
• 
  Gerald Held, Michael Stonebraker:
  On B-trees Re-examined - Authors' Response. 594

Volume 21, Number 8, August 1978

1977 ACM Turing Award Lecture

• 
  John W. Backus:
  Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. 613-641

Reports and Articles

• 
  Rob Kling:
  Value Conflicts and Social Choice in Electronic Funds Transfer System Developments. 642-657

Programming Techniques

• 
  Daniel S. Hirschberg:
  Fast Parallel Sorting Algorithms. 657-661
• 
  F. Lockwood Morris:
  A Time- and Space-Efficient Garbage Compaction Algorithm. 662-665

Programming Languages

• 
  C. A. R. Hoare:
  Communicating Sequential Processes. 666-677

Computer Systems

• 
  Richard S. Brice, James C. Browne:
  Feedback Coupled Resource Allocation Policies in the Multiprogramming-Multicomputer System. 678-686

Self-Assessment Procedure

• 
  Peter Scheuermann, C. Robert Carlson:
  Self-Assessment Procedure V: Database Systems. 687-693

Volume 21, Number 9, September 1978

Scientific Applications

• 
  R. A. Harris, J. D. Zund:
  An Algorithm Using Symbolic Techniques for the Bel-Petrov Classification of Gravitational Fields. 715-717

Computer Systems

• 
  Herbert D. Schwetman:
  Hybrid Simulation Models of Computer Systems. 718-723

Programming Languages

• 
  Jeffrey M. Barth:
  A Practical Interprocedural Data Flow Analysis Algorithm. 724-736

Operating Systems

• 
  Gerald J. Popek, David A. Farber:
  A Model for Verification of Data Security in Operating Systems. 737-749
• 
  Peter J. Denning, Donald R. Slutz:
  Generalized Working Sets for Segment Reference Strings. 750-759

Programming Techniques

• 
  Glenford J. Myers:
  A Controlled Experiment in Program Testing and Code Walkthroughs/Inspections. 760-768
• 
  Thomas Ottmann, Hans-Werner Six, Derick Wood:
  Right Brother Trees. 769-776

Management Science / Operations Research

• 
  Ernst G. Ulrich:
  Event Manipulation for Discrete Simulations Requiring Large Numbers of Events. 777-785

Short Communications

• 
  Kurt Maly:
  A Note on Virtual Memory Indexes. 786-787
• 
  Stephen A. Ward:
  Real Time Plotting of Approximate Contour Maps. 788-790
• 
  Aaron M. Tenenbaum:
  Simulations of Dynamic Sequential Search Algorithms. 790-791

Volume 21, Number 10, October 1978

Reports and Articles

• 
  Walter S. Brainerd:
  FORTRAN 77. 806-820

Computer Systems and Architecture

• 
  Donald F. Towsley, K. Mani Chandy, James C. Browne:
  Models for Parallel Processing Within Programs: Application to CPU: I/O and I/O: I/O Overlap. 821-831

Programming Techniques

• 
  Ben Shneiderman:
  Jump Searching: A Fast Sequential Search Technique. 831-834
• 
  Shi-Kuo Chang, Yin-Wah Wong:
  Optimal Histogram Matching by Monotone Gray Level Transformation. 835-840
• 
  Robert H. Morris Sr.:
  Counting Large Numbers of Events in Small Registers. 840-842
• 
  Colin L. McMaster:
  An Analysis of Algorithms for the Dutch National Flag Problem. 842-846
• 
  Robert Sedgewick:
  Implementing Quicksort Programs. 847-857
• 
  Gordon Lyon:
  Packed Scatter Tables. 857-865

Operating Systems

• 
  Malcolm C. Easton, Ronald Fagin:
  Cold-Start vs. Warm-Start Miss Ratios. 866-872

Short Communications

• 
  William R. Franta, Kurt Maly:
  A Comparison of Heaps and the TL Structure for the Simulation Event Set. 873-875

Volume 21, Number 11, November 1978

Reports and Articles

• 
  Norman R. Lyons:
  Systems Design Education: A Gaming Approach. 889-895

Student Award Paper

• 
  J. W. Wendorf:
  A Simply Extended and Modified Batch Environment Graphical System (SEMBEGS). 897-904

Computer Systems and Architecture

• 
  B. Kumar, Edward S. Davidson:
  Performance Evaluation of Highly Concurrent Computers by Deterministic Simulation. 904-913

Graphics and Image Processing

• 
  Berthold K. P. Horn, Brett L. Bachman:
  Using Synthetic Images to Register Real Images with Surface Models. 914-924

Management Science/Operations Research

• 
  Pandu R. Tadikamalla:
  Computer Generation of Gamma Random Variables - II. 925-928

Programming Languages

• 
  G. David Ripley:
  A Simple Recovery-Only Procedure For Simple Precedence Parsers. 928-930
• 
  Daniel P. Friedman, David S. Wise:
  A Note on Conditional Expressions. 931-933
• 
  Per Brinch Hansen:
  Distributed Processes: A Concurrent Programming Concept. 934-941

Programming Techniques

• 
  Fabrizio Luccio, Linda Pagli:
  Power Trees. 941-947
• 
  B. A. Sheil:
  Median Split Trees: A Fast Lookup Technique for Frequently Occurring Keys. 947-958
• 
  Eugene C. Freuder:
  Synthesizing Constraint Expressions. 958-966

Operating Systems

• 
  Edsger W. Dijkstra, Leslie Lamport, Alain J. Martin, Carel S. Scholten, Elisabeth F. M. Steffens:
  On-the-Fly Garbage Collection: An Exercise in Cooperation. 966-975

Volume 21, Number 12, December 1978

Operating Systems

• 
  Roger M. Needham, Michael D. Schroeder:
  Using Encryption for Authentication in Large Networks of Computers. 993-999

Programming Techniques

• 
  David Gries, Jayadev Misra:
  A Linear Sieve Algorithm for Finding Prime Numbers. 999-1003
• 
  James L. Peterson, James R. Bitner, John H. Howard:
  The Selection of Optimal Tab Settings. 1004-1007

Management Applications

• 
  James C. Wetherbe, V. Thomas Dock:
  A Strategic Planning Methodology for the Computing Effort in Higher Education: An Empirical Evaluation. 1008-1015
• 
  M. Ibramsha, V. Rajaraman:
  Detection of Logical Errors in Decition Table Programs. 1016-1025
• 
  Alberto Martelli, Ugo Montanari:
  Optimizing Decision Trees Through Heuristically Guided Search. 1025-1039

Computer Architecture and Systems

• 
  Yogen K. Dalal, Robert Metcalfe:
  Reverse Path Forwarding of Broadcast Packets. 1040-1048

Programming Languages

• 
  John V. Guttag, Ellis Horowitz, David R. Musser:
  Abstract Data Types and Software Validation. 1048-1064
• 
  Jay M. Spitzen, Karl N. Levitt, Lawrence Robinson:
  An Example of Hierarchical Design and Proof. 1064-1075