Search

URI Online Judge is an online tool that has a great potential for enhancing the teaching and learning process if it is aggregated with Algorithms classes. The tool allows problem correction in real time, interaction between users and flexibility in terms of the choice of the programming language. The professor does not have to deal with the complexity of correcting several different solutions because the tool does it automatically. The students, consequently, have access to a database of problems related to several subjects in different levels of difficulty, in which they can apply the theory studied in class and get real time feedback. [ABSTRACT FROM PUBLISHER]

Biometric face recognition is one of the fields of computer vision. The part of biometric person identification has been extensivly researched. This resulted in a large number of algorithms used for person identification. This paper gives an overview and classification of those algorithms. Because of large number of algorithms, knowledge visualization is used for easier understanding of structure and connections between those algorithms. [ABSTRACT FROM PUBLISHER]

This paper addresses task assignment problem fortree-structure task model on heterogeneous multicore embedded systems with time constraint considering both execution time and communication load. The goal is to minimize the total system cost for a given task graph representing a set of tasks and data dependencies in a heterogeneous multicore systemwhile the time constraint is satisfied. Instead of assigning all the tasks to processors of the same type in a homogeneous environment, heterogeneous task assignment usually can reduce the system cost by exploring various capacities and costs in a heterogeneous multicore system. The general heterogeneous assignment problem is NP-complete. In this paper, we show that optimal task assignment can be found for some widely-used, special task graphs, such as tree-structure graph, using dynamic programming. A dynamic programming algorithm, the Tree Assign (TA) algorithm, is proposed in this paper to solve the heterogeneous task assignment problem for tree-structure task graphs. The experimental results show that our algorithm reduces the total system cost by 31.8% compared with assignment results on homogeneous multicore systems. Also, our algorithm achieves an average cost reduction by 21.9% compared with greedy algorithm. [ABSTRACT FROM PUBLISHER]

The parallel nature of the multi-core architectural design can only be fully exploited by concurrent applications. This status quo pushed productivity to the forefront of the language design concerns. The community is demanding for new solutions in the design, compilation, and implementation of concurrent languages, making this research area one of great importance and impact. To that extent this paper proposes the expression of data parallelism at subroutine level. The calling of a subroutine in this context spawns several execution flows, each operating on distinct partitions of the input dataset. Such computations can be expressed by simply annotating sequential subroutines with data distribution and reduction policies, delegating the management of the parallel execution to a dedicated runtime system. The paper overviews the key concepts of the model, illustrating them with some small programming examples, and describes a Java implementation built on top of the X10 runtime system. A performance evaluation attests that this approach can provide good performance gains without burdening the programmer with the writing of specialized code. [ABSTRACT FROM PUBLISHER]

In recent years, researchers have paid more attention to influence maximization problem. This problem is firstly defined by Domingos and Richardson as follows: finding a small set of individuals in a social network that could maximize the spread of influence under certain influence cascade model. To solve this issue, researchers proposed different algorithms. However, in all of these algorithms, the size of the chosen individuals ¨C k, is assigned in advance. In this paper, we conduct a preliminary exploration on the relationship between the size of the chosen set and the corresponding influence spread. We propose two metrics to analyze the factor k. Then we further consider the performance metric of the chosen set, which can be described by the stability of the chosen set. Experimental results on two real social networks show the efficiency and necessity of our proposed metrics. [ABSTRACT FROM PUBLISHER]

Particle Swarm Optimisation (PSO) has the advantage of finding, if not the optimum of a continuous problem space, at least a very good position and doing this with modest computational cost. However, as the number of possible optima increases, PSO will only explore a subset of these positions. Techniques such as niching can allow a small number of positions to be explored in parallel but by the time that a problem has become truly deceptive, has many many optima, there is little choice but to explore optima sequentially. PSO, once having converged, has no way of dispersing its particle so as to allow a further convergence, hopefully to a new optima. Random restarts are one way of providing this divergence, this paper suggest another inspired by Extremal Optimisation (EO). The technique proposed allows the particles to disperse by way of positions that are fitter than average. After a while dispersion ceases and PSO takes over again, but since it starts from better than average fitnesses the point it converges to is also better than average. This alternation of algorithms can carry on indefinitely. This paper examines the performance of sequential PSO exploration on a range of problems, some deceptive, some non-deceptive. As predicted, performance on deceptive problems tends to improve significantly with time while performance on non-deceptive problems, which do not have multiple positions with comparable fitness to spread through, does not. [ABSTRACT FROM PUBLISHER]

A matching which saturates all the vertices of a graph is called a perfect matching. Let GB=(U, W) be a bipartite graph with bipartitions U and W, where |U| = |W|-1 and |U|>=1. Bipartite graph GB is called critical bipartite graph if the following property holds: graph GB has a perfect matching after removing any vertex of W. Critical bipartite graph plays an important role in the design of robust job assignment circuit. This paper proposes one sufficient and necessary condition of critical bipartite graph. Based on this result, a determining algorithm is developed which is superior to the best algorithm known by far. The time complexity of our algorithm is linear. [ABSTRACT FROM PUBLISHER]

