An On-Line Algorithm for the Location of Cross Point Faults in Programmable Logic Arrays

An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the valgorithm is the determination of a fault set corresponding to the response obtained for a failed test. For the apparently small number of faults in this set, all other tests are generated and a fault table is formed. Subsequently, an adaptive procedure is used to diagnose the fault. Functional equivalence test is carried out to determine the actual fault class if the adaptive testing results in a set of faults with identical tests. The large amount of computation time and storage required in the determination, a priori, of all the fault equivalence classes or in the construction of a fault dictionary are not needed here. A brief study of functional equivalence among the cross point faults is also made.

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

Performance Study of a Centralized Concurrency Control Algorithm for Distributed Database Systems using SIMULA

The stimulation technique has gained much importance in the performance studies of Concurrency Control (CC) algorithms for distributed database systems. However, details regarding the simulation methodology and implementation are seldom mentioned in the literature. One objective of this paper is to elaborate the simulation methodology using SIMULA. Detailed studies have been carried out on a centralised CC algorithm and its modified version. The results compare well with a previously reported study on these algorithms. Here, additional results concerning the update intensiveness of transactions and the degree of conflict are obtained. The degree of conflict is quantitatively measured and it is seen to be a useful performance index. Regression analysis has been carried out on the results, and an optimisation study using the regression model has been performed to minimise the response time. Such a study may prove useful for the design of distributed database systems.

An algorithm for optimum control of static VAR compensators to meet phase-wise unbalanced reactive power demands

The operation of thyristor-controlled static VAR compensators (SVCs) at various conduction angles can be used advantageously to meet the unablanced reactive power demands in a system. However, such operation introduces harmonic currents into the AC system. This paper presents an algorithm to evaluate an optimum combination of the phase-wise reactive power generations from SVC and balanced reactive power supply from the AC system, based on the defined performance indices, namely, the telephone influence factor (TIF), the total harmonic current factor (IT) and the distortion factor (D). Results of the studies conducted on a typical distribution system are presented and discussed.

Algorithm of medication review in frail older people: Focus on minimizing the use of high-risk medications

Aim Frail older people typically suffer several chronic diseases, receive multiple medications and are more likely to be institutionalized in residential aged care facilities. In such patients, optimizing prescribing and avoiding use of high-risk medications might prevent adverse events. The present study aimed to develop a pragmatic, easily applied algorithm for medication review to help clinicians identify and discontinue potentially inappropriate high-risk medications. Methods The literature was searched for robust evidence of the association of adverse effects related to potentially inappropriate medications in older patients to identify high-risk medications. Prior research into the cessation of potentially inappropriate medications in older patients in different settings was synthesized into a four-step algorithm for incorporation into clinical assessment protocols for patients, particularly those in residential aged care facilities. Results The algorithm comprises several steps leading to individualized prescribing recommendations: (i) identify a high-risk medication; (ii) ascertain the current indications for the medication and assess their validity; (iii) assess if the drug is providing ongoing symptomatic benefit; and (iv) consider withdrawing, altering or continuing medications. Decision support resources were developed to complement the algorithm in ensuring a systematic and patient-centered approach to medication discontinuation. These include a comprehensive list of high-risk medications and the reasons for inappropriateness, lists of alternative treatments, and suggested medication withdrawal protocols. Conclusions The algorithm captures a range of different clinical scenarios in relation to potentially inappropriate medications, and offers an evidence-based approach to identifying and, if appropriate, discontinuing such medications. Studies are required to evaluate algorithm effects on prescribing decisions and patient outcomes.

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

A Branch and Bound Algorithm for a Transportation Type Problem with Piecewise Linear Convex Objective Function

A branch and bound type algorithm is presented in this paper to the problem of finding a transportation schedule which minimises the total transportation cost, where the transportation cost over each route is assumed to be a piecewice linear continuous convex function with increasing slopes. The algorithm is an extension of the work done by Balachandran and Perry, in which the transportation cost over each route is assumed to beapiecewise linear discontinuous function with decreasing slopes. A numerical example is solved illustrating the algorithm.

Optimal simultaneous maximum a posterioriestimation of states, noise statistics and parameters I. Algorithm

The simultaneous state and parameter estimation problem for a linear discrete-time system with unknown noise statistics is treated as a large-scale optimization problem. The a posterioriprobability density function is maximized directly with respect to the states and parameters subject to the constraint of the system dynamics. The resulting optimization problem is too large for any of the standard non-linear programming techniques and hence an hierarchical optimization approach is proposed. It turns out that the states can be computed at the first levelfor given noise and system parameters. These, in turn, are to be modified at the second level.The states are to be computed from a large system of linear equations and two solution methods are considered for solving these equations, limiting the horizon to a suitable length. The resulting algorithm is a filter-smoother, suitable for off-line as well as on-line state estimation for given noise and system parameters. The second level problem is split up into two, one for modifying the noise statistics and the other for modifying the system parameters. An adaptive relaxation technique is proposed for modifying the noise statistics and a modified Gauss-Newton technique is used to adjust the system parameters.

A parallel wilf algorithm for complex zeros of a polynomial

