Bit-index sort: A fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.

Efficient algorithms for beacon routing in polygons

In a paper by Biro et al. [7], a novel twist on guarding in art galleries is introduced. A beacon is a fixed point with an attraction pull that can move points within the polygon. Points move greedily to monotonically decrease their Euclidean distance to the beacon by moving straight towards the beacon or sliding on the edges of the polygon. The beacon attracts a point if the point eventually reaches the beacon. Unlike most variations of the art gallery problem, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. We first study the characteristics of beacon attraction. We consider the quality of a "successful" beacon attraction and provide an upper bound of $\sqrt{2}$ on the ratio between the length of the beacon trajectory and the length of the geodesic distance in a simple polygon. In addition, we provide an example of a polygon with holes in which this ratio is unbounded. Next we consider the problem of computing the shortest beacon watchtower in a polygonal terrain and present an $O(n \log n)$ time algorithm to solve this problem. In doing this, we introduce $O(n \log n)$ time algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. We also prove that $\Omega(n \log n)$ time is a lower bound for computing the beacon kernel of a monotone polygon. Finally, we study the inverse attraction region of a point in a simple polygon. We present algorithms to efficiently compute the inverse attraction region of a point for simple, monotone, and terrain polygons with respective time complexities $O(n^2)$, $O(n \log n)$ and $O(n)$. We show that the inverse attraction region of a point in a simple polygon has linear complexity and the problem of computing the inverse attraction region has a lower bound of $\Omega(n \log n)$ in monotone polygons and consequently in simple polygons.

Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity

We present quasi-Monte Carlo analogs of Monte Carlo methods for some linear algebra problems: solving systems of linear equations, computing extreme eigenvalues, and matrix inversion. Reformulating the problems as solving integral equations with a special kernels and domains permits us to analyze the quasi-Monte Carlo methods with bounds from numerical integration. Standard Monte Carlo methods for integration provide a convergence rate of O(N^(−1/2)) using N samples. Quasi-Monte Carlo methods use quasirandom sequences with the resulting convergence rate for numerical integration as good as O((logN)^k)N^(−1)). We have shown theoretically and through numerical tests that the use of quasirandom sequences improves both the magnitude of the error and the convergence rate of the considered Monte Carlo methods. We also analyze the complexity of considered quasi-Monte Carlo algorithms and compare them to the complexity of the analogous Monte Carlo and deterministic algorithms.

Influence of third-generation oral contraceptives on the complexity analysis and symbolic dynamics of heart rate variability