In order to extract, transform and load large scale data from heterogeneous data sources into data warehouse efficiently, the SETL system is designed and implemented in this paper. By using PERL subroutine attribute and data partition, SETL can implement ETL job easily and perform ETL job efficiently, and the plug-in design makes SETL with high scalability, and the design that performing one ETL job in one ETL pipeline makes SETL with distribution environment support. For illustration, one ETL job example is utilized to show the scalability in designing ETL job and show the high efficiency in processing large scale data. Experiments prove that SETL can extract, transform, and load large scale data into data warehouse efficiently. The SETL system simplified the ETL job design and implementation and can deal with heterogeneous data sources flexibly. It is a light-weighted, scalable and high-performance ETL system. [ABSTRACT FROM PUBLISHER]

MGRID program is adapted by SPEC from the NAS Parallel Benchmarks with modifications for portability and a different workload, and it is the only benchmark that belongs to both SPEC and NAS benchmark suites. It is also one of few SPEC 2000 codes which was preserved from SPEC95 and SPEC98. RESID is the kernel computation of MGRID. MGRID spends about 60% of the total execution time in RESID. RESID is thus clearly an important part of MGRID. This paper analyzes the characteristic of RESID, including program structure analysis, dataflow analysis and dependence analysis, designs a custom architecture for MGRID, and proposes several optimization techniques for MGRID. Experimental result verifies the effectiveness of each optimization method. [ABSTRACT FROM PUBLISHER]

In order to fully draw out the potential of lightweight and efficient of the development of the rice direct sowing technology with seed tape, the paper-making improved the design on the rice seed tape twisting machine and developed an automatic control system for the machine. The developed system consists of a controller, input control module, rice seed tape winding control module, transmission control module. An STC90C514AD chip microprocessor has been used as the controller and a LCM display module is adopted as the indicator. It used an angular displacement sensor real-time detecting on the disk diameters during the winding process, used a photoelectric sensor detecting the break of the seed tape, based on STC90C514AD to realize the rotating speed adjustment of the seed tape disk by used the step motor and it controlled the other working parts working by each motor. The system can realize the motors worked in their times and make the rotating speed of the disk reduce when the diameters increase. It avoids the seed tape broken because of the seed tape linear velocity constant and the tensions uniform in the process of the seed tape rolling. The experimental results show that the machine performs well. Coefficient of variation of the seed rope linear velocity was 4.64%, the tension uniformed during the seed tape winding process. It shows that the machine and the control system meet the overall design requirements well. [ABSTRACT FROM PUBLISHER]

In this paper, we present a new progressive algorithm for Multiple Sequence Alignment (MSA). Our algorithm adopts a new distance, called anchor distance to compute the distance between two protein sequences, and a variant of the UPGMA method to construct a guide tree. Our algorithm implements also a refinement step. Our algorithm is of complexity O(N4+N*L2) in computing time, where N is the number of the sequences and L is the length of the longest sequence. We asses our algorithm on different protein benchmarks, e.g., BALIBASE, HOMSTRAD, OXBENCH, and we compared the obtained results to those obtained with other alignment algorithms, e.g., CLUSTALW, MUSCLE, MAFFT and PROBCONS, using the Column Score (CS) and the Sum of Pairs Score (SPS). We obtained good results. [ABSTRACT FROM PUBLISHER]

The objective of this paper is to suggest a fresh approach to introductory programming curricula in the Indian school and engineering college context. The approach allows the student to connect high-school (up to 10+2) mathematics to the fundamentals of computing, algorithms and problem solving. The bridge connecting algebra and computing is functional programming, a paradigm confined over forty years to the computer science research community but now gaining popularity in industry as well as undergraduate education in some schools across the world. We show, using several examples, why and how functional programming is easier to master than traditional imperative programming. We conclude with the results of our attempts so far at introducing functional programming to students in IT colleges in India. [ABSTRACT FROM PUBLISHER]

This paper presents an algorithm to discover and reuse subroutines in Variable Size Genetic Network Programming (GNPvs) called Subroutine embedded GNPvs (SGNPvs). GNPvs is a general type of GNP, which has a direct graph representation with changeable size. In order to improve the performance of GNPvs, SGNPvs has been proposed, in which a subroutine mechanism has been introduced to GNPvs by module acquisition. In SGNPvs, useful subgraphs are extracted and reused for individuals. Through extracting new subroutines to replace the old subroutines, SGNPvs can evolve the subroutines as well as evolve the individuals. The simulation results verify the performance of SGNPvs on a well-known dynamic multi-agent test bed - Tileworld. [ABSTRACT FROM PUBLISHER]