A global recursive bisection algorithm is described for computing the complex zeros of a polynomial. It has complexityO(n 3 p) wheren is the degree of the polynomial andp the bit precision requirement. Ifn processors are available, it can be realized in parallel with complexityO(n 2 p); also it can be implemented using exact arithmetic. A combined Wilf-Hansen algorithm is suggested for reduction in complexity.

Spatiotemporal clustering analysis and risk assessments of human cutaneous anthrax in China, 2005–2012

Objective To investigate the epidemic characteristics of human cutaneous anthrax (CA) in China, detect the spatiotemporal clusters at the county level for preemptive public health interventions, and evaluate the differences in the epidemiological characteristics within and outside clusters. Methods CA cases reported during 2005–2012 from the national surveillance system were evaluated at the county level using space-time scan statistic. Comparative analysis of the epidemic characteristics within and outside identified clusters was performed using using the χ2 test or Kruskal-Wallis test. Results The group of 30–39 years had the highest incidence of CA, and the fatality rate increased with age, with persons ≥70 years showing a fatality rate of 4.04%. Seasonality analysis showed that most of CA cases occurred between May/June and September/October of each year. The primary spatiotemporal cluster contained 19 counties from June 2006 to May 2010, and it was mainly located straddling the borders of Sichuan, Gansu, and Qinghai provinces. In these high-risk areas, CA cases were predominantly found among younger, local, males, shepherds, who were living on agriculture and stockbreeding and characterized with high morbidity, low mortality and a shorter period from illness onset to diagnosis. Conclusion CA was geographically and persistently clustered in the Southwestern China during 2005–2012, with notable differences in the epidemic characteristics within and outside spatiotemporal clusters; this demonstrates the necessity for CA interventions such as enhanced surveillance, health education, mandatory and standard decontamination or disinfection procedures to be geographically targeted to the areas identified in this study.

PLA folding algorithm from compatibility relations

The letter reports an algorithm for the folding of programmable logic arrays. The algorithm is valid for both column and row folding, although it has been presented considering only the simple column folding. The pairwise compatibility relations among all the pairs of the columns of the PLA are plotted in a matrix called the compatibility matrix of the PLA. A foldable compatibility matrix (FCM), a new concept defined in the letter, is then derived from the compatibility matrix. Once an FCM is obtained, the ordered pairs of fold-able columns and the reordering of the rows are readily determined

Design and flight testing of a bio-inspired plume tracking algorithm for unmanned serial vehicles

There is an increased interest on the use of UAVs for environmental research such as tracking bush fires, volcanic eruptions, chemical accidents or pollution sources. The aim of this paper is to describe the theory and results of a bio-inspired plume tracking algorithm. A method for generating sparse plumes in a virtual environment was also developed. Results indicated the ability of the algorithms to track plumes in 2D and 3D. The system has been tested with hardware in the loop (HIL) simulations and in flight using a CO2 gas sensor mounted to a multi-rotor UAV. The UAV is controlled by the plume tracking algorithm running on the ground control station (GCS).

Divide-and-Correct Algorithm for Division in a Negative Base

A divide-and-correct algorithm is described for multiple-precision division in the negative base number system. In this algorithm an initial quotient estimate is obtained from suitable segmented operands; this is then corrected by simple rules to arrive at the true quotient.

Divide-and-Correct Algorithm for Division in a Negative Base

A divide-and-correct algorithm is described for multiple-precision division in the negative base number system. In this algorithm an initial quotient estimate is obtained from suitable segmented operands; this is then corrected by simple rules to arrive at the true quotient.

Adaptive frequency scaled wavelet packet decomposition for frog call classification

Environmental changes have put great pressure on biological systems leading to the rapid decline of biodiversity. To monitor this change and protect biodiversity, animal vocalizations have been widely explored by the aid of deploying acoustic sensors in the field. Consequently, large volumes of acoustic data are collected. However, traditional manual methods that require ecologists to physically visit sites to collect biodiversity data are both costly and time consuming. Therefore it is essential to develop new semi-automated and automated methods to identify species in automated audio recordings. In this study, a novel feature extraction method based on wavelet packet decomposition is proposed for frog call classification. After syllable segmentation, the advertisement call of each frog syllable is represented by a spectral peak track, from which track duration, dominant frequency and oscillation rate are calculated. Then, a k-means clustering algorithm is applied to the dominant frequency, and the centroids of clustering results are used to generate the frequency scale for wavelet packet decomposition (WPD). Next, a new feature set named adaptive frequency scaled wavelet packet decomposition sub-band cepstral coefficients is extracted by performing WPD on the windowed frog calls. Furthermore, the statistics of all feature vectors over each windowed signal are calculated for producing the final feature set. Finally, two well-known classifiers, a k-nearest neighbour classifier and a support vector machine classifier, are used for classification. In our experiments, we use two different datasets from Queensland, Australia (18 frog species from commercial recordings and field recordings of 8 frog species from James Cook University recordings). The weighted classification accuracy with our proposed method is 99.5% and 97.4% for 18 frog species and 8 frog species respectively, which outperforms all other comparable methods.