On the Average Running Time of Odd–Even Merge Sort

This paper gives an upper bound for the average running time of Batcher's odd–even merge sort when implemented on a collection of processors. We consider the case wheren, the size of the input, is an arbitrary multiple of the numberpof processors used. We show that Batcher's odd–even merge (for two sorted lists of lengthneach) can be implemented to run in timeO((n/p)(log(2 + p²/n))) on the average,¹and that odd–even merge sort can be implemented to run in timeO((n/p)(log n + log p log(2 + p²/n))) on the average. In the case of merging (sorting), the average is taken over all possible outcomes of the merge (all possible permutations ofnelements). That means that odd–even merge and odd–even merge sort have an optimal average running time ifn ≥ p². The constants involved are also quite small.     

A deconvolution problem related to a singular system

We present a recursive deconvolution algorithm for a Volterra integral equation which corresponds to a singular differential equation in a Hilbert space. The algorithm is robust with respect to errors in the sampling of the output, and to the sampling times.     

Matrix Representation of Recursive Sequences of Order $3$ and Its Applications

Here presented is a matrix representation of recursive number sequences of order $3$ defined by $a_n=pa_{n-1}+qa_{n-2}+ra_{n-3}$ with arbitrary initial conditions $a_0,$ $a_1=0$, and $a_2$ and their special cases of Padovan number sequence and Perrin number sequence with initial conditions $a_0=a_1=0$ and $a_2=1$ and $a_0=3$, $a_1=0$, and $a_2=2$, respectively. The matrix representation is used to construct many well known and new identities of recursive number sequences as well as Pavodan and Perrin sequences.     

A statistical analysis of an algorithm's complexity

In doing the statistical analysis of bubble sort program, we compute its execution times with various parameters. The statistical analysis endorses the specific quadratic pattern of the execution time on the number of items to be sorted. Next, a cursor along the future direction is indicated.     

Physical Sorting of Coded Documents

A large number of coded items such as bank checks are initially mixed randomly. It is desired to sort them into k categories using a sorting device with m pockets (m < k). Several possible objectives are noted, and a new criterion oriented to the average time until categories are sorted out is analyzed. A simple strategy is shown to minimize the average number of sorting passes that elapse until an item is sorted out.     

The density function of the number of moves to complete the Towers of Hanoi puzzle

Any sequence of legal moves leads the Towers of Hanoi puzzle to an arrangement from which the final configuration must be built up. A recursive algorithm which finishes off the puzzle is considered and, assuming a uniform distribution on the possible unfinished situations, the density function of the number of moves it takes is derived.     

Gray codes for signed involutions

In this paper we present two cyclic Gray codes for signed involutions. The first one has a natural construction, implemented by a CAT algorithm, based in the recursive formula for the number of signed involutions. The second code, although with a higher computational cost, has the smallest possible Hamming distance for this family of objects.     

Computational aspects of robust Holt-Winters smoothing based on M-estimation

To obtain a robust version of exponential and Holt-Winters smoothing the idea of M-estimation can be used. The difficulty is the formulation of an easy-to-use recursive formula for its computation. A first attempt was made by Cipra (Robust exponential smoothing, J. Forecast. 11 (1992), 57–69). The recursive formulation presented there, however, is unstable. In this paper, a new recursive computing scheme is proposed. A simulation study illustrates that the new recursions result in smaller forecast errors on average. The forecast performance is further improved upon by using auxiliary robust starting values and robust scale estimates. This research has been supported by the Research Fund K.U. Leuven and the Fonds voor Wetenschappelijk Onderzoek (Contract number G.0594.05).     

A short remark on Fibonacci-type sequences,Möbius strips and the ψ-function

A base for linear recursive sequences, such as the sequence of Fibonacci numbers, is defined within the framework of the sum of the digits of a number. Examples of bases of a number of such sequences are then outlined, and a Möbius strip is also used to illustrate the effects diagrammatically.     

The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

基于同异反态势排序的学生成绩分析

同异反态势排序是根据同异反联系数 a+bi+cj中 a、b、c大小关系而进行的一种排序。当把学生成绩用同异反联系数表示之后 ,可对照同异反态势排序表来研究其中的某些规律     

A formula for multiple classifiers in data mining based on Brandt semigroups

