January 1980 - Vol. 23 No. 1

January 1980 issue cover image

Features

Research and Advances

Performance statistics of a time sharing network at a small university

The purpose of the study was to characterize the input traffic on the interactive terminal facility (ITF) at Jackson State University by mathematical distributions. Five traffic measures were extracted from a week's job accounting records: arrival time (time of day of log on), interarrival time (time between successive arrivals), active central processing unit (CPU) time (user's time slice), inactive CPU time (swapping time), and connect time (duration of a user session). To facilitate analysis, four user groups were formed. An analysis of variance established that the group category largely determined the volume of arrivals. Since a normal distribution could not be fitted to the data, it was concluded that the pattern of daily arrivals was best treated as an empirical distribution. Using the method of moments to estimate parameters, it was found that interarrival times could best be characterized by a gamma distribution, while connect, inactive CPU, and active CPU times approximated exponential distributions.
Research and Advances

Identifying potential to acquire programming skill

Over several years, a large number of students took the same introductory programming course. The students were drawn from all academic disciplines and academic experience levels. Low correlations were found between success in the course or its evaluation components when posed against academic program, gender, or semester in school. Additionally, when the IBM Programmer's Aptitude Test was administered, the predictive value of the test was found to be low.
Research and Advances

Minimal perfect hash functions made simple

A method is presented for computing machine independent, minimal perfect hash functions of the form: hash value ← key length + the associated value of the key's first character + the associated value of the key's last character. Such functions allow single probe retrieval from minimally sized tables of identifier lists. Application areas include table lookup for reserved words in compilers and filtering high frequency words in natural language processing. Functions for Pascal's reserved words, Pascal's predefined identifiers, frequently occurring English words, and month abbreviations are presented as examples.
Research and Advances

Information transfer and area-time tradeoffs for VLSI multiplication

The need to transfer information between processing elements can be a major factor in determining the performance of a VLSI circuit. We show that communication considerations alone dictate that any VLSI design for computing the 2n-bit product of two n-bit integers must satisfy the constraint AT2 ≥ n2/64 where A is the area of the chip and T is the time required to perform the computation. This same tradeoff applies to circuits which can shift n-bit words through n different positions.
Research and Advances

Scan line methods for displaying parametrically defined surfaces

This paper presents three scan line methods for drawing pictures of parametrically defined surfaces. A scan line algorithm is characterized by the order in which it generates the picture elements of the image. These are generated left to right, top to bottom in much the same way as a picture is scanned out on a TV screen. Parametrically defined surfaces are those generated by a set of bivariate functions defining the X, Y, and Z position of points on the surface. The primary driving mechanism behind such an algorithm is the inversion of the functions used to define the surface. In this paper, three different methods for doing the numerical inversion are presented along with an overview of scan line methods.

Recent Issues

  1. November 2024 CACM cover
    November 2024 Vol. 67 No. 11
  2. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  3. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  4. August 2024 CACM cover
    August 2024 Vol. 67 No. 8