Objective To evaluate the influence of oral contraceptives (OCs) containing 20 mu mu g ethinylestradiol (EE) and 150 mu mu g gestodene (GEST) on the autonomic modulation of heart rate (HR) in women. Methods One-hundred and fifty-five women aged 24 +/-+/- 2 years were divided into four groups according to their physical activity and the use or not of an OC: active-OC, active-non-OC (NOC), sedentary-OC, and sedentary-NOC. The heart rate was registered in real time based on the electrocardiogram signal for 15 minutes, in the supine-position. The heart rate variability (HRV) was analysed using Shannon`s entropy (SE), conditional entropy (complexity index [CInd] and normalised CInd [NCI]), and symbolic analysis (0V%, 1V%, 2LV%, and 2ULV%). For statistical analysis the Kruskal-Wallis test with Dunn post hoc and the Wilcoxon test (p < 0.05 was considered significant) were applied. Results Treatment with this COC caused no significant changes in SE, CInd, NCI, or symbolic analysis in either active or sedentary groups. Active groups presented higher values for SE and 2ULV%, and lower values for 0V% when compared to sedentary groups (p < 0.05). Conclusion HRV patterns differed depending on life style; the non-linear method applied was highly reliable for identifying these changes. The use of OCs containing 20 mu mu g EE and 150 mu mu g GEST does not influence HR autonomic modulation.

Local complexity of Delone sets and crystallinity

This paper characterizes when a Delone set X in R-n is an ideal crystal in terms of restrictions on the number of its local patches of a given size or on the heterogeneity of their distribution. For a Delone set X, let N-X (T) count the number of translation-inequivalent patches of radius T in X and let M-X (T) be the minimum radius such that every closed ball of radius M-X(T) contains the center of a patch of every one of these kinds. We show that for each of these functions there is a gap in the spectrum of possible growth rates between being bounded and having linear growth, and that having sufficiently slow linear growth is equivalent to X being an ideal crystal. Explicitly, for N-X (T), if R is the covering radius of X then either N-X (T) is bounded or N-X (T) greater than or equal to T/2R for all T > 0. The constant 1/2R in this bound is best possible in all dimensions. For M-X(T), either M-X(T) is bounded or M-X(T) greater than or equal to T/3 for all T > 0. Examples show that the constant 1/3 in this bound cannot be replaced by any number exceeding 1/2. We also show that every aperiodic Delone set X has M-X(T) greater than or equal to c(n)T for all T > 0, for a certain constant c(n) which depends on the dimension n of X and is > 1/3 when n > 1.

Independent contribution of plaque complexity to myocardial ischemia during Dobutamine stress echocardiography

The influence of complex plaque morphology on the extent of demand-induced ischemia in unselected patients is not well defined. We sought to investigate the functional significance of lesion morphology in patients who underwent coronary angiography and dobutamine stress echocardiography (DSE).,Angiography and DSE were performed within a 6-month period (mean 1 +/- 1 month) in 196 patients. Angiographic assessments involved quantification of stenosis severity, assessment of the extent of jeopardized myocardium, and categorization of plaque morphology according to the Ambrose classification. DSE was interpreted by separate investigators with respect to wall motion score index (WMSI) and number of coronary territories involved. A general linear model was constructed to assess,the independent contribution of patient characteristics and angiographic and DSE results with respect to extent of ischemic myocardium. Complex lesion morphology was seen in 62 patients (32%). Patients with complex lesions were more likely to have had prior myocardial infarction (p < 0.001) and be current smokers (p = 0.03). During angiography, they exhibited a trend toward a greater number of diseased vessels, had a greater coronary jeopardy score (p < 0.001) and more frequent collateral flow (p = 0.03). During echocardiography, patients had a higher stress WMSI (p < 0.001) and were more likely to show ischemia in all 3 arterial territories (p < 0.01). On multivariate regression, the coronary artery jeopardy score and the presence of complex plaque morphology were independent predictors of the extent of ischemic myocardium (R 2 = 34%, p < 0.001). Thus, patients with complex plaque morphology are older, more likely to smoke, and more likely to have had prior myocardial. infarction. They exhibit more extensive disease with higher coronary jeopardy scores and a higher resting and peak stress WMSI. Despite these differences, complex plaque morphology remains an independent predictor of the extent of ischemia during stress. (C) 2003 by Excerpta Medica, Inc.

Numerical solution of a PDE system with non-linear steady state conditions that translates the air stripping pollutants removal

This work deals with the numerical simulation of air stripping process for the pre-treatment of groundwater used in human consumption. The model established in steady state presents an exponential solution that is used, together with the Tau Method, to get a spectral approach of the solution of the system of partial differential equations associated to the model in transient state.

Linear amplification with multiple nonlinear devices

Dissertação para obtenção do Grau de Mestre em Engenharia Electrotécnica e Computadores

What do we gain from simplicity versus complexity in species distribution models?

Species distribution models (SDMs) are widely used to explain and predict species ranges and environmental niches. They are most commonly constructed by inferring species' occurrence-environment relationships using statistical and machine-learning methods. The variety of methods that can be used to construct SDMs (e.g. generalized linear/additive models, tree-based models, maximum entropy, etc.), and the variety of ways that such models can be implemented, permits substantial flexibility in SDM complexity. Building models with an appropriate amount of complexity for the study objectives is critical for robust inference. We characterize complexity as the shape of the inferred occurrence-environment relationships and the number of parameters used to describe them, and search for insights into whether additional complexity is informative or superfluous. By building 'under fit' models, having insufficient flexibility to describe observed occurrence-environment relationships, we risk misunderstanding the factors shaping species distributions. By building 'over fit' models, with excessive flexibility, we risk inadvertently ascribing pattern to noise or building opaque models. However, model selection can be challenging, especially when comparing models constructed under different modeling approaches. Here we argue for a more pragmatic approach: researchers should constrain the complexity of their models based on study objective, attributes of the data, and an understanding of how these interact with the underlying biological processes. We discuss guidelines for balancing under fitting with over fitting and consequently how complexity affects decisions made during model building. Although some generalities are possible, our discussion reflects differences in opinions that favor simpler versus more complex models. We conclude that combining insights from both simple and complex SDM building approaches best advances our knowledge of current and future species ranges.

On codes, matroids, and secure multiparty computation from linear secret-sharing schemes

Error-correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, the connections between codes, matroids, and a special class of secret sharing schemes, namely, multiplicative linear secret sharing schemes (LSSSs), are studied. Such schemes are known to enable multiparty computation protocols secure against general (nonthreshold) adversaries.Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. A property of strongly multiplicative LSSSs that could be useful in solving this problem is proved. Namely, using a suitable generalization of the well-known Berlekamp–Welch decoder, it is shown that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, the considered open problem is to determine whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be restated in terms of representability of identically self-dual matroids by self-dual codes. A new concept is introduced, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. It is proved that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.

What kind of relationships between the evolution of pain, beliefs and bio-psycho-social complexity after a locomotor traumatism?

Introduction: Pain and beliefs have an influence on the patient's course in rehabilitation, pain causes fears and fears influence pain perception. The aim of this study is to understand pain and beliefs evolutions during rehabilitation taking into account of bio-psycho-social complexity.Patients and methods: 631 consecutive patients admitted in rehabilitation after a musculoskeletal traumatism were included and assessed at admission and at discharge. Pain was measured by VAS (Visual Analogical Scale), bio-psycho-social complexity by Intermed scale, and beliefs by judgement on Lickert scales. Four kinds of beliefs were evaluated: fear of a severe origin of pain, fear of movement, fear of pain and feeling of distress (loss of control). The association between the changes in pain and beliefs during the hospitalization was assessed by linear regressions.Results: After adjustment for gender, age, education and native language, patients with a decrease in pain during rehabilitation have higher probability of decreasing their fears. For the distress feeling, this relationship is weaker among bio-psycho-socially complex patients (odds-ratio 1.22 for each decreasing of 10mm/100 VAS) than among non-complex patients (OR 1.47). Patients with a pain decrease of 30% or more during hospitalization have higher probability of seeing their fears decrease, this relationship being stronger in complex patient for fear of a severe origin of pain.Discussion: The relationships between evolution of pain and beliefs move in the same direction. The higher a patient feels pain, the less they could be able to modify their dysfunctional beliefs. When the pain diminishes of 30% or more, the probability to challenge the beliefs is increased. The prognostic with regard to feeling of distress and fear of a severe origin of pain, is worse among bio-psycho-socially complex patients.

To select or to weigh: a comparative study of linear combination schemes for superparent-one-dependence estimators

We conduct a large-scale comparative study on linearly combining superparent-one-dependence estimators (SPODEs), a popular family of seminaive Bayesian classifiers. Altogether, 16 model selection and weighing schemes, 58 benchmark data sets, and various statistical tests are employed. This paper's main contributions are threefold. First, it formally presents each scheme's definition, rationale, and time complexity and hence can serve as a comprehensive reference for researchers interested in ensemble learning. Second, it offers bias-variance analysis for each scheme's classification error performance. Third, it identifies effective schemes that meet various needs in practice. This leads to accurate and fast classification algorithms which have an immediate and significant impact on real-world applications. Another important feature of our study is using a variety of statistical tests to evaluate multiple learning methods across multiple data sets.

Resting-State Functional Connectivity Emerges from Structurally and Dynamically Shaped Slow Linear Fluctuations.

Brain fluctuations at rest are not random but are structured in spatial patterns of correlated activity across different brain areas. The question of how resting-state functional connectivity (FC) emerges from the brain's anatomical connections has motivated several experimental and computational studies to understand structure-function relationships. However, the mechanistic origin of resting state is obscured by large-scale models' complexity, and a close structure-function relation is still an open problem. Thus, a realistic but simple enough description of relevant brain dynamics is needed. Here, we derived a dynamic mean field model that consistently summarizes the realistic dynamics of a detailed spiking and conductance-based synaptic large-scale network, in which connectivity is constrained by diffusion imaging data from human subjects. The dynamic mean field approximates the ensemble dynamics, whose temporal evolution is dominated by the longest time scale of the system. With this reduction, we demonstrated that FC emerges as structured linear fluctuations around a stable low firing activity state close to destabilization. Moreover, the model can be further and crucially simplified into a set of motion equations for statistical moments, providing a direct analytical link between anatomical structure, neural network dynamics, and FC. Our study suggests that FC arises from noise propagation and dynamical slowing down of fluctuations in an anatomically constrained dynamical system. Altogether, the reduction from spiking models to statistical moments presented here provides a new framework to explicitly understand the building up of FC through neuronal dynamics underpinned by anatomical connections and to drive hypotheses in task-evoked studies and for clinical applications.

Dynamic patterns of flow in the workplace: characterizing within-individual variability using a complexity science approach

As a result of the growing interest in studying employee well-being as a complex process that portrays high levels of within-individual variability and evolves over time, this present study considers the experience of flow in the workplace from a nonlinear dynamical systems approach. Our goal is to offer new ways to move the study of employee well-being beyond linear approaches. With nonlinear dynamical systems theory as the backdrop, we conducted a longitudinal study using the experience sampling method and qualitative semi-structured interviews for data collection; 6981 registers of data were collected from a sample of 60 employees. The obtained time series were analyzed using various techniques derived from the nonlinear dynamical systems theory (i.e., recurrence analysis and surrogate data) and multiple correspondence analyses. The results revealed the following: 1) flow in the workplace presents a high degree of within-individual variability; this variability is characterized as chaotic for most of the cases (75%); 2) high levels of flow are associated with chaos; and 3) different dimensions of the flow experience (e.g., merging of action and awareness) as well as individual (e.g., age) and job characteristics (e.g., job tenure) are associated with the emergence of different dynamic patterns (chaotic, linear and random).