6028662
The Least Witness of a Composite Number
We consider the problem of finding the least witness of a composite number. If n is a composite number then a number w for which n is not a strong pseudo-prime to the base w is called a witness for n. Let w(n) be the least witness for a composite n. Bach [7] assuming the Generalized Riemann Hypothesis (GRH) showed that w(n) < 2log2 n. In this paper we are interested in obtaining upper bounds for w(n) without assuming the GRH.
27625864
Path Balance Heuristic for Self-Adjusting Binary Search Trees
In (A. Subramanian, An Explanation of Splaying, Proceedings of the 14th Foundations of Software Technology and Theoretical Computer Science, LNCS Springer Verlag 880 354–365), D. Sleator suggested the following heuristic for self adjusting binary search trees: Every time an access is made, restructure the entire path from the root of the search tree to the accessed node into a balanced binary search tree on those nodes, and place all other subtrees rooted at the children of the nodes in the access path in their proper positions. We show that the method has an O(log n log log n/ log log log n) amortized complexity.
5346923
Finding Scores in Tournaments
A tournamentTnis an orientation of the complete graph onnvertices. We continue the algorithmic study initiated by10of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree) in the same model. We show that the complexity of finding a vertex of outdegreek(?(n?1)/2) inTnis ?(nk). This bound is in sharp contrast to the ?(n) bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directed/undirected graphs. These bounds generalize the classical bound of11for finding a sink (a vertex of outdegree 0 and indegreen?1) in a directed graph.
119712961
On ideal-function-like functions
The aim of this paper is to extend the considerations of the first and the third authors and others to the setting of Suetuna, i.e. we consider some important sums of multiplicative ideal-functions in relative extensions of number fields. This contains most of the earlier work on those sums related to the divisor and the circle problems.
30972999
Perfect Power Testing
Bach and Sorenson present two algorithms for testing whether a number n is a perfect power, with average running time O(log2 n) under the assumption that n is chosen uniformly from an interval of length at least (log n)3 log log log n. We modify their algorithms to reduce the interval to polynomial size.
8028128
Maximal Sets of Integers with Distinct Divisors
A set of positive integers is said to have the distinct divisor property if there is an injective map that sends every integer in the set to one of its proper divisors. In 1983, P. Erdős and C. Pomerance showed that for every $c>1$, a largest subset of $[N,cN]$ with the distinct divisor property has cardinality $\sim \delta(c)N$, for some constant $\delta(c)>0$. They conjectured that $\delta(c)\sim c/2$ as $c \to \infty$. We prove their conjecture. In fact we show that there exist positive absolute constants $D_1,D_2$ such that $D_1\le c^{\beta}(c/2-\delta(c))\le D_2$ where $\beta = \log 2/\log (3/2)$.
28520158
Blended Learning - A Trend in e-Learning
A method, apparatus, and article of manufacture for a computer-implemented random reliability engine for computer-implemented dimension reduction using association rules for data mining application. The data mining is performed by the computer to retrieve data from a data store stored on a data storage device coupled to the computer. The data store has records that have multiple attributes. The multiple attributes of a table are clustered to produce a plurality of sets of attributes. Each set of attributes is clustered to obtain data mining attributes.
13457273
A new Contrast Based Image Fusion using Wavelet Packets
Image Fusion, a technique which combines complimentary information from different images of the same scene so that the fused image is more suitable for segmentation, feature extraction, object recognition and Human Visual System. In this paper, a simple yet efficient algorithm is presented based on contrast using wavelet packet decomposition. First, all the source images are decomposed into low and high frequency sub-bands and then fusion of high frequency sub-bands is done by the means of Directive Contrast. Now, inverse wavelet packet transform is performed to reconstruct the fused image. The performance of the algorithm is carried out by the comparison made between proposed and existing algorithm.