Rainbow Sort: Sorting at the Speed of Light

Rainbow Sort is an unconventional method for sorting, which is based on the physical concepts of refraction and dispersion. It is inspired by the observation that light that traverses a prism is sorted by wavelength. At first sight this “rainbow effect” that appears in nature has nothing to do with a computation in the classical sense, still it can be used to design a sorting method that has the potential of running in Θ (n) with a space complexity of Θ (n), where n denotes the number of elements that are sorted. In Section 1, some upper and lower bounds for sorting are presented in order to provide a basis for comparisons. In Section 2, the physical background is outlined, the setup and the algorithm are presented and a lower bound for Rainbow Sort of Ω (n) is derived. In Section 3, we describe essential difficulties that arise when Rainbow Sort is implemented. Particularly, restrictions that apply due to the Heisenberg uncertainty principle have to be considered. Furthermore, we sketch a possible implementation that leads to a running time of O(n+m), where m is the maximum key value, i.e., we assume that there are integer keys between 0 and m. Section 4 concludes with a summary of the complexity and some remarks on open questions, particularly on the treatment of duplicates and the preservation of references from the keys to records that contain the actual data. In Appendix A, a simulator is introduced that can be used to visualise Rainbow Sort.     

Slabpose Columnsort: A New Oblivious Algorithm for Out-of-Core Sorting on Distributed-Memory Clusters

Our goal is to develop a robust out-of-core sorting program for a distributed-memory cluster. The literature contains two dominant paradigms for out-of-core sorting algorithms: merging-based and partitioning-based. We explore a third paradigm, that of oblivious algorithms. Unlike the two dominant paradigms, oblivious algorithms do not depend on the input keys and therefore lead to predetermined I/O and communication patterns in an out-of-core setting. Predetermined I/O and communication patterns facilitate overlapping I/O, communication, and computation for efficient implementation. We have developed several out-of-core sorting programs using the paradigm of oblivious algorithms. Our baseline implementation, 3-pass columnsort, was based on Leighton's columnsort algorithm. Though efficient in terms of I/O and communication, 3-pass columnsort has a restriction on the maximum problem size. As our first effort toward relaxing this restriction, we developed two implementations: subblock columnsort and M-columnsort. Both of these implementations incur substantial performance costs: subblock columnsort performs additional disk I/O, and M-columnsort needs substantial amounts of extra communication and computation. In this paper we present slabpose columnsort, a new oblivious algorithm that we have designed explicitly for the out-of-core setting. Slabpose columnsort relaxes the problem-size restriction at no extra I/O or communication cost. Experimental evidence on a Beowulf cluster shows that unlike subblock columnsort and M-columnsort, slabpose columnsort runs almost as fast as 3-pass columnsort. To the best of our knowledge, our implementations are the first out-of-core multiprocessor sorting algorithms that make no assumptions about the keys and produce output that is perfectly load balanced and in the striped order assumed by the Parallel Disk Model.     

Unconditionally Secure Oblivious Polynomial Evaluation: A Survey and New Results

Oblivious polynomial evaluation (OPE) is a two-party protocol that allows a receiver, R to learn an evaluation f(α), of a sender, S's polynomial f(x), whilst keeping both α and f(x) private. This protocol has attracted a lot of attention recently, as it has wide ranging applications in the field of cryptography. In this article we review some of these applications and, additionally, take an in-depth look at the special case of information theoretic OPE. Specifically, we provide a current and critical review of the existing information theoretic OPE protocols in the literature. We divide these protocols into two distinct cases (three-party and distributed OPE) allowing for the easy distinction and classification of future information theoretic OPE protocols. In addition to this work, we also develop several modifications and extensions to existing schemes, resulting in increased security, flexibility and efficiency. Lastly, we also identify a security flaw in a previously published OPE scheme.     

Discovering Dependencies via Algorithmic Mutual Information: A Case Study in DNA Sequence Comparisons

