This paper considers allocation of space in a hnear storage medium when space must be allocated dynamically as customers arrive A heuristic is proposed for this problem and for a simple model of the resultmg reference sequence, we show that the average distance between consecutive references is asymptotically 7n/30, where n is the size of the storage For optimal static placement where one waits for all arrivals before any space allocation, the average distance is shown to be asymptotically 7n/30 For random placement, the average distance is asymptotically n/3 Thus, the heuristic is asymptotically optimal in a strong sense For reasonable values of n, we demonstrate that the heuristic is nearly as good as optimal static placement and much better than random placement KEY WORDS AND PHRASES minimization of disk seek time, minidisks, linear store, dynamic allocation of storage space, concrete complexity, optimal algorithms, asymptotically optimal algorithms, analysts of algorithms, heuristics CR CATEGORIES 4 35, 5 25 Notational ConventionsWe must deal with a set of n users who arrive at n distinct points in time, and who are General permission to make fair use in teachmg or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice ts given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by

We consider the problem of placing records in a 2-dimensional storage array so that expected distance between consecutive references is minimized. A simple placement heuristic which uses only relative frequency of access for different records is shown to be within an additive constant of optimal when distance is measured by the Euclidean metric. For the rectilinear and maximum metrics, we show that there is no such heuristic. For the special case in which all access probabilities are equal, however, heuristics within an additive constant of optimal do exist, and their implementation requires solution of differential equations for which we give numerical solutions.

An algorithm for obtaining all simple disjunctive decompositions of a switching function is described. It operates on a function given as an expression using the operations AND, EXCLUSIVE OR, and complementation. It uses necessary conditions for the existence of a decomposition to eliminate sets of bound sets from consideration. Thus this technique differs from existing methods in that it attempts to test fewer bound sets at the expense of additional analysis. The algorithm can also be applied to functions given in a canonical form. It is shown that for a collection of functions of n variables chosen at random, the time required grows as n3. Previous methods, on the other hand, have an exponential growth rate.

The methods currently in use and previously proposed for the choice of a root in minimal storage tree sorting are in reality methods for making inefficient statistical estimates of the median of the sequence to be sorted. By making efficient use of the information in a random sample chosen during input of the sequence to be sorted, significant improvements over ordinary minimal storage tree sorting can be made. A procedure is proposed which is a generalization of minimal storage tree sorting and which has the following three properties: (a) There is a significant improvement (over ordinary minimal storage tree sorting) in the expected number of comparisons required to sort the input sequence. (b) The procedure is statistically insensitive to bias in the input sequence. (c) The expected number of comparisons required by the procedure approaches (slowly) the information-theoretic lower bound on the number of comparisons required. The procedure is, therefore, “asymptotically optimal.”

An algorithm for obtaining all simple disjunctive decompositions of a switching function is described. The algorithm proceeds by testing for all decompositions with a bound set of size two. Under given conditions, this test for a pair of variables will show that some larger bound sets, containing the two variables for which the test was conducted, cannot yield a decomposition. The remaining bound sets require further testing. Thus this algorithm differs from existing techniques in that it attempts to test fewer bound sets at the expense of additional analysis. The relative merit of this algorithm is discussed.

Abstract—A particular method for storage of first-in-first-out queues in random access memory is analyzed. The storage scheme gives minimum overhead costs at the expense of storage utilization. The resulting queue is analyzed as a Markov chain and the stationary, joint probability distribution is obtained for the queue length and the relative location of the head of the queue. Expressions for the mean length and the locations of the head and the tail of the queue are also derived.