A general approach to designing multiple classifiers represents them as a combination of several binary classifiers in order to enable correction of classification errors and increase reliability. This method is explained, for example, in Witten and Frank (Data Mining: Practical Machine Learning Tools and Techniques, 2005, Sect. 7.5). The aim of this paper is to investigate representations of this sort based on Brandt semigroups. We give a formula for the maximum number of errors of binary classifiers, which can be corrected by a multiple classifier of this type. Examples show that our formula does not carry over to larger classes of semigroups.     

Characterization of the barrier parameter of homogeneous convex cones

We characterize the smallest (best) barrier parameter of self-concordant barriers for homogeneous convex cones. In particular, we prove that this parameter is the same as the rank of the cone which is the number of steps in a recursive construction of the cone (Siegel domain construction). We also provide lower bounds on the barrier parameter in terms of the Carathéodory number of the cone. The bounds are tight for homogeneous self-dual cones. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by an operating grant from NSERC of Canada.Research supported in part by the National Science Foundation under grant DMS-9306318.     

Merging of Linear Combinations to Semistable Laws

We prove merge theorems along the entire sequence of natural numbers for the distribution functions of suitably centered and normed linear combinations of independent and identically distributed random variables from the domain of geometric partial attraction of any non-normal semistable law. Surprisingly, for some sequences of linear combinations, not too far from those with equal weights, the merge theorems reduce to ordinary asymptotic distributions with semistable limits. The proofs require working out general conditions for merging in terms of characteristic functions.     

On extremal sort sequences

A sort sequence S_n is a sequence of all unordered pairs of indices inI _n = {1, 2, ..., n}. With a sort sequenceS_n = (s₁ ,s₂ ,...,s_{( 2ⁿ )} )S_n = (s_1 ,s_2 ,...,s_{\left( {_2^n } \right)} ), one can associate a predictive sorting algorithm A(S_n). An execution of the algorithm performs pairwise comparisons of elements in the input setX in the order defined by the sort sequence S_n except that the comparisons whose outcomes can be inferred from the results of the preceding comparisons are not performed. A sort sequence is said to be extremal if it maximizes a given objective function. First we consider the extremal sort sequences with respect to the objective function ω(S_n) — the expected number of active predictions inS _n. We study ω-extremal sort sequences in terms of their prediction vectors. Then we consider the objective function Ω(S_n) — the minimum number of active predictions in S_n over all input orderings.     

切换系统的自适应广义预测控制

针对一类切换系统研究了含有输出预测误差的自适应广义预测控制问题．切换律由有限个子系统的输出预测误差确定．对于单个子系统和多个子系统两种情况,证明了所提出的广义预测控制直接算法能够保证系统的全局收敛性．该算法克服了传统自适应控制固有的收敛速度慢且暂态误差较大的缺点．     

“韩信点兵”问题新解

对"韩信点兵"问题的解法进行新解,给出了较孙子定理简便的求同余式组最小正整数解的一种递推公式解法.     

Credibility theory and the Kalman filter

Following Mehra (1975) we indicate how some of the well known credibility models may be formulated as Kalman filters. The formulation yields recursive premium forecasts including recursive predictions errors which are of importance to practitioners.     

关于非强平稳NA列的重对数律及其应用

本文讨论了非强平稳ＮＡ（ＮｅｙａｔｉｖｅｌｙＡｓｓｏｃｉａｔｅｄ）列的若干重对数律,并用以估计线性模型中ＮＡ误差的方差估计的一类强收敛速度．     

Full forward kinematics of redundant kinematic hybrid manipulator

A unified recursive mathematic model is established for full forward kinematics analysis of various redundant kinematic hybrid manipulators which are formed by several different parallel manipulators connected in series. In the established model, the relationships between the general input velocity/acceleration and the general output velocity/acceleration are discovered. The Jacobian matrices for mapping the general output velocities to the general input velocity and the Hessian matrices for mapping the general output velocities to the general input acceleration are derived. The unified iteration recursive formulae are derived for solving the general output velocity/acceleration of the end moving platform of the redundant kinematic hybrid manipulator by only giving the general input velocity/acceleration of every parallel manipulator. A 3D model of a novel (4SPS + SPR )+ (4SPS/SP) + 3SPR type hybrid manipulator is constructed and its full forward velocity/acceleration formulae are derived from the established unified recursive mathematic model and are proved to be correct by utilizing a simulation solution of the novel redundant kinematic hybrid manipulator.