Let F be a finite set of graphs. In the F-deletion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k vertices can be deleted from G such that the resulting graph does not contain a graph from F as a minor. F-deletion is a generic problem and by selecting different sets of forbidden minors F, one can obtain various fundamental problems such as {\sc Vertex Cover}, {\sc Feedback Vertex Set} or {\sc Tree width k-deletion}. In this paper we obtain a number of generic algorithmic results about F-deletion, when F contains at least one planar graph. The highlights of our work are: 1. A constant factor approximation algorithm for the optimization version of Planar F-deletion, 2. A linear time and single exponential parameterized algorithm, that is, an algorithm running in time O(exp(2, O(k))n), for the parameterized version of Planar F-deletion where all graphs in Planar F are connected, 3. A polynomial kernel for parameterized F-deletion. These algorithms unify, generalize, and improve a multitude of results in the literature. Our main results have several direct applications, but also the methods we develop on the way have applicability beyond the scope of this paper. Our results -- constant factor approximation, polynomial kernelization and FPT algorithms -- are stringed together by a common theme of polynomial time preprocessing. [ABSTRACT FROM PUBLISHER]

We implemented and evaluated the triple precision Basic Linear Algebra Subprograms (BLAS) subroutines, AXPY, GEMV and GEMM on a Tesla C2050. In this paper, we present a Double Single (D+S) type triple precision floating-point value format and operations. They are based on techniques similar to Double-Double (DD) type quadruple precision operations. On the GPU, the D+S-type operations are more costly than the DD-type operations in theory and in practice. Therefore, the triple precision GEMM, which is a compute-bound operation, is slower than the quadruple precision GEMM. However, the triple precision AXPY and GEMV are memory-bound operations on the GPU, thus their execution time of these triple precision subroutines is close to 3/4 of the quadruple precision subroutines. Therefore, we conclude that the triple precision value format is useful for memory-bound operations, in cases where the quadruple precision is not required, but double precision is not sufficient. [ABSTRACT FROM PUBLISHER]

The anonymous channels have been the essence of numerous protocols that include anonymous message passing between peers. The mixnet structure is one way to accomplish the anonymity. Since the publication of the Chaumian mixnet, there have been many practical implementations. There are two main approaches to implement mixnets: the decryption (Chaumian) and the re-encryption mixnets. In this paper we analyze four types of mixnets, from which one decryption and three re-encryption types. They were implemented in the Java programing language and evaluated on several criterias as: the number of messages, the total number of nodes, the number of threshold nodes, and the key length of underlying crypto system. In the results section we compare the results from the practical tests to answer the research question, which type of mixnets has better features. [ABSTRACT FROM PUBLISHER]

In this paper principles of modeling of a human centrifuge for pilot training, as a 3 DoF manipulator, are presented. The basis is a kinematic and dynamic model of the manipulator. The centrifuge represents a manipulator with three revolute joints. According to the D-H convention transformation matrices for the manipulator were derived. The problem of direct and inverse kinematics and dynamics is briefly explained. In order to control the centrifuge, control algorithms were developed and tested. New solutions for the forward and inverse kinematics and dynamics of the centrifuge will be integrated in the off-line and real-time parts of the control system, that contains the previously developed path planner adapted to novel commands. [ABSTRACT FROM PUBLISHER]

Recently, a great interest to routing concept in Delay Tolerant Networks has been increased notably. Deplorably, while several DTN routing protocols have been proposed, there are hardly any approaches which take as objective an attempt to improve such protocols. In this paper we focus on the predictability concept and present a new routing algorithm for DTN. We present a comparison to other existing DTN routing protocols such Spray & Wait, prophet, epidemic and maxprop. We prove through a various scale simulations, the efficiency in term of aborted transmissions and dropped messages between nodes, buffer time, and the hop count enhancement. [ABSTRACT FROM PUBLISHER]

In this paper we present Architecture, Algorithms and VLSI implementation in CMOS 65 nm, of an ISDB-T Digital Receiver for Fixed-Reception of Digital Television. Furthermore, we show the System Test environment used to validate the FPGA and VLSI designs. The Receiver can work on Zero-IF or IF modes and several blocks are based on CORDIC Algorithm. It is the first VLSI implementation of an ISDB-T receiver in Brazil, in full compliance with the so-called ISDB-Tb. Furthermore, it is a landmark within IC-Brazil Program, which aims the development of an ecosystem in Microelectronics, capable of insert Brazil in the International Semiconductor landscape. [ABSTRACT FROM PUBLISHER]

In distributed computing field, there are many challenges, and one of them is leader election in distributed system. It is really tough task to find suitable and efficient algorithms for leader election. The main role of an elected leader is that it performs a centralized coordination after being selected and manages the use of a shared resource in an optimal manner. Whenever a failure occurs the new leader is elected by nodes using various algorithms so that nodes can continue working. In this paper, the proposal is a new approach, the improved heap tree mechanism for electing the coordinator. The higher efficiency and better performance in the presented algorithms with respect to the existing algorithms is validated through results. [ABSTRACT FROM PUBLISHER]

