- Write pseudocode for a brute force algorithm for each of the following, and de
ID: 671248 • Letter: #
Question
- Write pseudocode for a brute force algorithm for each of the following, and determine its time and space complexity.
1. Determine whether a given Boolean expression is satisfiable.
Notes:
A. A Boolean expression is one written using only the three Python connectives (and, or, not), and variables ranging over True and False, and parentheses.
B. A Boolean expression is satisfiable if there is a substitution of values for its variables that makes it true.
C. Operations available:
1. vars(E) gives a list of the variables occurring in Boolean Expression E
2. val(E) gives the value of a ground Boolean expression (that is, one written with True, False, and, or, not and parentheses)
3. sub(V,X,E) returns the result of substituting value V for variable X in expression E
basic list operations are available
Explanation / Answer
A)
input x (length n)
input y (length l)
match = -1; // set to start
index of matching substring if we find it found = true
for i=1 to n-l+1 \try all start positions in x
found = true;
for j=1 to l \ try to match y with x[i...i+l-1]
if x[i+j-1] != y[j] then {
found = false; break;
}
end
if found then {
match=i; break;
}
end;
print(match);
Using brute force, we can test whether or not each pair is a dominating set in polynomial time. But then note that such an approach will not run in polynomial time when, for example, k = n/10
B)
import java.io.*; // for I/O
class TrialDivision
{
public static void main(String[] args)
{
int n;
boolean prime;
n=getInt();
// test if n is prime
prime=true;
for (i=2; i < n; i++) {
if (n % i == 0) prime=false;
}
if (prime) putText("Prime") else putText("Composite’);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.