The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
58 views

What did Dijkstra think about Monte Carlo algorithms?

In A Discipline of Programming, Dijkstra wrote: Two circumstances have changed the scene since then.* The one is the insight that, even in the case of fully deterministic machines, program testing ...
1
vote
1answer
47 views

Validate that a threaded binary tree works as intended

I am attempting to validate that my threaded binary tree’s insertion and deletion works as intended. Would it be safe to assume that the following procedure would have tested all corner cases at ...
0
votes
1answer
54 views

Test cases for graph embeddability problem

Suppose that I have a polynomial-time algorithm to solve the graph embeddability problem. $k$-embeddability problem : Given an edge-weighted and undirected graph $G = (V,E)$, can we assign ...
3
votes
1answer
81 views

How to Generate Control flow graph from a Petri net model?

My research is mainly focused on generating test sequences automatically using Colored Petri net.CFG provides techniques for generating test sequences. But some papers says that, test sequence ...
2
votes
0answers
46 views

Memory testing algorithms? [closed]

What am I doing? I have been digging more and more and googling more than often finding very small amount of results I am trying to make a RAM testing program that can do memory testing with the ...
5
votes
1answer
187 views

Transition coverage for a DFA

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
3
votes
3answers
123 views

Minimum number of tests to identify subset of modules that trigger a bug?

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run. I can run the program with any desired ...
2
votes
1answer
1k views

Control flow graphs - Tree decomposition

Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example : While A if B do .. else do .. end while For ...
2
votes
2answers
899 views

How can I debug my pseudocode algorithm?

The algorithms for the problem I am working on become more and more complex as I try to improve their performance. They already span several pages with cases and sub-cases, and will probably become ...
10
votes
3answers
229 views

When testing n items, how to cover all t-subsets by as few s-subsets as possible?

This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem. There are 10 items to be tested, say A to J, and ...
0
votes
1answer
339 views

In control flow graphs, what is the difference between a path and a branch?

I'm studying for an exam on software testing and in my notes I found this: Many more paths than branches. A pragmatic compromise will be needed I cannot ...
4
votes
0answers
74 views

Is there difference between workflow-aware and non-workflow-aware optimal selection of web-service composition?

Small introduction. We have a task that consists of sub-tasks. Each sub-task can be implemented by some set of web-services. We want to find the best implementation of this task. "Best" means it has ...
4
votes
0answers
247 views

Test cases for λ-Calculus

For testing automated theorem provers we have Seventy-Five Problems for Testing Automatic Theorem Provers by Pelletier. Are there any such standard/well regarded tests for a λ-calculus that verify ...
1
vote
1answer
141 views

Phrase generators for use with testing grammars that don't use a seed

In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and ...
16
votes
1answer
755 views

Generating inputs for random-testing graph algorithms?

When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness....