We present a new approach for an average-case analysis of algorithms and data structures that supports a non-uniform distribution of the inputs and is based on the maximum likelihood training of stochastic grammars. T...
详细信息
We present a new approach for an average-case analysis of algorithms and data structures that supports a non-uniform distribution of the inputs and is based on the maximum likelihood training of stochastic grammars. The approach is exemplified by an analysis of the expected size of binary tries as well as by three sorting algorithms and it is compared to the known results that were obtained by traditional techniques. Investigating traditional settings like the random permutation model, we rediscover well-known results formerly derived by pure analytic methods;changing to biased data yields original results. All but one step of our analysis can be automated on top of a computer-algebra system. Thus Our new approach can reduce the effort required for an average-case analysis, allowing for the consideration of realistic input distributions with unknown distribution functions at the same time. As a by-product, our approach yields an easy way to generate random combinatorial objects according to various probability distributions. (C) 2009 Elsevier B.V. All rights reserved.
A detailed probabilistic analysis is given of algorithms for the Dutch national flag problem. We derive central and local limit theorems for the cost, as well as probabilities of large deviations. Performance of a rel...
详细信息
A detailed probabilistic analysis is given of algorithms for the Dutch national flag problem. We derive central and local limit theorems for the cost, as well as probabilities of large deviations. Performance of a related algorithm is also studied. (c) 2005 Elsevier B.V. All rights reserved.
We survey some problems that appear in the analysis of different problems in Computer Science, and show that they can be cast in a common framework (occupancy urn models) and admit a uniform treatment. (C) 2002 Elsevi...
详细信息
We survey some problems that appear in the analysis of different problems in Computer Science, and show that they can be cast in a common framework (occupancy urn models) and admit a uniform treatment. (C) 2002 Elsevier Science B.V. All rights reserved.
Algorithm analysis is an important part of algorithm design. Traditionally, analysis of programming code or algorithms is theoretical and mathematical. This makes it a time consuming and manual process. This limits th...
详细信息
ISBN:
(纸本)9781509027941
Algorithm analysis is an important part of algorithm design. Traditionally, analysis of programming code or algorithms is theoretical and mathematical. This makes it a time consuming and manual process. This limits the scope and scale of undertaking such a task. There has always been an ever-growing need to automate this analysis. With mobile development taking the center stage, we need to ensure that we build programs that are efficient as this translates to better power consumption and improved battery life. We have compiled this paper after taking all the limitations around the input domain into consideration. We have developed and presented the idea, data structures and the algorithm that can accomplish the automated Big O analysis of basic programs. For our research, we have considered programs written in the Java programming language. We have illustrated the working using an example. Further, we have presented the future scope of the system. Using this anyone interested in the field can enhance and extend the system.
Many algorithms perform very well in practice, but have a poor worst-case performance. The reason for this discrepancy is that worst-case analysis is often a way too pessimistic measure for the performance of an algor...
详细信息
Many algorithms perform very well in practice, but have a poor worst-case performance. The reason for this discrepancy is that worst-case analysis is often a way too pessimistic measure for the performance of an algorithm. In order to provide a more realistic performance measure that can explain the practical performance of algorithms, smoothed analysis has been introduced. It is a hybrid of the classical worst-case analysis and average-case analysis, where the performance on inputs is measured that are subject to random noise. We give a gentle, not too formal introduction to smoothed analysis by means of two examples: the k-means method for clustering and the Nemhauser/Ullmann algorithm for the knapsack problem.
The problem of edge-coloring a bipartite graph is to color the edges so that adjacent edges receive different colors. An optimal algorithm uses the minimum number of colors to color the edges. We consider several appr...
详细信息
The problem of edge-coloring a bipartite graph is to color the edges so that adjacent edges receive different colors. An optimal algorithm uses the minimum number of colors to color the edges. We consider several approximation algorithms for edge-coloring bipartite graphs and show tight bounds on the number of colors they use in the worst case. We also present results on the constrained edge-coloring problem where each color may be used to color at most k edges.
We study a class of Euclidean algorithms related to divisions where the remainder is constrained to belong to [alpha-1, alpha], for some alpha is an element of [0, 1]. The paper is devoted to the average-case analysis...
详细信息
We study a class of Euclidean algorithms related to divisions where the remainder is constrained to belong to [alpha-1, alpha], for some alpha is an element of [0, 1]. The paper is devoted to the average-case analysis of these algorithms, in terms of number of steps or bit-complexity. This is a new instance of the so-called "dynarnical analysis" method, where dynamical systems are made a deep use of. Here, the dynamical systems of interest have an infinite number of branches and they axe not Markovian, so that the general framework of dynamical analysis is more complex to adapt to this case than previously. (C) 2002 Elsevier Science (USA). All rights reserved.
The importance of parallel programming increases as multiple processor systems become accepted more widely. Recent research investigates some approaches to the design and analysis of parallel algorithms, and several e...
详细信息
The importance of parallel programming increases as multiple processor systems become accepted more widely. Recent research investigates some approaches to the design and analysis of parallel algorithms, and several examples serve to illustrate the importance of interprocessor communication in parallel processing. Various techniques that are applicable in the design and analysis of parallel algorithms are reviewed, the emphasis being on those techniques that incorporate communication aspects. Included in the research are several models of synchronous and asynchronous parallel computation and their use in the analysis of algorithms. Relatively primitive methodologies for designing parallel algorithms are examined, with the conclusion that a need exists for more general and practical methodologies. Models reviewed include: 1. a shared memory parallel method, 2. a communication-oriented model, and 3. automata models.
Worst-case analyses of two approximation algorithms for the m-machine permutation flow-shop Problem are presented. Worst-case performance ratios m/square-root 2 + O(1/m) for the former and m - 1 for the latter algorit...
详细信息
Worst-case analyses of two approximation algorithms for the m-machine permutation flow-shop Problem are presented. Worst-case performance ratios m/square-root 2 + O(1/m) for the former and m - 1 for the latter algorithm are found.
The subject of this paper is a preliminary analysis of the algorithms for automatic spatial orientation of the clouds of points obtained by using a terrestrial scanner. In the proposed data processing method, the clou...
详细信息
ISBN:
(纸本)9786197105346
The subject of this paper is a preliminary analysis of the algorithms for automatic spatial orientation of the clouds of points obtained by using a terrestrial scanner. In the proposed data processing method, the clouds of points were treated as images projected on a spherical plane of reference, additionally enriched with a depth map. The algorithms and a library of the sets of functions used in CV were presented. The implementation of a free C++ language library with algorithms used in CV was analysed. The correctness of the tie points search and operation time was examined. Clouds of points obtained from a terrestrial laser scanner Z+F 5006H were used as the source data. The analysis presented the algorithms linking the photogrammetric approach with the approach supported by CV.
暂无评论