4
votes
Test cases for graph embeddability problem
No finite set of test cases can prove correctness of an algorithm, if we have no information about the form or structure of the algorithm and if the set of possible inputs is infinite.
For any finite ...
D.W.♦
- 156k
4
votes
How to Generate Control flow graph from a Petri net model?
Since you are interested in generating test sequences automatically using colored Petri nets, note that it's not clear that you need reduction to control flow graphs (and dealing with all the related ...
- 540
4
votes
Accepted
optimal testing strategy
in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense.
This is the famous two egg problem where
You are given ...
- 268
3
votes
Accepted
Are there invariants in text processing problems?
Yes. One can find invariants in any program. The notion is well-defined and meaningful in any program (whether it is useful in practice is a different question).
Normally identifying invariants is ...
D.W.♦
- 156k
3
votes
Accepted
Finding minimal and complete test sets for circuits
Yes. One can construct a Majella sequence of length $n \cdot 2^n + 1$, recursively. It's easy to see you can't do any better than this, so this is optimal.
Definition. I'll say that a sequence $x_0,...
D.W.♦
- 156k
3
votes
Accepted
How a Symbolic Evaluator Generates Test Input for this Example
Tools that solve problems like this often use a SMT (Satisfiability Modulo Theories) solver. This a SAT solver combined with a "theory solver" that can understand operations in some domain.
For ...
- 1,013
2
votes
Accepted
What to prove and how to prove it
I think you raise an important point, which is that in a high level language, specifications can be hard to distinguish from implementations. For example, in Coq, the specification of "The sum of the ...
- 8,114
2
votes
How to test if my implementation of tree/graph data structures are correct?
Identify the representation invariants. Add assert statements to check that the representation invariant holds (sometimes called a repOK function). Use random testing to generate millions of test ...
D.W.♦
- 156k
2
votes
What is the theory behind testing fixes for intermittent bugs?
You juggle with "probabilities" without defining any. There are two different questions here.
For practical programs, can I use random testing to establish that any given execution has close to 100%...
- 72k
1
vote
Are Unit Tests Required if you have a good End to End Test?
This isn't really a CS question, more of a Software Engineering question. Still: If you find an error in an end-to-end test, and you can then replicate it in a simpler unit test, then you definitely ...
- 865
1
vote
Accepted
Populating a vector of numbers to expose an error in a function implementation
Multilinear polynomials
If you're willing to use probabilistic methods, I suggest using a randomized algorithm for polynomial identity testing.
You want to test whether $f(x)=g(x)$ holds for all $x$, ...
D.W.♦
- 156k
1
vote
Accepted
Problem with understanding the Mathematical Equations related to Testing Tool
They are statements about patterns of correct and incorrect code:
For all call sites L1, there does not exist a store site L2 such that ... (and here I’m not clear—is that L2 may follow L1? Or that ...
- 645
1
vote
How to test implementation details when there are multiple ways of implementing the algorithm, without reading the code?
To find out if it is e.g. doing binary search (or using hashing, or whatever) inside, you have to look at what it is doing. No way around it.
Why would you insist on a particular algorithm? The whole ...
- 13.9k
1
vote
How to choose the right input(s) to test my algorithm?
To achieve 100% coverage of all the cases, you'll probably need many test cases.
You might want to do some reading on "test case generation". Typically, software developers think through the ...
D.W.♦
- 156k
1
vote
How to choose the right input(s) to test my algorithm?
If you want to automatically explore the state space of a program, you could try a fuzzer like AFL. But usually programmers do this by running the program under a debugger and thinking a bit about how ...
- 5,931
1
vote
What to prove and how to prove it
It's not correct to say that in TLA+, the program is the specification. I don't know of any system where that is true.
Rather, TLA+ is a way of writing a formal model of a system. You could think ...
D.W.♦
- 156k
1
vote
Pseudocode for constructing control flow graph
To create a CFG you begin with an Abstract Syntax Tree (AST). So I
assume you have an AST available. The first step is to collect the
nodes in the tree into basic blocks. This step is optional but ...
- 1,151
1
vote
Accepted
Validate that a threaded binary tree works as intended
Shortly - no, it is not safe.
Huge random test does not guarantee success (but of course, when there is a bug, it finds it in the most cases).
To test threaded tree with deletion and insertion you ...
- 9,425
Only top scored, non community-wiki answers of a minimum length are eligible