In order to improve the performance of immune algorithm, chaos optimization is integrated into immune clone selection algorithm. Portion antibodies after decoding are mapped into Lozi's chaos field, and then collect every optical value by each of chaos iteration is added into the new antibody group to improve the antibody-antigen fitness value. This paper analyzes the importance of the selection probability of antibody and gives its varied calculated equation, and adopts the changeable rate of fitness by antibodies 3 times continuous generations to regulate antibody selection probability value adaptively, and gives the concrete steps for the optimization method of hybrid chaos immune algorithm with self-adaptive parameter adjusting. To compare the performance of optimization method of hybrid chaos immune algorithm with self-adaptive parameter adjusting, immune clone selection algorithm and traditional method in the literature, the three methods are used to optimize the main beam cross-section for crane structure. Comparison results indicate that the optimization method of hybrid chaos immune algorithm with self-adaptive parameter adjusting has many advantages such as better self-adaptive capacity, higher computation efficiency and design accuracy. [ABSTRACT FROM PUBLISHER]

Today small, battery-operated electrocardiograph devices, known as Ambulatory Event Monitors, are used to monitor the heart's rhythm and activity. These on-body healthcare devices typically require a long battery life and moreover efficient detection algorithms. They need the ability to automatically assess atrial fibrillation (A-Fib) risk, and detect the onset of A-Fib from EKG recordings for further clinical diagnosis and treatment. The focus of this paper is the design of a real-time early detection algorithm cascaded with an A-Fib risk assessment algorithm. We compare accuracy of machine learning schemes such as J48, Naïve Bayes, and Logistic Regression and choose the best algorithm to classify A-Fib from EKG medical data. Though all three algorithms have similar accuracy, the Logistic Regression model is selected for its easy portability to mobile devices. A-Fib risk factor is used to determine a monitoring schedule where the detection algorithm is triggered by the age dependent A-Fib incidence rate inside a circadian prevalence window. The design may provide a great public health benefit by predicting A-Fib risk and detecting A-Fib in order to prevent strokes and heart attacks. It also shows promising results in helping meet the needs for energy efficient real-time A-Fib monitoring, detecting and reporting. [ABSTRACT FROM PUBLISHER]

Active-matrix organic light emitting diode displays are prone to significant VTH and mobility variations in low-temperature polycrystalline-silicon thin-film transistors. A low-cost characterization of these variations can lead to a practical external calibration and simulation of the display non-uniformity. This paper proposes a generic methodology based on principal component analysis, relying on the display current levels corresponding to applied characterization images. This technique results in simultaneous characterization of the VTH and mobility for the entire active matrix. Measurement results show that taking advantage of spatial correlation leads to 100 times reduction in characterization time with less than 30% relative error. [ABSTRACT FROM PUBLISHER]

Cloud computing utilizes arbitrary mega-scale computing infrastructures and is currently revolutionizing the ICT landscape by allowing remote access to computing power and data over the Internet. Besides the huge economical impact Cloud technology exhibits a high potential to be a cornerstone of a new generation of sustainable and energy-efficient ICT. The challenging issue thereby is the energy-efficient utilization of physical machines (PMs) and the resource-efficient management of virtual machines (VMs) while attaining promised non-functional qualities of service expressed by means of Service Level Agreements (SLAs). Currently, there exist solutions for PM power management, VM migrations, and dynamic reconfiguration of VMs. However, most of the existing approaches consider each of them alone, and only use rudimentary concepts for migration costs or disrespect the nature of the highly volatile workloads. In this paper we present an integrated approach for VM migration and reconfiguration, and PM power management. Thereby, we incorporate an autonomic management loop, where proactive actions are suggested for all three areas in a hierarchically structured way. We evaluate our approach with both, synthetic workload data and real-word monitoring data of a Next Generation Sequencing (NGS) application used for the protein folding in the bioinformatics area. The efficacy of our approach is evaluated by considering classical algorithms like First Fit, Monte Carlo and Vector Packing, adapted for energy-efficient reallocation. The results show energy savings up to 61.6% while keeping acceptably low SLA violation rates. [ABSTRACT FROM PUBLISHER]

Microfluidic-based biochips are replacing the conventional biochemical analyzers, and are able to integrate on-chip all the necessary functions for biochemical analysis using microfluidics. The digital microfluidic biochips are based on the manipulation of liquids not as a continuous flow, but as discrete droplets. Researchers have presented approaches for the synthesis of digital microfluidic biochips, which, starting from a biochemical application and a given biochip architecture, determine the allocation, resource binding, scheduling, placement and routing of the operations in the application. The droplet volumes can vary erroneously due to parametric faults, thus impacting negatively the correctness of the application. Researchers have proposed approaches that synthesize offline predetermined recovery subroutines, which are activated online when errors occur. In this paper, we propose an online synthesis strategy, which determines the appropriate recovery actions at the moment when faults are detected. We have also proposed a biochemical application model which can capture both time-redundant and space-redundant recovery operations. Experiments performed on three real-life case studies show that, by taking into account the biochip configuration when errors occur, our online synthesis is able to reduce the application times. [ABSTRACT FROM PUBLISHER]

