In this paper, we are concerned with the merging of two linearly-ordered listsA andB consisting of elements:a1<a2<...<b n . The Hwang-Lin merging algorithm was considered very efficient for merging two lists ...
详细信息
In this paper, we are concerned with the merging of two linearly-ordered listsA andB consisting of elements:a1
Given the input-output behavior of a stochastic automaton and a map which compares output words, optimal controls are introduced, and an explicit formula for such a control is derived by means of linear programming te...
详细信息
Given the input-output behavior of a stochastic automaton and a map which compares output words, optimal controls are introduced, and an explicit formula for such a control is derived by means of linear programming techniques. The second part of the paper deals with the situation in which an inputand an output word are given and the probability with which the optimal control puts out the word is requested. An algorithm for computing this probability is presented and analysed with respect to its behavior in the worst and in the average case. The latter analysis develops some new techniques, which are necessary since an uncountable variety of possible inputs has to be considered. These techniques come mainly from real analysis, in particular from measure theory.
Reports on the use of coalesced hashing for implementations on the study of algorithm. Development of technique for parameter tuning; Discussion of a parameter that relates the sizes of the address region and the cell...
详细信息
Reports on the use of coalesced hashing for implementations on the study of algorithm. Development of technique for parameter tuning; Discussion of a parameter that relates the sizes of the address region and the cellar; analysis of related methods and applications to external searching on secondary storage devices.
The macroanalysis of algorithms consists of choosing a dominant operation of an algorithm and expressing execution time as a function of the number of times this operation is used. In contrast, the microanalysis of pr...
详细信息
The macroanalysis of algorithms consists of choosing a dominant operation of an algorithm and expressing execution time as a function of the number of times this operation is used. In contrast, the microanalysis of programs consists of expressing the execution time as a function of the time needed to execute each of the operations in the program. Approaches are described whereby one may, with the help of a computer, perform microanalyses of programs by constructing their time-formulas. Time-formulas are symbolic formulas that express execution times as functions of variables representing the time needed to perform common, elementary operations, e.g., addition, assignment, subscripting, loop overhead. By binding the variables to numeric values corresponding to a specific machine, one can estimate program execution times without resorting to empirical tests. This paper reviews methods of microanalysis and discusses some programs that have been analyzed using the suggested approaches. These include Strassen's matrix multiplication algorithm, deterministic parsers, and a certain class of straight-line programs. The desirable software tools for performing microanalysis are also discussed. [ABSTRACT FROM AUTHOR]
A priority queue is a data structure for maintaining a collection of items, each having an associated key, such that the item with the largest key is easily accessible. Priority queues are implemented by using heap, k...
详细信息
A priority queue is a data structure for maintaining a collection of items, each having an associated key, such that the item with the largest key is easily accessible. Priority queues are implemented by using heap, k-ary tree, single linked-list, leftist tree, linked tree, AVL tree, 2-3 tree and fixed priority property. Required storage for each method was obtained and the worst case time analysis was done in terms of key comparisons and key exchanges during the insertion and deletion process. Finally, each of these methods were run on PDP-11 UNIX TIME SHARING SYSTEM at NPS using different random number generators to get the average CPU time for insertion and deletion process.
Formulas are given for the expected number of nodes in the backtrack tree that is generated while searching for all the solutions of a random predicate. The most general formulas apply to selection from any set of pre...
详细信息
Formulas are given for the expected number of nodes in the backtrack tree that is generated while searching for all the solutions of a random predicate. The most general formulas apply to selection from any set of predicates that obeys the following conditions. Each predicate is the conjunction of t terms selected from a set of terms T. For any subset T′≦
Monotonicity of a polygon is defined. The class of monotone polygons contain the class of convex polygons and is itself contained in the class of simple polygons. Given a simple polygon, the analyst finds an advanta...
详细信息
Monotonicity of a polygon is defined. The class of monotone polygons contain the class of convex polygons and is itself contained in the class of simple polygons. Given a simple polygon, the analyst finds an advantage in being able to say whether the polygon is monotonous. It appears that certain computational problems involving polygons are easier for monotone than for arbitrary simple polygons. An algorithm is developed to yield a solution to the following problem: Given a simple polygon, determine whether the polygon is monotone, and, if so, exhibit a line with respect to which the polygon is monotone. Figures.
In this paper we analyze various search schemes in a major/minor loop bubble memory. Specifically, we study balanced tree search, one-sided height-balanced tree search, and one-sided K-Keight-balanced tree search. Two...
详细信息
In this paper we analyze various search schemes in a major/minor loop bubble memory. Specifically, we study balanced tree search, one-sided height-balanced tree search, and one-sided K-Keight-balanced tree search. Two parameters are of interest in the present framework, namely, the number of comparisons and the amount of record movement required for a search. One-sided height- balanced tree search seems to offer the best compromise. Other related ❉s such as insertion and deletions are also discussed.
Many of the centrally important predicates in theorem-proving programs involve, in their computations, a sub-calculation aimed at determining whether a substitution exists satisfying certain constraints. Some of the ...
详细信息
Many of the centrally important predicates in theorem-proving programs involve, in their computations, a sub-calculation aimed at determining whether a substitution exists satisfying certain constraints. Some of the principal difficulties in achieving efficient theorem-proving programs are traceable to the amount of computation required by this substitution-existence. Stillman mentioned that the amount of computation needed to evaluate the weak predicate-namely, the predicate obtained when one seeks weak substitutions rather than proper substitutions to satisfy the constraints-is significantly less than that required to evaluate the original predicate. That suggestion is incorporated into a formal theorem and demonstrated to be true. Mathematical notation.
Upper and lower bounds are established for the time required to perform certain vector operations in a binary tree machine of the kind introduced by Mago. Two disjoint n-vectors can be matched element by element in O...
详细信息
Upper and lower bounds are established for the time required to perform certain vector operations in a binary tree machine of the kind introduced by Mago. Two disjoint n-vectors can be matched element by element in O(n+h) time, where h is the height of the tree. If the space occupied by the 2 vectors is only linear, then at least linear time is required to bring them together. No matching can be done in less time than the value of the square root of n, and some matchings (such as identity) require at least linear time, regardless of the amount of space used by the vectors.
暂无评论