Algorithmic mutual information is a central concept in algorithmic information theory and may be measured as the difference between independent and joint minimal encoding lengths of objects; it is also a central concept in Chaitin's fascinating mathematical definition of life. We explore applicability of algorithmic mutual information as a tool for discovering dependencies in biology. In order to determine significance of discovered dependencies, we extend the newly proposed algorithmic significance method. The main theorem of the extended method states thatd bits of algorithmic mutual information imply dependency at the significance level 2^–d+O(1). We apply a heuristic version of the method to one of the main problems in DNA and protein sequence comparisons: the problem of deciding whether observed similarity between sequences should be explained by their relatedness or by the mere presence of some shared internal structure, e.g., shared internal repetitive patterns. We take advantage of the fact that mutual information factors out sequence similarity that is due to shared internal structure and thus enables discovery of truly related sequences. In addition to providing a general framework for sequence comparisons, we also propose an efficient way to compare sequences based on their subword composition that does not require any a priori assumptions about k-tuple length.     

Sorting Stably,in Place,with O(n log n) Comparisons and O(n) Moves

We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e., preserving the original relative order of the equal elements), using O(1) auxiliary space and performing O(n log n) comparisons and O(n) data moves. Munro and Raman stated this problem in J. Algorithms (13, 1992) and gave an in-place but unstable sorting algorithm that performs O(n) data moves and O(n^1+ε) comparisons. Subsequently (Algorithmica, 16, 1996) they presented a stable algorithm with these same bounds. Recently, Franceschini and Geffert (FOCS 2003) presented an unstable sorting algorithm that matches the asymptotic lower bounds on all computational resources.     

Improving Random Number Generators in the Monte Carlo simulations via twisting and combining

Problems for various random number generators accompanying the Wolff algorithm [U. Wolff, Phys. Rev. Lett. 62 (1989) 361; U. Wolff, Phys. Lett. B 228 (1989) 379] are discussed, including the hidden errors first reported in [A.M. Ferrenberg, D.P. Landau, Y.J. Wong, Phys. Rev. Lett. 69 (1992) 3382]. A general (though simple) method of twisting and combining for improving the performance of these generators is proposed. Some recent generators motivated by such a twisting and combining method with extremely long period are discussed. The proposed method provides a novel and simple way to improve RNGs in its performance.     

Aircraft taxi time prediction: Comparisons and insights

The predicted growth in air transportation and the ambitious goal of the European Commission to have on-time performance of flights within 1 min makes efficient and predictable ground operations at airports indispensable. Accurately predicting taxi times of arrivals and departures serves as an important key task for runway sequencing, gate assignment and ground movement itself. This research tests different statistical regression approaches and also various regression methods which fall into the realm of soft computing to more accurately predict taxi times. Historic data from two major European airports is utilised for cross-validation. Detailed comparisons show that a TSK fuzzy rule-based system outperformed the other approaches in terms of prediction accuracy. Insights from this approach are then presented, focusing on the analysis of taxi-in times, which is rarely discussed in literature. The aim of this research is to unleash the power of soft computing methods, in particular fuzzy rule-based systems, for taxi time prediction problems. Moreover, we aim to show that, although these methods have only been recently applied to airport problems, they present promising and potential features for such problems.     

Proof Pearl: The KeY to Correct and Stable Sorting

We discuss a proof of the correctness of two sorting algorithms: Counting sort and Radix sort. The semi-automated proof is formalized in the state-of-the-art theorem prover KeY.     

Random Constraint Satisfaction: Flaws and Structure

A recent theoretical result by Achlioptas et al. shows that many models of random binary constraint satisfaction problems become trivially insoluble as problem size increases. This insolubility is partly due to the presence of flawed variables, variables whose values are all flawed (or unsupported). In this paper, we analyse how seriously existing work has been affected. We survey the literature to identify experimental studies that use models and parameters that may have been affected by flaws. We then estimate theoretically and measure experimentally the size at which flawed variables can be expected to occur. To eliminate flawed values and variables in the models currently used, we introduce a flawless generator which puts a limited amount of structure into the conflict matrix. We prove that such flawless problems are not trivially insoluble for constraint tightnesses up to 1/2. We also prove that the standard models B and C do not suffer from flaws when the constraint tightness is less than the reciprocal of domain size. We consider introducing types of structure into the constraint graph which are rare in random graphs and present experimental results with such structured graphs.     