This paper complements our previous results in the context of effectively and efficient designing Parallel Relational Data Warehouses (PRDW) over heterogenous database clusters, which are represented by the proposal of a methodology called Fragmentation & Allocation (F& A). The main merit of F& A is that of combining the fragmentation and the allocation phases simultaneously, which are instead performed separately by traditional approaches. In this paper, we prove the practical impact and the reliability of F& A on a real-life parallel processing database system. [ABSTRACT FROM PUBLISHER]

Virtual Trip Line are system based challenges used in vehicle with GPS for traffic monitoring. In earlier method, a factor called accuracy in not been considered and significant improvement in cost, coverage, accuracy and privacy is enlight in my paper. This accuracy is achieved by using K-anonymity algorithm. when the object passes through these lines make changes in their VTLID with the help of HMAC algorithm. [ABSTRACT FROM PUBLISHER]

A digraph G=(V, E) is \textit{upward planar} if it has a planar drawing with all edges pointing upward. A sub graph \tildeG of a digraph G with an upward planar drawing is called a {\it maximal upward planar sub graph} of G if the addition of any edge in G\backslash\tildeG to \tildeG causes non-upward planarity. Binucci \emph{et al.} showed that finding even the maximum upward planar sub graph of an embedded digraph G\phi is NP-Complete \cite{Walter07}. In this paper, we compare different algorithms to find maximal upward planar sub graph of an embedded digraph. We also use a large test suite of embedded digraphs to gain a deeper understanding of upward planarity and see how the different heuristics perform in practice. [ABSTRACT FROM PUBLISHER]

Currently, incremental document clustering is one the most effective techniques to organize documents in an unsupervised manner for many Web applications. This paper summarizes the research actuality and new progress in incremental clustering algorithm in recent years. First, some representative algorithms are analyzed and generalized from such aspects as algorithm thinking, key technique, advantage and disadvantage. Secondly, we select four typical clustering algorithms and carry out simulation experiments to compare their clustering quality from both accuracy and efficiency. The work in this paper can give a valuable reference for incremental clustering research. [ABSTRACT FROM PUBLISHER]

Traditionally data cannot be delivered between isolated networks. However by using a data mule which is a combination between an electronic device and a mobile entity we can connect isolated networks. However, the main problem is that a long delay is experience and most of the time a large amount of undeliverable. In this paper we propose an algorithm that increases message delivery by clustering data mules in order to find a more reliable path between the sender and the receiver. Instead of data remaining on the same mule when travelling from one network to another, our algorithm allows mules to transfer data to nearby mules arriving to the destination network sooner. Using movement traces for the data mules for rural-like areas we compared two algorithms for a different number of nodes in the network and different communication ranges for each node. The preliminary results show that our proposed algorithm increases the network performance. [ABSTRACT FROM PUBLISHER]

In this paper we design a system that adopts a novel approach for emotional classification from human dialogue based on text and speech context. Our main objective is to boost the accuracy of speech emotional classification by accounting for the features extracted from the spoken text. The proposed system concatenates text and speech features and feeds them as one input to the classifier. The work builds on past research on music mood classification based on the combination of lyrics and audio features. The innovation in our approach is in the specific application of text and speech fusion for emotion classification and in the choice of features, Furthermore, in the absence of benchmark data, a dataset of movie quotes was developed for testing of emotional classification and future benchmarking. The comparison of the results obtained in each case shows that the hybrid text-speech approach achieves better accuracy than speech or text mining alone. [ABSTRACT FROM PUBLISHER]

Multi-layer network optimization has been studied for efficient use of network resources by solving Mixed Integer Linear Programming (MILP) problem. Here, the multi-layer network consists of lambda-layer network and IP-layer network. However, when applying this MILP problem for a large-scale network with a few hundred nodes, huge amount of variables are used and cannot be handled by middle size computers. In order to cope with this problem, some heuristic methods have been proposed and evaluated from viewpoints of accuracy and calculation time for their computation results. These heuristic methods reduce variables at lambda-layer and also decompose the original MILP problem into smaller sub-problems and induce an approximate solution by solving these smaller MILP problems. However, these heuristic methods cannot obtain accurate results in many cases. In this paper, we propose a novel variable reduction method at both lambda-layer and IP-layer by excluding long hop routes. We evaluate our proposed method and the conventional methods and show the availability of our method. [ABSTRACT FROM PUBLISHER]

