Improving the average delay of sorting

In previous work we have introduced an average case measure for the time complexity of Boolean circuits. Instead of fixed circuit depth, for each input we take the minimal number of time steps necessary to perform the computation for that particular input using gates that forward their output values as soon as possible. This measure is called delay. Based on it, the complexity of a whole class of functions that can be described as prefix computations has been analysed in detail.     

On the average number of rebalancing operations in weight-balanced trees

It is shown that the average number of rebalancing operations (rotations and double rotations) in weight-balanced trees is constant.     

Algorithms and average time bounds of sorting on a mesh-connectedcomputer

We give three new parallel sorting algorithms on a mesh-connected computer with wraparound connections (i.e. a torus). These three algorithms, with the minimum queue size of 1, sort n² random input data items into a blocked snakelike row major order, a row major order, and a snakelike row major order, in 1.5n+o(n), 2n+o(n), and 2n+o(n) average steps, respectively. These results improve the previous results of 2n+o(n), 2.5n+o(n), and 2.5n+o(n), respectively. In addition, we prove that the distance bound n on a torus is an average-time lower bound independent of indexing schemes of sorting random input data items on it     

On sorting and counting

When performing an external sort, an extra integer field added to the sort key can be used to count subsequences, and make the counts available at the beginning of each subsequence.     

Optimum tradeoff between class-selective rejection error and average number of classes

The paper first reviews the recently proposed optimum class-selective rejection rule. This rule provides an optimum tradeoff between the error rate and the average number of (selected) classes. Then, a new general relation between the error rate and the average number of classes is presented. The error rate can be directly computed from the class-selective reject function, which in turn can be estimated from unlabelled patterns, by simply counting the rejected classes. Theoretical as well as practical implications are discussed, and some future research directions are proposed.     

A note on the average number of RSA fixed points

Recently, Chmielowiec (2010) [3] studied an upper bound for the average number of fixed points in RSA encryption and asserted that it is on the order of (logn)² for randomly chosen RSA parameters (n,e). In this paper, we point out some error in his estimation and present detailed procedures for correct evaluation. It is shown that the expected number of RSA fixed points is in fact O((logn)³).     

Optimal information dissemination in star and pancake networks

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N=n! processors, our algorithms take less than [log N]+1.5n steps     

On sorting triangles in a delaunay tessellation

In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.This work was partially supported by the National Science Foundation's US-Italy Collaborative Research Program under Grant INT-8714578 and Information, Robotics, and Intelligent Research Grant IRI-8704781.     

On sorting triangles in a delaunay tessellation

In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.     

The average number of registers needed to evaluate a binary tree optimally

Summary In this paper we determine the number of binary trees with n leaves which can be evaluated optimally with less than or equal to k registers. Furthermore we obtain the result that this number is equal to the number of the binary trees with n leaves, using for traversal a maximum size of stack less than or equal to 2^k+1–1. This fact is only a connection between the numbers of the trees and not between the sets of the trees. We compute also the average number ¯R(n) of registers needed to evaluate a binary tree optimally. We get for all >0: where C = 0.82574... is a constant and F(n) is a function with F(n) = F(4n) for all n>0 and –0.574相似文献   

On Quickselect, partial sorting and Multiple Quickselect

We present explicit solutions of a class of recurrences related to the Quickselect algorithm. Thus we are immediately able to solve recurrences arising at the partial sorting problem, which are contained in this class. Furthermore we show how the partial sorting problem is connected to the Multiple Quickselect algorithm and present a method for the calculation of solutions for a class of recurrences related to the Multiple Quickselect algorithm. Further an analysis of an algorithm for sorting a subarray A[r…r+p−1], given the array A[1…n], is provided.     

On the average depth of asymmetric LC-tries

Andersson and Nilsson have already shown that the average depth Dn of random LC-tries is only Θ(log^∗n) when the keys are produced by a symmetric memoryless process, and that Dn=O(loglogn) when the process is asymmetric. In this paper we refine the second estimate by showing that asymptotically (with n→∞): , where n is the number of keys inserted in a trie, η=−log(1−h/h−∞), h=−plogp−qlogq is the entropy of a binary memoryless source with probabilities p, q=1−p (p≠q), and h−∞=−logmin(p,q).     

A comparative study of job allocation and migration in the pancake network

Pancake networks are an attractive class of Cayley graphs functioning as a viable interconnection scheme for large multi-processor systems. The hierarchy of the pancake graph allows the assignment of its special subgraphs, which have the same topological features as the original graph, to a sequence of incoming jobs. We investigate the hierarchical structure of the pancake network and derive a job allocation scheme for assigning processors to incoming jobs. An algorithm is presented for job migration. Finally, we compare the assignment scheme to those derived previously for the star network and address the shortcomings of the pancake network.     

On the estimation of two-dimensional moving average parameters

The authors address the estimation problem of moving average (MA) parameters of a 2D autoregressive moving average (ARMA) model. The problem is equivalent to solving a set of overdetermined 2D transcendental equations. Based on some extensions of the Newton-Raphson method, an iterative algorithm is proposed for estimating 2D MA parameters. The performance of the algorithm is demonstrated by a numerical example. For 2D sinusoids in white noise spatial series, some interesting features of 2D ARMA modeling are observed