Evolutionary Algorithms for Multi-Objective Optimization: Performance Assessments and Comparisons

Evolutionary techniques for multi-objective(MO) optimization are currently gainingsignificant attention from researchers invarious fields due to their effectiveness androbustness in searching for a set of trade-offsolutions. Unlike conventional methods thataggregate multiple attributes to form acomposite scalar objective function,evolutionary algorithms with modifiedreproduction schemes for MO optimization arecapable of treating each objective componentseparately and lead the search in discoveringthe global Pareto-optimal front. The rapidadvances of multi-objective evolutionaryalgorithms, however, poses the difficulty ofkeeping track of the developments in this fieldas well as selecting an existing approach thatbest suits the optimization problem in-hand.This paper thus provides a survey on variousevolutionary methods for MO optimization. Manywell-known multi-objective evolutionaryalgorithms have been experimented with andcompared extensively on four benchmark problemswith different MO optimization difficulties.Besides considering the usual performancemeasures in MO optimization, e.g., the spreadacross the Pareto-optimal front and the abilityto attain the global trade-offs, the paper alsopresents a few metrics to examinethe strength and weakness of each evolutionaryapproach both quantitatively and qualitatively.Simulation results for the comparisons areanalyzed, summarized and commented.     

Profiles of Random Trees: Limit Theorems for Random Recursive Trees and Binary Search Trees

We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio α of the level and the logarithm of tree size lies in [0,e). Convergence of all moments is shown to hold only for α ∈ [0,1] (with only convergence of finite moments when α ∈ (1,e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for α = 0 and a "quicksort type" limit law for α = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees; we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.     

Random differential operational calculus: Theory and applications

In this article, we obtain a product rule and a chain rule for mean square derivatives. An application of the chain rule to the mean square solution of random differential equations is shown. However, to achieve such mean square differentiation rules, fourth order properties were needed and, therefore, we first studied a mean fourth order differential and integral calculus. Results are applied to solve random linear variable coefficient differential problems.     

Large-scale vehicle routing problems: Quantum Annealing,tunings and results

Quantum Annealing was previously applied to the vehicle routing problem and the results were promising. For all benchmark instances in the study, optimal results were obtained. However, 100% success rate was not achieved in every case, and tuning the control parameters for larger instances proved cumbersome. This work addresses these remaining difficulties. An empirical approach is taken wherein measurements of run-time behaviour are exploited to transform existing good values of control parameters so that they can be used successfully for other problem instances. The course of this work shows a method which simplifies hand-tuning so that the heuristic performs successfully when applied to larger instances, and also demonstrates a tuning method which establishes control parameter values for instances which belong in broadly defined groupings. In addition, new best known solutions for large-scale instances, and initial results for the distance-constrained variant of the vehicle routing problem are presented.     

Spectral Element Methods on Unstructured Meshes: Comparisons and Recent Advances

Spectral element approximations for triangles are not yet as mature as for quadrilaterals. Here we compare different algorithms and show that using an integration rule based on Gauss-points for simplices is of interest. We point out that this can be handled efficiently and allows to recover the convergence rate theoretically expected, even with curved elements.     

Microsystems Minimal Storage Sorting and Searching Techniques for RAM Applications: a Tutorial

A large number of sorting and searching techniques, covering a variety of applications, are dealt with in computer science literature. The classical problem associated with these methods has been determining which set of algorithms is most appropriate for a given application. With the recent advances in LSI technology and the assured proliferation of microprocessors and RAM memory, yet another application has evolved. Memory address widths associated with microprocessor systems are limited, in many cases, to a maximum of 16 bits, severely restricting maximum memory size. Minimal storage implementation techniques, characterized by the optimal use of the data space associated with an algorithm, therefore, are most appropriate for these restricted address space environments common to microprocessor systems.