A vast variety of feature selection methods have been proposed according to different metrics, such as information gain, entropy, chi-square test, t-test. Yet when applied to multi-class classification task, these methods generally suffer the “siren pitfall” of a surplus of predictive features for some classes while lack of predictive features for the remaining classes. A number of solutions to the “siren pitfall” have been proposed, yet there are still problems with these methods. For example, the selected features by “randomized feature set” method are not re-configurable; the “rand-robin” method and the “round-robin” method may miss some important features whenever the one v.s. others binary partition does not work; the computation cost of the wrapper's method is rather high. In this paper, we propose an adaptive feature selection method for multi-class classification task. With our method, the “siren pitfall” could be avoided, the selected features could be reproduced, the feature selection scheme does not rely on any prior knowledge, and the corresponding computation cost is low. Experimental results indicate the effectiveness of our adaptive feature selection method. [ABSTRACT FROM PUBLISHER]

Load balance is critical to the performance of adaptive routing algorithm for on-chip interconnection networks. Load Balance is mainly depended on the algorithm's selection strategy which is employed when the algorithm's routing function returns more than one admissible output ports. Existing selection strategies use local congestion metrics to make a port selection decision while ignore the global congestion condition, thus results in sub-optimal selections. In this paper, we propose an efficient Load-balancing inter Dimension Group Routing selection strategy (LDGR) in on-chip networks. The proposed selection strategy takes into account the neighbor's free VC count when make a routing decision. LDGR can achieve load balance over a wider area beyond local area by balancing the load of both X dimension link group and Y dimension link group. The evaluation result indicates that the proposed method outperforms local selection strategy in throughput about 13.4% on average under synthetic traffics patterns on 8×8 mesh topology. [ABSTRACT FROM PUBLISHER]

Resource provisioning based on virtual machine (VM) has been widely accepted and adopted in cloud computing environments. A key problem resulting from using static scheduling approaches for allocating VMs on different physical machines (PMs) is that resources tend to be not fully utilised. Although some existing cloud reconfiguration algorithms have been developed to address the problem, they normally result in high migration costs and low resource utilisation due to ignoring the multi-dimensional characteristics of VMs and PMs. In this paper we present and evaluate a new algorithm for improving resource utilisation for cloud providers. By using a multivariate probabilistic model, our algorithm selects suitable PMs for VM re-allocation which are then used to generate a reconfiguration plan. We also describe two heuristics metrics which can be used in the algorithm to capture the multi-dimensional characteristics of VMs and PMs. By combining these two heuristics metrics in our experiments, we observed that our approach improves the resource utilisation level by around 8% for cloud providers, such as IC Cloud, which accept user-defined VM configurations and 14% for providers, such as Amazon EC2, which only provide limited types of VM configurations. [ABSTRACT FROM PUBLISHER]

Digital micro fluidic biochips (DMFB) represent a new generation lab-on-a-chip architecture based upon micromanipulation of droplets via a programmed external electric field by an individually addressable 2D electrode array. DMFBs are classified as: Direct addressing and Cross-referencing biochips. Cross-referencing biochip technology scales down the number of pins per chip drastically, thereby reducing the costs of manufacturing and testing. However, these chips face a serious issue in terms of electrode interference during simultaneous routing of droplets. In this paper, we propose a routing-aware zone-based detailed placement scheme that rearranges the droplet locations on a pre-synthesized Bioassay schematic. The objectives of the proposed scheme include (i) an improved routing in respect of less overall routing time, more cell utilization, less crossover with intelligent collision avoidance, and (ii) enhanced pin sharing overcoming the major issue of electrode interference for Cross-referencing biochips. Simulations are carried out on four test benches of Benchmark suite III, and the results obtained are encouraging. [ABSTRACT FROM PUBLISHER]

Let \alpha be the maximal value such that the product of an n\times n^\alpha matrix by an n^\alpha\times n matrix can be computed with n^2+o(1) arithmetic operations. In this paper we show that \alpha>0.30298, which improves the previous record \alpha>0.29462 by Coppersmith (Journal of Complexity, 1997). More generally, we construct a new algorithm for multiplying an n\times n^k matrix by an n^k\times n matrix, for any value k\neq 1. The complexity of this algorithm is better than all known algorithms for rectangular matrix multiplication. In the case of square matrix multiplication (i.e., for k=1), we recover exactly the complexity of the algorithm by Coppersmith and Wino grad (Journal of Symbolic Computation, 1990). These new upper bounds can be used to improve the time complexity of several known algorithms that rely on rectangular matrix multiplication. For example, we directly obtain a O(n^2.5302)-time algorithm for the all-pairs shortest paths problem over directed graphs with small integer weights, where $n$ denotes the number of vertices, and also improve the time complexity of sparse square matrix multiplication. [ABSTRACT FROM PUBLISHER]

