MODULE - I
1. CSPs are – [1 mark]
a. an alternative formulation for general problem solving method
b. ways of formulating problems using variables and constraints
c. problems that come in the way of satisfying constraints
d. problems that arise after constraint satisfaction
e. none of the above
Ans= a, b
2. Which of the following statements are true regarding solving a CSP? [1 mark]
a. Values must be assigned to ALL variables such that ALL constraints are satisfied.
b. Values must be assigned to at least SOME variables such that ALL constraints are satisfied.
c. Values must be assigned to ALL variables such that at least SOME constraints are satisfied.
d. Values must be assigned to at least SOME variables such that at least SOME constraints are satisfied.
Ans=a
3. Consider the following constraint network R = <{x1, x2, x3}, {D1, D2, D3}, {C}> where D1 = D2 = D3 = {a, b, c} and C = <{x1, x2, x3}, {<a, a, b>, <a, b, b>, <b, a, c>, <b, b, b>}. How many solutions exist? [1 mark]
Ans: 4
4. “A constraint can be viewed as a pair <S, R>, where S is the _____, and R is the relation.” Fill in the blanks with a single word in lowercase. [1 mark]
Ans: scope
5. Which of the following statements are true? [2 marks]
a. Since the number of binary CSPs is less than the number of non-binary CSPs, not every primal constraint graph will have an equivalent dual constraint graph.
b. Since the number of binary CSPs is less than the number of non-binary CSPs, two or more primal constraint graphs will have the same equivalent dual constraint graph.
c. Every primal constraint graph has an equivalent dual constraint graph. <
d. The number of possible primal constraint graphs is more than the number of possible dual constraint graphs.
MODULE - II
6. Which of the following are necessary conditions for two constraint networks to be equivalent? [2 marks]
a. both networks must have the same set of variables <
b. the sets of variables in both networks must have the same domains
c. both networks must have the same set of solutions <
d. both networks must have the same set of constraints
e. if a constraint with the same scope is present in both networks, the relations in the constraint in both networks must be the same
7. The arity of a constraint is [1 mark]
a. The number of constraints that have at least one common variable with this constraint.
b. The number of rows in its relation.
c. The cardinality of its scope. <
d. None of the above
8. Given the following constraint networks X,Y and Z with four variables x1,x2,x3 and x4 all defined on the same domain values {red,blue}. The constraints in the network are as follows: [1 mark]
X: R13=R14=R23=R24={(red,blue) (blue,red)}
Y: R13=R14=R23=R24={(red,blue) (blue,red)} , R12={(red,red) (blue,blue)}
Z: R13=R14=R23=R24={(red,blue) (blue,red)} , R34={(red,blue) (blue,red)}
Identify which of them are equivalent:
a. Z and X
b. Z and Y
c. X and Y <
d. All are equivalent
9. In the previous question, for network X, what is the result of composition of constraints R13=R14? [1 mark]
a. R34={(red,blue)(blue,red)}
b. R34={(red,red)(blue)(blue)} <
c. R34={(red,red)(blue,blue)(red,blue)(blue,red)}
d. None of the above
Given a constraint networks with three variables x1, x2 and x3 with one constraint, ρ123={(1,1,2) (1,2,2) (2,1,3) (2,2,2)}
10. The number of constraints in the projection network P(ρ) for the above network is ________ .
Ans: 3 [1 mark]
11. Given the above network with constraint ρ123, which of the following tuple(s) will be present in the solution of projection network of ρ:
a. (1,1,3)
b. (2,1,3)
c. (1,2,3)
d. (2,1,2) <
[1 mark]
12. Given the following constraint networks X,Y and Z with three variables x1,x2 and x3 all defined on the same domain values {red,blue}. The constraints in the network are R12=R23={(red,blue) (blue,red)}. If you construct a minimal network for the given CSP, the number of edges in the matching diagram of the minimal network will be ___________.
[1 mark]
Ans: 6
MODULE - III
13. Given a constraint satisfaction problem with two variables x and y whose domains are Dx={1,2,3}, Dy={1,2,3} and constraint x<y. What happens to Dx and Dy after the REVISE(x,y) algorithm is called?
a. Both Dx and Dy remain the same as before
b. Dx ={1,2} and Dy ={1,2,3}
c. Dx ={2,3} and Dy ={1,2}
d. Dx ={ } and Dy ={1,2,3}
[2 marks]
Ans: (b)
14. What are the complexities of the REVISE algorithm for arc consistency and AC-1 algorithm
a. O(ek2) and O(ek3)
b. O(k2) and O(nek3)
c. O(k2) and O(ek3)
d. O(k2) and O(ek2)
[1 mark]
Ans: (b)
15. Which of the following statement(s) is/are true about the AC-4 algorithm?
a. It does not use the REVISE algorithm
b. The best case performance of AC-4 is better than that of AC-1 and AC-3
c. A value from a domain is removed only if it has no support from the neighbouring variable
d. All of the above
[2 mark]
Ans: (a) and (c)
16. Node consistency is also known as
a. 3 consistency
b. 2 consistency
c. 1 consistency
d. None of the above
[1 mark]
Ans: (c)
MODULE - IV
17. Given a constraint graph with an ordering, the parent of a given node is - [1 mark]
a. the node preceding the given node in the ordering.
b. the node succeeding the given node in the ordering.
c. the latest variable earlier in the ordering connected to the given variable. <
d. the earliest variable later in the ordering connected to the given variable.
Given the following constraint network
18. Which of the following are possible solution(s) for the above constraint network [2 marks]
a. A=1,B=3,C=1,D=1,E=2
b. A=1,B=3,C=1,D=3,E=2 <
c. A=1,B=3,C=2,D=3,E=2
d. A=2,B=3,C=2,D=2,E=1
e. A=2,B=3,C=2,D=3,E=1
f. A=2,B=3,C=1,D=3,E=2 <
19. Given an ordering CDBAE. If you try to perform the bucket elimination algorithm over this network and ordering, what should be the initial constraints in Bucket C? [1 mark]
a. C≠E,C≠B
b. C≠E
c. C≠B
d. empty bucket <
20. Given an ordering CDBAE. If you try to perform the bucket elimination algorithm over this network and ordering, what will be the constraints in bucket B after the variable A is processed?
a. B≠C [2 marks]
b. RBCD
c. B≠C || RBCD <
d. empty bucket
21. In the previous question, if the ordering was EDCBA, what would be your answer [1 mark]
a) B≠C
b) B≠C,B≠E
c) B≠A,B≠C,B≠E || RCED
d) B≠C,B≠E || RCED <
22. For a given graph and ordering, the width of an ordering is
a. the minimum width over all the nodes
b. the maximum width over all the nodes
c. the sum of width of all the nodes
d. None of the above
[1 mark]
Ans: (b)
MODULE - V
23. In the Backtracking algorithm which of the following are true? [1 mark]
a. The Select-Value procedure selects for the current variable a value that must be consistent with both the current partial instantiation, and the future variables.
b. If Select-Value finds no value for the current variable, a dead-end occurs. <
c. If Select-Value finds no value for the current variable, the algorithm terminates as no solution can be found.
d. None of the above.
24. The Generalized-Look-Ahead algorithm with Select-Value-Forward-Checking is applied to the CSP in this figure, for the ordering (x1, x2, x3, x4, x5, x6, x7). If the algorithm chooses the assignments x1 = r, x2 = b, and x3 = b, how many total values are pruned from the domains of the variables x4, x5, x6, and x7? (Answer is a single number) [2 marks]
Ans: ???
25. The Generalized-Look-Ahead algorithm with Select-Value-Arc-Consistency is applied to the CSP in this figure, for the ordering (x1, x2, x3, x4, x5, x6, x7). If the algorithm chooses the assignments x1 = r, x2 = b, and x3 = b, how many total values are pruned from the domains of the variables x4, x5, x6, and x7? (Answer is a single number) [5 marks]
Ans: ???
26. The Generalized-Look-Ahead algorithm with Select-Value-Partial-Look-Ahead is applied to the CSP in this figure, for the ordering (x1, x2, x3, x4, x5, x6, x7). If the algorithm chooses the assignments x1 = r, x2 = b, and x3 = b, how many total values are pruned from the domains of the variables x4, x5, x6, and x7? (Answer is a single number) [3 marks]
Ans: ???
27. The Generalized-Look-Ahead algorithm with Select-Value-Full-Look-Ahead is applied to the CSP in this figure, for the ordering (x1, x2, x3, x4, x5, x6, x7). If the algorithm chooses the assignments x1 = r, x2 = b, and x3 = b, how many total values are pruned from the domains of the variables x4, x5, x6, and x7? (Answer is a single number) [3 marks]
Ans: ???
Dynamic Variable Ordering With Forward Checking (DVFC) algorithm is applied to the CSP in this figure.
28. What is the order in which DVFC will inspect the nodes. [5 marks]
a) x1, x2, x3, x4, x5, x6, x7
b) x7, x6, x5, x4, x3, x2, x1
c) x1, x5, x3, x4, x2, x7, x6
d) x1, x4, x2, x7, x5, x6, x3
e) x1, x4, x2, x7, x3, x6, x5
f) none of the above
Ans=f
29. List the number of times DVFC backtracks. (Answer is a single number) [2 marks]
Ans: 0
The Davis-Putnam, Logemann, and Loveland (DPLL) algorithm is applied to the following set of clauses: {(ㄱA V B), (ㄱC V A), (A V B V D), (C)}.
30. How many times is unit propagation done? [2 marks]
Ans: 3
31. How many solutions does the above set of clauses have? [1 mark]
Ans: 2
32. What is the minimum number of nodes that need to be removed from the following graph for a cycle-cutset? [2 marks]
Ans: 2
MODULE - VI
33. Chronological backtracking in depth first search involves - [1 mark]
a. undoing the assignment to the last variable assigned.
b. undoing the assignment to the first variable assigned.
c. backtracking to the least constrained variable assigned.
d. backtracking to the most constrained variable assigned.
Ans=a
34. Let ā be a consistent assignment to a set of variables. We say that ā is a conflict set with respect to a variable X if – [1 mark]
a. no value in X is consistent with ā.
b. some value in X is consistent with ā.
c. all values in X are consistent with ā.
d. none of the above.
Ans=a
35. Let ā be a consistent assignment to a proper subset of variables. Identify the true statements. [2 marks]
a. If ā is a nogood then it is necessarily a conflict set with respect to some variable X.
b. If ā is a conflict set with respect to some variable X then it is necessarily a nogood.
c. A nogood ā is not necessarily a conflict set with respect to some variable X.
d. A conflict set ā with respect to some variable X may not be a nogood.
e. If ā is a nogood then there is no solution to the CSP.
f. If ā is a nogood then there may still be solution to the CSP.
Ans=b, c , e
36. An algorithm searching for a solution to a CSP on a ordered set of variables {x1, x2, ..., x9} reaches a deadend at variable x7. The algorithm then jumps back to the variable x3 to assign a new value. This jump is safe iff - [marks 2]
a. the domain D3 of x3 has at least one more value left.
b. if a new value assigned instead to a variable xi, 3<i<7, could have led to a solution.
c. if no new value assigned instead to a variable xi, 3<i<7, could have led to a solution.
d. if the domain Di of all variables xi, 3<i<7, have at least one more value left.
Ans=c
37. An algorithm searching for a solution to a CSP on a ordered set of variables {x1, x2, ..., x9} reaches a deadend at variable x7. This deadend is an internal deadend if - [mark 1]
a. the domain D7 of x7 has at least one more value left.
b. in the previous round it tried a value for the variable x6 and failed.
c. in the previous round it tried a value for the variable x8 and failed.
d. in the previous round it tried a value for the variable x9 and failed.
Ans=c,d
38. The set of relevant deadends in the context of Graph Based Backjumping [2 marks]
a. includes all the deadends encountered by the algorithm since backtracking started from the latest node visited.
b. includes all the deadends encountered by the algorithm since the current internal deadend was invisited.
c. must include at least one leaf deadend.
d. can have more than one leaf deadend.
Ans=b,c,d
39. The induced parent of a deadend in Graph Based Backjumping [1 mark]
a. is the parent of the deadend being considered.
b. is the earliest node that is the parent of the deadend being considered.
c. is the earliest induced ancestor of the parent that is earlier that the current deadend.
d. is the latest induced ancestor of the parent that is earlier that the current deadend.
Ans=d
40. Figure MAP-COLOURING is the constraint graph for a map colouring problem with the ordering (x1, x2, ..., x7) on the variables. An edge between two nodes means they should be assigned different colours. Let the domains be D1={w,r}, D2={b,r,w}, D3={r,b,g}, D4={b,w}, D5={r,b,g}, D6={g,b,y}, D7={b,r,w}. Gaschnig’s Backjumping arrives at a deadend on variable x4 with the partial solution (w,b,r). The culprit variable identified by the algorithm is - [2 marks]
a. x1
b. x2
c. x3
d. x4
e. none of the above
Ans=b
41. Figure MAP-COLOURING is the constraint graph for a map colouring problem with the ordering (x1, x2, ..., x7) on the variables. An edge between two nodes means they should be assigned different colours. Let the domains be D1={w,r}, D2={b,r,g}, D3={r,b,g}, D4={b,w}, D5={r,b,g}, D6={g,b,y}, D7={b,r,w}. Gaschnig’s Backjumping arrives at a deadend on variable x7 which is conflicting with (w,w,r,b,b,g). The culprit variable identified by the algorithm is - [2 marks]
a. x1
b. x2
c. x3
d. x4
e. x5
f. x6
g. x7
h. none of the above.
Ans=d
42. After jumping back to the culprit variable identified in the previous problem, the Gaschnig’s Backjumping algorithm finds that [1 mark]
a. the culprit variable is a deadend.
b. the culprit variable is not a deadend.
Ans=a
43. Continuing the above problem, the Gaschnig’s Backjumping algorithm will next assign a new value to which variable? [2 marks]
a. x1
b. x2
c. x3
d. x4
e. x5
f. x6
g. x7
h. none of the above.
Ans=c
44. Figure MAP-COLOURING is the constraint graph for a map colouring problem with the ordering (x1, x2, ..., x7) on the variables. An edge between two nodes means they should be assigned different colours. Let the domains be D1={w,r}, D2={b,r,g}, D3={r,b,g}, D4={b,w}, D5={r,b,g}, D6={g,b,y}, D7={b,r,w}. Graph Based Backjumping arrives at a deadend on variable x7 which is conflicting with (w,w,r,b,b,g). The culprit variable identified by the algorithm is - [2 marks]
a. x1
b. x2
c. x3
d. x4
e. x5
f. x6
g. x7
h. none of the above.
Ans=f
45. After jumping back to the culprit variable identified in the previous problem, the Graph Based Backjumping algorithm finds that [1 mark]
a. the culprit variable is a deadend.
b. the culprit variable is not a deadend.
Ans= b
46. Continuing the above problem, the Graph Based Backjumping algorithm will next assign a new value to which variable? [2 marks]
a. x1
b. x2
c. x3
d. x4
e. x5
f. x6
g. x7
h. none of the above.
Ans= f
47. Figure MAP-COLOURING is the constraint graph for a map colouring problem with the ordering (x1, x2, ..., x7) on the variables. An edge between two nodes means they should be assigned different colours. Let the domains be D1={w,r}, D2={b,r,g}, D3={r,b,g}, D4={b,w}, D5={r,b,g}, D6={g,b,y}, D7={b,r,w}. Conflict Directed Backjumping arrives at a deadend on variable x7 which is conflicting with (w,w,r,b,b,g). The culprit variable identified by the algorithm is - [2 marks]
a. x1
b. x2
c. x3
d. x4
e. x5
f. x6
g. x7
h. none of the above.
Ans=d
48. After jumping back to the culprit variable identified in the previous problem, the Conflict Directed Backjumping algorithm finds that [1 mark]
a. the culprit variable is a deadend.
b. the culprit variable is not a deadend.
Ans=a
49. Continuing the above problem, the Conflict Directed Backjumping algorithm will next assign a new value to which variable? [2 marks]
a. x1
b. x2
c. x3
d. x4
e. x5
f. x6
g. x7
h. none of the above.
Ans=b
MODULE - VII
50. Model Based Diagnosis employs [1 marks]
a. mathematical models of devices that generate predicted behaviour.
b. algorithms to search the space of models consistent with observations.
c. diagnosis arrived at by manipulating physical models of devices.
d. algorithms to mimic how human technicians learn diagnosis.
Ans= a, b
51. According to Jon Doyle the term Truth Maintenance System is probably a misnomer. An alternative he suggests is, [1 mark]
a. Truth Destruction System
b. Falsity Destruction System
c. Reason Maintenance System
d. Truth Evolving System
Ans=c
52. In a Truth Maintenance System a justification is [2 marks]
a. made for an assertion that is added based on an inference.
b. a link to the assertions that match the antecedent(s) of the rule used for inference.
c. an argument that that justifies why the TMS should be used.
d. a reason given why a particular rule was chosen to be fired.
Ans=a, b
53. For adder multiplier circuit given in the figure above – given the inconsistency in the value of F1 which of following are conflict sets,
[2 marks]
a. M1, M2, M3
b. A1, A2
c. M1, M2, A1
d. M2, M3, A2
e. A1, A2, M3
Ans=c
54. Given the above conflict set which of the following cannot be a single fault [2 marks]
a. A1
b. A2
c. M1
d. M2
e. M3
Ans=b, e
55. Given the above conflict set which of the following cannot be a double fault [2 marks]
a. A1,A2
b. A1,M1
c. A1,M2
d. M1,M2
e. A2,M2
f. A2,M3
g. M2,M3
Ans=f
56. For the above adder multiplier circuit and the data shown which of the following is another conflict set
[2 marks]
a. A1, A2, M1, M2
b. A1, A2, M1, M3
c. A1, A2, M2, M3
d. A1, M1, M2, M3
e. A2, M1, M2, M3
Ans=b
57. Given the conflict sets above which single faults are eliminated [2 marks]
a. A1
b. A2
c. M1
d. M2
e. M3
ans=b, d ,e
Consider a planning problem in the blocks world domain.
58. If the above problem is solved as DCSP, which of the following are the initial set of constraints that denote the active propositions?
a) Active {On0(A,B),On0(C,D),Clear0(A),Clear0(C}
b) Active {On4(A,B),On4(C,D),Clear4(A),Clear4(C}
c) Active {On0(D,B),OnT0(A),OnT0(C),Clear0(D)}
d) Active {On4(D,B),OnT4(A),OnT4(C),Clear4(D)}
[1 mark]
Ans: (b)
59. Which of the following are true about the initial state in the state variable representation
a) On(A,S0)=table
b) Clear(B,S0)=1
c) Clear(C,S0)=0
d) OnT(D,S0)=0
[1 mark]
Ans: (a), (d)
60. Which of the following constraints denote the frame axioms for the given domain
a) <a1=UnStack(D,B), Clear(C,S0)=1, Clear(C,S1)=1 >
b) <a1=UnStack(D,B), Clear(A,S0)=1, Clear(A,S1)=1 >
c) <a1=UnStack(D,B), On(B,S0)=1, On(B,S1)=0 >
d) <a1=PickUp(A), Clear(C,S0)=1, Clear(C,S1)=0 >
[1 mark]
Ans: (a), (b)
61. Which of the following formulas are valid encoding of actions as clauses in SAT
a) UnStack(D,B,t) ⊃ On(D,B, t-1) ∧ ArmEmpty(t-1) ∧Clear(B,t-1)
b) Stack(A,B,t) ⊃ Holding(A, t-1) ∧Clear(B,t-1)
c) UnStack(D,B,t) ⊃ On(D,B, t-1) ∧ ArmEmpty(t-1) ∧Clear(D,t-1)
d) Stack(A,B,t) ⊃ On(A,B, t-1) ∧ ArmEmpty(t-1) ∧Clear(D,t-1)
[1 mark]
Ans: (b), (c)
62. Which of the following formulas denote the action that are mutex while encoding the planning graph as SAT
a) UnStack(D,B,0) ∧ PickUp(A,0)
b) UnStack(D,B,0) ∧ PickUp(C,0)
c) ¬UnStack(D,B,0) ∨ ¬PickUp(C,0)
d) ¬UnStack(D,B,0) ∨ ¬PickUp(A,0)
[1 mark]
Ans: (c), (d)
No comments:
Post a Comment