The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

An approximate mathematical model for solidification of a flowing liquid in a microchannel

A mathematical model is developed to analyse the combined flow and solidification of a liquid in a small pipe or two-dimensional channel. In either case the problem reduces to solving a single equation for the position of the solidification front. Results show that for a large range of flow rates the closure time is approximately constant, and the value depends primarily on the wall temperature and channel width. However, the ice shape at closure will be very different for low and high fluxes. As the flow rate increases the closure time starts to depend on the flow rate until the closure time increases dramatically, subsequently the pipe will never close.

An approximate solution method for boundary layer flow of a power law fluid over a flat plate

The work in this paper deals with the development of momentum and thermal boundary layers when a power law fluid flows over a flat plate. At the plate we impose either constant temperature, constant flux or a Newton cooling condition. The problem is analysed using similarity solutions, integral momentum and energy equations and an approximation technique which is a form of the Heat Balance Integral Method. The fluid properties are assumed to be independent of temperature, hence the momentum equation uncouples from the thermal problem. We first derive the similarity equations for the velocity and present exact solutions for the case where the power law index n = 2. The similarity solutions are used to validate the new approximation method. This new technique is then applied to the thermal boundary layer, where a similarity solution can only be obtained for the case n = 1.

Influence of altitude, latitude and season of collection (Bergmann's Rule) on the dimensions of Lutzomyia intermedia (Lutz & Neiva, 1912) (diptera, psychodidae, phlebotominae)

The influence of altitude and latitude on some structure sizes of Lutzomyia intermedia was noted; several structures of insects collected in higher localities were greater, according to Bergmann's rule. This influence was more remarkable in two localities of the State of Espírito Santo, probably due to greater differences in altitude. Comparing insects from different latitudes, more differences were noted in comparisons of insects from low altitude localities than in those of material from higher altitudes. The small number of differences between insects collected in July and in December does not indicate a defined influence of season and temperature on the size of adults. The possible epidemiological implications of these variations are discussed.

A prediction rule to identify low-risk patients with pulmonary embolism.

BACKGROUND: A simple prognostic model could help identify patients with pulmonary embolism who are at low risk of death and are candidates for outpatient treatment. METHODS: We randomly allocated 15,531 retrospectively identified inpatients who had a discharge diagnosis of pulmonary embolism from 186 Pennsylvania hospitals to derivation (67%) and internal validation (33%) samples. We derived our rule to predict 30-day mortality using classification tree analysis and patient data routinely available at initial examination as potential predictor variables. We used data from a European prospective study to externally validate the rule among 221 inpatients with pulmonary embolism. We determined mortality and nonfatal adverse medical outcomes across derivation and validation samples. RESULTS: Our final model consisted of 10 patient factors (age > or = 70 years; history of cancer, heart failure, chronic lung disease, chronic renal disease, and cerebrovascular disease; and clinical variables of pulse rate > or = 110 beats/min, systolic blood pressure < 100 mm Hg, altered mental status, and arterial oxygen saturation < 90%). Patients with none of these factors were defined as low risk. The 30-day mortality rates for low-risk patients were 0.6%, 1.5%, and 0% in the derivation, internal validation, and external validation samples, respectively. The rates of nonfatal adverse medical outcomes were less than 1% among low-risk patients across all study samples. CONCLUSIONS: This simple prediction rule accurately identifies patients with pulmonary embolism who are at low risk of short-term mortality and other adverse medical outcomes. Prospective validation of this rule is important before its implementation as a decision aid for outpatient treatment.

Space-time relatedness and Hamilton's rule for long-lasting behaviors in viscous populations.

Genes affect not only the behavior and fitness of their carriers but also that of other individuals. According to Hamilton's rule, whether a mutant gene will spread in the gene pool depends on the effects of its carrier on the fitness of all individuals in the population, each weighted by its relatedness to the carrier. However, social behaviors may affect not only recipients living in the generation of the actor but also individuals living in subsequent generations. In this note, I evaluate space-time relatedness coefficients for localized dispersal. These relatedness coefficients weight the selection pressures on long-lasting behaviors, which stem from a multigenerational gap between phenotypic expression by actors and the resulting environmental feedback on the fitness of recipients. Explicit values of space-time relatedness coefficients reveal that they can be surprisingly large for typical dispersal rates, even for hundreds of generations in the future.

Selected configuration interaction with truncation energy error and application to the Ne atom

Selected configuration interaction (SCI) for atomic and molecular electronic structure calculations is reformulated in a general framework encompassing all CI methods. The linked cluster expansion is used as an intermediate device to approximate CI coefficients BK of disconnected configurations (those that can be expressed as products of combinations of singly and doubly excited ones) in terms of CI coefficients of lower-excited configurations where each K is a linear combination of configuration-state-functions (CSFs) over all degenerate elements of K. Disconnected configurations up to sextuply excited ones are selected by Brown's energy formula, ΔEK=(E-HKK)BK2/(1-BK2), with BK determined from coefficients of singly and doubly excited configurations. The truncation energy error from disconnected configurations, Δdis, is approximated by the sum of ΔEKS of all discarded Ks. The remaining (connected) configurations are selected by thresholds based on natural orbital concepts. Given a model CI space M, a usual upper bound ES is computed by CI in a selected space S, and EM=E S+ΔEdis+δE, where δE is a residual error which can be calculated by well-defined sensitivity analyses. An SCI calculation on Ne ground state featuring 1077 orbitals is presented. Convergence to within near spectroscopic accuracy (0.5 cm-1) is achieved in a model space M of 1.4× 109 CSFs (1.1 × 1012 determinants) containing up to quadruply excited CSFs. Accurate energy contributions of quintuples and sextuples in a model space of 6.5 × 1012 CSFs are obtained. The impact of SCI on various orbital methods is discussed. Since ΔEdis can readily be calculated for very large basis sets without the need of a CI calculation, it can be used to estimate the orbital basis incompleteness error. A method for precise and efficient evaluation of ES is taken up in a companion paper

The curvature of the conical intersection seam: an approximate second-order analysis

We present a method for analyzing the curvature (second derivatives) of the conical intersection hyperline at an optimized critical point. Our method uses the projected Hessians of the degenerate states after elimination of the two branching space coordinates, and is equivalent to a frequency calculation on a single Born-Oppenheimer potential-energy surface. Based on the projected Hessians, we develop an equation for the energy as a function of a set of curvilinear coordinates where the degeneracy is preserved to second order (i.e., the conical intersection hyperline). The curvature of the potential-energy surface in these coordinates is the curvature of the conical intersection hyperline itself, and thus determines whether one has a minimum or saddle point on the hyperline. The equation used to classify optimized conical intersection points depends in a simple way on the first- and second-order degeneracy splittings calculated at these points. As an example, for fulvene, we show that the two optimized conical intersection points of C2v symmetry are saddle points on the intersection hyperline. Accordingly, there are further intersection points of lower energy, and one of C2 symmetry - presented here for the first time - is found to be the global minimum in the intersection space

A Simple Access Pricing Rule to Achieve the Ramsey Outcome in Two-Way Access

In this paper, I consider a general and informationally effcient approach to determine the optimal access rule and show that there exists a simple rule that achieves the Ramsey outcome as the unique equilibrium when networks compete in linear prices without network-based price discrimination. My approach is informationally effcient in the sense that the regulator is required to know only the marginal cost structure, i.e. the marginal cost of making and terminating a call. The approach is general in that access prices can depend not only on the marginal costs but also on the retail prices, which can be observed by consumers and therefore by the regulator as well. In particular, I consider the set of linear access pricing rules which includes any fixed access price, the Efficient Component Pricing Rule (ECPR) and the Modified ECPR as special cases. I show that in this set, there is a unique access rule that achieves the Ramsey outcome as the unique equilibrium as long as there exists at least a mild degree of substitutability among networks' services.

Glover's rule in North American barn owls

Studying the geographic variation of phenotypic traits can provide key information about the potential adaptive function of alternative phenotypes. Gloger's rule posits that animals should be dark-vs. light-colored in warm and humid vs. cold and dry habitats, respectively. The rule is based on the assumption that melanin pigments and/or dark coloration confer selective advantages in warm and humid regions. This rule may not apply, however, if genes for color are acting on other traits conferring fitness benefits in specific climes. Covariation between coloration and climate will therefore depend on the relative importance of coloration or melanin pigments and the genetically correlated physiological and behavioral processes that enable an animal to deal with climatic factors. The Barn Owl (Tyto alba) displays three melanin-based plumage traits, and we tested whether geographic variation in these traits at the scale of the North American continent supported Gloger's rule. An analysis of variation of pheomelanin-based reddish coloration and of the number and size of black feather spots in 1,369 museum skin specimens showed that geographic variation was correlated with ambient temperature and precipitation. Owls were darker red in color and displayed larger but fewer black feather spots in colder regions. Owls also exhibited more and larger black spots in regions where the climate was dry in winter. We propose that the associations between pigmentation and ambient temperature are of opposite sign for reddish coloration and spot size vs. the number of spots because selection exerted by climate (or a correlated variable) is plumage trait-specific or because plumage traits are genetically correlated with different adaptations.