The abundant availability of multi-core computers makes "parallel computers" a common place and teaching Computer Science students to be able to design and develop parallel algorithms an urgent task. Most students recognize the needs of developing skills in parallel programming. However, since their Computer Science related curriculum are mostly taught based on sequential computers, introducing a new way of analysis and solving problems can be difficult. Making students interested in the subject can have a pivotal effect in the learning outcomes. In this short paper, we show several approaches we have been using to excite our students about learning parallel processing at our Concurrent Systems class, where parallel processing and parallel programming are taught. Some approach include showing students algorithms with an appeared impossible high performance, showing them simple steps to achieve 100% CPU utilization on multi-core computers, combining sequential algorithms they learned in the past to create new parallel algorithms, and challenging them with implementing some rather complex parallel algorithms. [ABSTRACT FROM PUBLISHER]

Conventional CMOS devices are facing an increasing number of challenges as the feature sizes scale down. In the meantime, new nanoscale materials, like graphene nanoribbons (GNR), have been shown to have large integration capability, and thus will probably replace CMOS devices in the future. However, in practice, the GNR wire segments can have a connection defective rate. Particularly, each wire segment has a survival probability, and thus has a chance to fail. This makes the routing in traditional ways very unreliable. In this paper, we study the routing reliability problem and propose an algorithm flow to solve it. Given a s-t routing path on a routing graph, we try to reinforce the reliability of the routing path by adding redundant wiring segments in such a way that its survival probability is maximized with a reasonable overhead of routing resources. Our proposed algorithm flow is two-fold: (1) generation of candidate redundancy segment via min-cost max-flow; (2) optimal selection among the candidates by dynamic programming. The results of extensive experiments confirm the effectiveness and efficiency of our approach. [ABSTRACT FROM PUBLISHER]

This paper presents the functional composition (FC), a new paradigm for combinational logic synthesis. FC is based on the following principles: (1) representation of logic functions as a bonded pair of functional/structural representations; (2) it starts from a set of initial functions; (3) simpler functions are associated to create more complex ones; (4) a partial order that enables dynamic programming is respected; (5) a set of allowed functions is maintained to reduce execution time/memory consumption. We present functional composition algorithms variants for Boolean factoring, AIG rewriting, minimum decision chain computation and SOP generation. [ABSTRACT FROM PUBLISHER]

In this paper, taking a three-phase 12/8 structure SR motor as its control object, the SR motor digital control system is designed based on MCF5213 which integrated the DSP computing power and MCU controller characteristics. This paper adopts the PWM voltage chopping control strategy with fuzzy logic algorithm and the angle position control strategy to realize rotor speed regulation control. The realization method of the system hardware structure and software are also introduced with verified the feasibility of the scheme through the experiment. [ABSTRACT FROM PUBLISHER]

In this paper, a new snake external force is proposed as the gradient of the image local energy diffusion potential. The local energy is computed using a bank of orthogonal log Gabor filters. The proposed Local Energy Diffusion Field (LEDF) is computed by energy diffusion Partial Differential Equation (PDE). The results of the LEDF snake were compared with the GVF snake in terms of capture range, and convergence to concavities. Experimental results showed that the LEDF field provided a wide capture range and smooth field in the object concavities. [ABSTRACT FROM PUBLISHER]

We present in this paper novel context-driven search techniques that compute the semantic similarities among different GO ontology terms. We implemented these techniques in a middleware search engine called GOcSim, which resides between user application and GO database. Most current research is focused on determining semantic similarities between GO ontology terms based solely on their IDs and proximity to one another in GO graph structure, while overlooking the contexts of the terms, which may lead to erroneous results. The context of a term T is determined by the set of other terms, whose existence is dependent on T. We propose novel techniques that determine the contexts of terms based on the concept of existence dependency. We present a stack-based sort-merge algorithm employing these techniques for determining the semantic similarities between GO terms. We evaluated GOcSim experimentally and compared it with four other methods. The results showed marked improvement. [ABSTRACT FROM PUBLISHER]

The online detection of anomalies is a vital element of operations in utility clouds. Detection should function for different levels of abstraction including hardware and software, and for the various metrics used in cloud computing systems. Given ever-increasing cloud sizes coupled with the complexity of system components, continuous monitoring leads to the overwhelming volume of data collected by health monitoring tools. High metric dimensionality and existence of interacting metrics compromise the detection accuracy and lead to high detection complexity. In this paper, we present a metric selection framework and propose systematic approaches to effectively identify and select the most essential metrics for online anomaly detection in utility clouds. Specifically, a mutual information based approach selects metrics with the maximized mutual relevance and the minimized redundancy. Then metric space combination and separation are explored to reduce the metric dimensionality further. Experimental results on utility cloud scenarios demonstrate the viability and efficiency of this framework. The selected metrics contribute to a high efficiency and accuracy in anomaly detection. [ABSTRACT FROM PUBLISHER]

