1,720,964 research outputs found
State coverage: an empirical analysis based on a user study
No full textState coverage is a relatively new metric to evaluate the quality of test suites. While most existing test adequacy criteria measure the degree of exploration of the code under test, state coverage estimates the strength of the assertions in the test suite. Initial experiments have shown that there is a correlation between state coverage and mutation adequacy, and that expert users can discover
new faults by modifying the test suite to increase state coverage. Since the faults injected by mutation testing are relatively simple, it is not clear whether these experiment are valid in a broader setting. Furthermore, these results may not be reproducible by average users, since they usually lack full understanding of the internals of the tool.
This paper presents a user-based experiment to evaluate whether the state coverage of a test suite correlates with the number defects it discovers. While the results of the experiments fail to confirm this hypothesis, they do raises important questions. First, test suites with high state coverage should be good in finding logical software faults, but these faults occur less frequently than structural faults. Second, state coverage is not monotonic in the size of the test suite. Therefore, adding new test cases which check new properties and detect new faults can often
reduce state coverage. Based on this, we suggest a number of improvements.sponsorship: Dries Vanoverberghe is a Postdoctoral Fellow of the Fund for Scientific Research - Flanders
(FWO).
This research is partially funded by the Interuniversity Attraction Poles Programme
Belgian State, Belgian Science Policy, by the IWT, and by the Research Fund K.U.Leuven.status: Publishe
S. Barry Cooper (1943-2015)
No full textThis article is an obituary in memoriam Barry Cooper (1943-2015
Thirty nine years of stratified trees
Full text linkoai:dspace.epoka.edu.al:1/835The stratified tree, also called van Emde Boas tree, is a data structure implementing the full repertoire of instructions manipulating a single subset of a finite ordered Universe . Instructions include , , , , , and , as well as composite ones like . The processing time per instruction is . Hence it improves upon the traditional comparison based tree structures for dense subsets ; if is sparse, meaning that the size n = # A = O(log(u)) the improvement vanishes.
Examples exist where this improvement helps to speed-up algorithmic solutions of real problems; such applications can be found for example in graph algorithms, computational geometry and forwarding of packets on the internet.
The structure was invented during a short postdoc residence at Cornell University in the fall of 1974. In the sequel of this paper I will use the original name Stratified Trees which was used in my own papers on this data structure.
There are two strategies for understanding how this improvement can be obtained. Today a direct recursive approach is used where the universe is divided into a cluster of galaxies each of size ; the set manipulation instructions decompose accordingly in a instruction at the cluster and galaxy level, but one of these two instructions is always of a special trivial type. The processing complexity thus satisfies a recurrence . Consequently .
However, this recursive approach requires address calculations on the arguments which use multiplicative arithmetical instructions. These instructions are not allowed in the Random Access Machine model (RAM) which was the standard model in the developing research area of design and analysis of algorithms in 1974. Therefore the early implementations of the stratified trees are based on a different approach which best is described as a binary-search-on-levels strategy. In this approach the address calculations are not required, and the structure can be implemented using pointers. The downside of this approach is that it leads to rather complex algorithms, which are still hard to present correctly even today. Another bad consequence was the super linear space consumption of the data structure, which was only eliminated three years later.
In this paper I want to describe the historical backgrounds against which the stratified trees were discovered and implemented. I do not give complete code fragments implementing the data structure and the operations; they can be found in the various textbooks and papers mentioned, including a Wikipedia page. Code fragments appearing in this paper are copied verbatim from the original sources; the same holds for the figures
Compared to what? An introduction to the analysis of algorithms Gregory J.E. Rawlins, (Freeman, New York, 1992), ISBN 0-7167-8243-X, xxvi + 536 pages
No full text
Dynamic data structures on multiple storage media, a tutorial
Full text linkTwo problems are considered that deal with dynamic data structures on multiple storage media. In the first problem we want to partition a range tree into parts of a small size, such that queries and updates visit only a small number of parts. In this way, the range tree can be maintained in secondary memory efficiently. The second problem is the reconstruction problem: given a main memory data structure, design a shadow administration, to be stored in secondary memory, such that the main memory structure can be reconstructed after e.g. a system crash
The problem of space invariance for sequential machines
No full textAbstractIn complexity theory the use of informal estimates can be justified by appealing to the Invariance Thesis which states that all standard models of sequential computing devices are equivalent in the sense that the fundamental complexity classes do not depend on the precise model chosen for their definition. This thesis would require, among others, that a RAM can be simulated by a Turing machine with constant factor overhead in space. We argue that the definition of RAM space, at least in the manner it is traditionally given in the literature, is inadequate for this purpose. The invariance thesis can be validated only in a weak interpretation. The rather complicated simulation which achieves the constant factor space overhead is based on a new method for condensing space and uses perfect hash functions with minimal program size
Simplicity, immunity, relativizations and nondeterminism
No full textAbstractA diagonalization method is discussed by which a recursive oracle A can be constructed such that NP(A) has a set L(A) which is both simple and P(A)-immune
- …
