Mathematical Preliminaries Flashcards
T/F The goal of predicate-based test generation is to generate tests from a predicate p that guarantee the detection of any error that belongs to a class of errors in the coding of p
T
What does the + sign represent?
OR
What does a multiplication mean?
AND
What is the condition part of the statement
Predicate
T/F A predicate can be converted to a Boolean expression by replacing each relational expression with a distinct Boolean variable
T
A Boolean variable or a relational expression
Simple predicate
Join one or more simple predicates using bop
Compound predicate
One or more Boolean variables joined by bop
Boolean expression
A Boolean expression is ____ if each variable in the
expression occurs only once
Singular
A Boolean expression is in ____ _____ ____ if it is represented as a sum of product terms
Disjunctive normal form
A Boolean expression is in ___ ____ ____ if it is represented as a product of sums
Conjunctive normal form
T/F Any Boolean expression in CNF can be converted to an equivalent DNF and vice versa
T
Captures flow of control within a program
Control flow graph
What has a finite set N of nodes and a finite set E of edges
Control flow graph
What does descendant mean for nodes?
There is a path from one node to the next (m to n)
What does proper descendant mean for nodes?
m != n (m and n are not the same node)
How do you denote all successor nodes of n?
succ(n)
How do you denote all predecessor nodes of n
pred(n)
If there is an edge (n,m) in E, what is n and what is m?
m is the successor of n. n is the predecessor of m
A path through G is ____if the first node along the path is Start and the terminating node is End.
complete
A path p is ____ if there exists at least one test case which when input to program P causes p to be traversed
feasible
T/F Whether a path p through program P is feasible is, in general, an undecidable problem
T
T/F Any algorithm can be expressed using only three
control structures
T
T/F The cyclomatic complexity of a nonstructured program is at least 2
F, 3
T/F A flow graph is reducible to a structured program if and only if it contains a loop with two or more exits
F, if it DOES NOT CONTAIN a loop with two or more exits
G has only one path if and only if….
V(G) = 1
Inserting a new edge in G increases V(G) by _
1
T/F V(G) depends only on the decision structure of G
T
T/F V(G) is the maximum number of linearly independent paths in G
T
What is V(G)
Cyclomatic Complexity
V(G) is always >= _
1
When is a boolean expression singular?
Each variable in the expression occurs only once
Two expressions are ____ ____ if they do not share any variable
Mutually singular
What is disjunctive normal form (DNF)?
Sum of product terms
What is conjunctive normal form (CNF)?
Product of sums
In an abstract syntax tree, what are leaf nodes?
Boolean or relational expressions
In an abstract syntax tree, what are internal nodes?
Boolean operator
T/F All loops are basic blocks by themselves
F, only pre-test loops
T/F if statements are the last statement in a basic block
T
T/F If a path is infeasible, you can cover the true and false branch
F
T/F Not all programs can be written as a structured program
F, they can
What is the structured program theorem?
Any program can be written as a structured program
For nodes n and m in N, n ____ m if n lies on every path from Start to m
Dominates
n is the ____ ____ of m when n is the last dominator of m along a path from Start to m
Immediate dominator
If n dominates m, how is it denoted?
dom(n,m)
If n is the immediate dominator of m, how is it denoted?
idom(n,m)
T/F Each node, except for Start, has a unique immediate dominator
T
T/F Start has a unique immediate dominator
F
For nodes n and m in N, n ____ m if n lies on every path from m to the End node
Post-dominates
If n post-dominates m, how is it denoted?
pdom(n,m)
n is the ____ ____ of m if n is the first post-dominator along a path from m to End
immediate post-dominator
If n is the immediate post-dominator of m, how is it denoted?
ipdom(n,m)
T/F Each node, except for End, has a unique
immediate post-dominator
T
A sequence of instructions forms a ____ ____ if the instruction in each position dominates, or always executes before all those in later positions and no other instruction executes between two instructions in the sequence
Basic block
T/F Inserting or deleting functional statements to G affects V(G)
F, it does not
When is a path through G considered complete?
The first node along the path is Start and the terminating node is End
When is a path considered feasible?
There exists at least one test case which when input to program P causes p to be traversed
When is a flow graph reducible to a structured program?
If and only if it does not contain a loop with two or more exits
__ is the maximum number of linearly independent paths in G
V(G)
When are two or more expressions mutually singular?
When they don’t share any variable
T/F if statements are the first statement in a basic block
F, last
End has a unique immediate post-dominator
F