The Soil Moisture and Ocean Salinity (SMOS) mission by ESA has been delivering Level 1 data to the Level 2 users since 2010. The Level 1 processing is divided in three levels: Level 1a, comprising the conversion of the raw data from MIRAS into calibrated visibilities; Level 1b, where the calibrated visibilities are corrected from the effects of unwanted sources (for example, the Sun) and are transformed into Brightness Temperatures; finally, in the Level 1c the Brightness Temperatures are geolocated over the Earth in a discrete grid and several auxiliary parameters are computed and annotated in the L1c final product. The algorithms responsible for the Calibration (L1a), Image Reconstruction (L1b) and Geolocation (L1c) have been validated during the In-Orbit Commissioning Phase that took place in the first half of 2010. However, as the knowledge on the performance of MIRAS increases, it has become necessary to set in motion a review on the current algorithms. This paper focuses on the review of the Image Reconstruction algorithms being conducted by DEIMOS Engenharia and IRAP and it is divided in the following sections: in Section 1 the theory for the proposed alternatives with respect to the baseline algorithm is demonstrated, along with several examples to ilustrate them. All the results have been obtained using the baseline algorithm or the alternatives that have been implemented in the Level 1 Prototype Processor (L1PP); in Section 2 the impact on the Level 1 Operational Processor (L1OP) is assessed, using as reference the L1PP results; and finally, in Section 3 the main conclusions found throughout this paper are summarized. [ABSTRACT FROM PUBLISHER]

One of the big challenges that teachers and students face at early stages of CSET (Computer Science, Engineering, and Technology) courses are the difficulties related to teaching and learning algorithms. Usually, such knowledge is presented during introductory programming related disciplines, when students are also presented to some programming language to describe simple algorithms. Therefore, they need to learn not only the new language but also a formal way to describe the solution of problems using that language. This is much different from any formalism they were presented in their previous student's experience. This paper presents iVProg, a system conceived to overcome some of these difficulties by using visual programming. Some experiments were conducted during three years to evaluate students' performance without the system support and with it using different didactic approaches. [ABSTRACT FROM PUBLISHER]

Community detection in social networks is a topic of central importance in modern graph mining, and the existence of overlapping communities has recently given rise to new interest in arc clustering. In this paper, we propose the notion of triangular random walk as a way to unveil arc-community structure in social graphs: a triangular walk is a random process that insists differently on arcs that close a triangle. We prove that triangular walks can be used effectively, by translating them into a standard weighted random walk on the line graph, our experiments show that the weights so defined are in fact very helpful in determining the similarity between arcs and yield high-quality clustering. Even if our technique gives a weighting scheme on the line graph and can be combined with any node-clustering method in the final phase, to make our approach more scalable we also propose an algorithm (ALP) that produces the clustering directly without the need to build the weighted line graph explicitly. Our experiments show that ALP, besides providing the largest accuracy, it is also the fastest and most scalable among all arc-clustering algorithms we are aware of. [ABSTRACT FROM PUBLISHER]

In a software watermarking environment, several graph theoretic watermark methods encode the watermark values as graph structures and embed them in application programs. In this paper we first present an efficient codec system for encoding a watermark number $w$ as a reducible permutation graph $F[\pi^*]$ through the use of the self-inverting permutation $\pi^*$ which encodes the number $w$ and, then, we propose a method for embedding the watermark graph $F[\pi^*]$ into a program $P$. The main idea behind the proposed embedding method is a systematic use of appropriate calls of specific functions of the program $P$. That is, our method embeds the graph $F[\pi^*]$ into $P$ using only real functions and thus the size of the watermarked program $P^*$ remains very small. Moreover, the proposed codec system has low time complexity, can be easily implemented, and incorporates such properties which cause it resilient to attacks. [ABSTRACT FROM PUBLISHER]

In communication networks, the distance between two nodes is one measure of transfer delay between them. Thus, it is required that the diameter of the network, which is defined as the maximum distance between every two nodes in it, is relatively small. This paper surveys the computational results on graph augmentation problems which model network design problems with diameter requirements, initiated in [F. R. K. Chung and M. R. Garey, ^^ ^^ Diameter bounds for altered graphs, " {\em J. Graph Theory}, vol. 8, pp. 511–534, 1984]. [ABSTRACT FROM PUBLISHER]

In this paper, multiple electronic court rule line representations with controlled LED light bars are proposed. The various court rule lines can be represented by the LED light bars which are controlled by 8051 MCU. In our designed system, the distinct rule lines can be shown for basketball, badminton, and volleyball courts, respectively. By this novel design, the drawbacks of overlapped and confused rule lines in the traditional courts can be improved. On other hand, this design can help the sportsmen to recognize relative rule lines and their positions. Furthermore, the pressure sensors are also considered into our design as an aiding judge system for the referees. In addition, when the player shot ball into the basket, the LED light bars of the court rule will flash and the recorded sound will be played with the sound module. Particularly, the RFID module is also considered as an electronic key to help user to get the authorization of the electronic court rule line system. This electronic court rule line system not only helps sportsmen and referees, but also connects them with audiences. [ABSTRACT FROM PUBLISHER]