cs3003_2025T3_ET_FN.pdf
AI: Search Methods for Problem Solving · End Term · Sep 2025 FN
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 2 MSQ · 0.0 marks
[[IMAGE:93b86d00fec429a7_2_2]]
Printed graph sheets were provided on time.
Printed graph sheets were provided late.
Printed graph sheets were not provided.
I used the graph sheets.
I did not use graph sheets.
A published solution is not available for this question yet.
Question 3 SHORT_TEXT · 1.0 marks
**SEARCH**
The figure shows a map on a uniform grid where each tile is 1x1 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in **alphabetical** order.
Use Manhattan Distance as the heuristic function.
**Tie-breaker:** If several nodes have the same cost, use node labels to break the tie.
[[IMAGE:93b86d00fec429a7_3_3]]
Based on the above data, answer the given subquestions.
What is the path found by the Best First Search algorithm? Enter the path as a comma separated
list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: S,X,Y,Z,G**
A published solution is not available for this question yet.
Question 4 SHORT_TEXT · 1.0 marks
**SEARCH**
The figure shows a map on a uniform grid where each tile is 1x1 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in **alphabetical** order.
Use Manhattan Distance as the heuristic function.
**Tie-breaker:** If several nodes have the same cost, use node labels to break the tie.
[[IMAGE:93b86d00fec429a7_3_3]]
Based on the above data, answer the given subquestions.
[[IMAGE:93b86d00fec429a7_4_4]]
A published solution is not available for this question yet.
Question 5 SHORT_TEXT · 1.0 marks
**SEARCH**
The figure shows a map on a uniform grid where each tile is 1x1 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in **alphabetical** order.
Use Manhattan Distance as the heuristic function.
**Tie-breaker:** If several nodes have the same cost, use node labels to break the tie.
[[IMAGE:93b86d00fec429a7_3_3]]
Based on the above data, answer the given subquestions.
What is the path found by Branch-and-Bound search algorithm? Enter the path as a comma
separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: S,X,Y,Z,G**
A published solution is not available for this question yet.
Question 6 MCQ · 1.0 marks
**SEARCH**
The figure shows a map on a uniform grid where each tile is 1x1 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in **alphabetical** order.
Use Manhattan Distance as the heuristic function.
**Tie-breaker:** If several nodes have the same cost, use node labels to break the tie.
[[IMAGE:93b86d00fec429a7_3_3]]
Based on the above data, answer the given subquestions.
For the given map, which algorithm finds the shortest path from S to G?
[[IMAGE:93b86d00fec429a7_5_5]]
[[IMAGE:93b86d00fec429a7_5_6]]
[[IMAGE:93b86d00fec429a7_5_7]]
[[IMAGE:93b86d00fec429a7_5_8]]
A published solution is not available for this question yet.
Question 7 MCQ · 1.0 marks
**SEARCH**
The figure shows a map on a uniform grid where each tile is 1x1 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in **alphabetical** order.
Use Manhattan Distance as the heuristic function.
**Tie-breaker:** If several nodes have the same cost, use node labels to break the tie.
[[IMAGE:93b86d00fec429a7_3_3]]
Based on the above data, answer the given subquestions.
Select the correct statement about the given graph.
Heuristic is admissible.
Heuristic is not admissible.
Heuristic is admissible in some cases and not admissible in other cases.
There is not enough information to determine admissibility.
A published solution is not available for this question yet.
Question 8 NAT · 1.0 marks
**GAMES: ALPHA-BETA**
Consider a game tree with the root node as MAX.
Alpha-Beta algorithm is in mid-flight currently processing a path from the root to a node labeled
N.
The snapshot of evals of nodes along the current path is: 2, 14, 4, 10, N.
Where evals are restricted to EVEN NUMBERS greater than zero and less than 15.
Based on the above data, answer the given subquestions.
Determine the eval of node N that will induce a cutoff to prune its siblings.
Enter an even number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 16**
A published solution is not available for this question yet.
Question 9 MCQ · 1.0 marks
**GAMES: ALPHA-BETA**
Consider a game tree with the root node as MAX.
Alpha-Beta algorithm is in mid-flight currently processing a path from the root to a node labeled
N.
The snapshot of evals of nodes along the current path is: 2, 14, 4, 10, N.
Where evals are restricted to EVEN NUMBERS greater than zero and less than 15.
Based on the above data, answer the given subquestions.
What type of cut-off is induced by the eval selected for N?
Alpha Cutoff
Beta Cutoff
Alpha-Beta Cutoff
None of these
A published solution is not available for this question yet.
Question 10 SHORT_TEXT · 1.0 marks
**GAMES: SSS STAR**
The figure shows a game tree with evaluation function values at the horizon nodes.
The horizon nodes are labeled from A to D.
Use these labels to enter a horizon node or a list of horizon nodes in short answers.
**Tie-breaker:**
When several nodes carry the same best cost then select the deepest node, if tie persists then
select the leftmost of the deepest nodes to break the tie.
[[IMAGE:93b86d00fec429a7_7_9]]
Run SSS* algorithm on the game tree, then answer the sub-questions.
[[IMAGE:93b86d00fec429a7_7_10]]
A published solution is not available for this question yet.
Question 11 SHORT_TEXT · 1.0 marks
**GAMES: SSS STAR**
The figure shows a game tree with evaluation function values at the horizon nodes.
The horizon nodes are labeled from A to D.
Use these labels to enter a horizon node or a list of horizon nodes in short answers.
**Tie-breaker:**
When several nodes carry the same best cost then select the deepest node, if tie persists then
select the leftmost of the deepest nodes to break the tie.
[[IMAGE:93b86d00fec429a7_7_9]]
Run SSS* algorithm on the game tree, then answer the sub-questions.
[[IMAGE:93b86d00fec429a7_8_11]]
A published solution is not available for this question yet.
Question 12 SHORT_TEXT · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR decomposition of problem S into smaller problems.
The nodes are uniquely identified by labels (S, A, B, C, …).
Each node shows the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs.
A primitive node is added to the graph, with SOLVED status, when its parent is expanded.
And therefore, a primitive node is never expanded.
**The cost of each edge is 2 units.**
**Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels.
**Tie-breaker 2:** For AND nodes, select the unsolved branch with the highest cost.
[[IMAGE:93b86d00fec429a7_9_12]]
Use AO* algorithm to solve S, then answer the sub-questions.
[[IMAGE:93b86d00fec429a7_10_13]]
A published solution is not available for this question yet.
Question 13 SHORT_TEXT · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR decomposition of problem S into smaller problems.
The nodes are uniquely identified by labels (S, A, B, C, …).
Each node shows the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs.
A primitive node is added to the graph, with SOLVED status, when its parent is expanded.
And therefore, a primitive node is never expanded.
**The cost of each edge is 2 units.**
**Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels.
**Tie-breaker 2:** For AND nodes, select the unsolved branch with the highest cost.
[[IMAGE:93b86d00fec429a7_9_12]]
Use AO* algorithm to solve S, then answer the sub-questions.
[[IMAGE:93b86d00fec429a7_10_14]]
A published solution is not available for this question yet.
Question 14 MCQ · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR decomposition of problem S into smaller problems.
The nodes are uniquely identified by labels (S, A, B, C, …).
Each node shows the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs.
A primitive node is added to the graph, with SOLVED status, when its parent is expanded.
And therefore, a primitive node is never expanded.
**The cost of each edge is 2 units.**
**Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels.
**Tie-breaker 2:** For AND nodes, select the unsolved branch with the highest cost.
[[IMAGE:93b86d00fec429a7_9_12]]
Use AO* algorithm to solve S, then answer the sub-questions.
What can you conclude about the given AND-OR decomposition?
The heuristic is admissible.
The heuristic is inadmissible.
The heuristic is sometimes admissible and sometimes inadmissible.
A published solution is not available for this question yet.
Question 15 MSQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for classification of vehicles is shown in the figure. Labels A1, A2, A3, ..., A10, A11, A12,
A13, ..., and B1, B2, B3 uniquely identify nodes in the network. When required, use the above label
ordering to **break ties** and to enter short answers.
[[IMAGE:93b86d00fec429a7_12_15]]
The Working Memory contains the following WMEs uniquely identified by timestamps (sequence
numbers). Assume that WMEs reside in the appropriate Alpha node, and Beta nodes simply point
to WMEs in the Alpha nodes.
[[IMAGE:93b86d00fec429a7_13_16]]
For each WME identify its location (node label) in the Rete Net, then prepare the conflict set for the
first Match-Resolve-Execute cycle, then answer the sub-questions.
Which of the following rule-data tuples occur in the conflict set?
Luxury-Car,104,107
Minivan,103,106
Truck,101,102,105
Minivan,103,106,108
A published solution is not available for this question yet.
Question 16 MCQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for classification of vehicles is shown in the figure. Labels A1, A2, A3, ..., A10, A11, A12,
A13, ..., and B1, B2, B3 uniquely identify nodes in the network. When required, use the above label
ordering to **break ties** and to enter short answers.
[[IMAGE:93b86d00fec429a7_12_15]]
The Working Memory contains the following WMEs uniquely identified by timestamps (sequence
numbers). Assume that WMEs reside in the appropriate Alpha node, and Beta nodes simply point
to WMEs in the Alpha nodes.
[[IMAGE:93b86d00fec429a7_13_16]]
For each WME identify its location (node label) in the Rete Net, then prepare the conflict set for the
first Match-Resolve-Execute cycle, then answer the sub-questions.
If the Inference Engine uses **Specificity** for conflict resolution then which rule-data tuple will fire in
the first round?
Luxury-Car,104,107
Minivan,103,106
Truck,101,102,105
Minivan,103,106,108
A published solution is not available for this question yet.
Question 17 MCQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for classification of vehicles is shown in the figure. Labels A1, A2, A3, ..., A10, A11, A12,
A13, ..., and B1, B2, B3 uniquely identify nodes in the network. When required, use the above label
ordering to **break ties** and to enter short answers.
[[IMAGE:93b86d00fec429a7_12_15]]
The Working Memory contains the following WMEs uniquely identified by timestamps (sequence
numbers). Assume that WMEs reside in the appropriate Alpha node, and Beta nodes simply point
to WMEs in the Alpha nodes.
[[IMAGE:93b86d00fec429a7_13_16]]
For each WME identify its location (node label) in the Rete Net, then prepare the conflict set for the
first Match-Resolve-Execute cycle, then answer the sub-questions.
If the Inference Engine uses **Recency** for conflict resolution which rule-data tuple will fire in the
first round?
Luxury-Car,104,107
Minivan,103,106
Truck,101,102,105
Minivan,103,106,108
A published solution is not available for this question yet.
Question 18 MCQ · 1.0 marks
**AUTOMATED PLANNING 1**
Answer the given subquestions.
Consider actions a and b and two **feasible** orderings (a then b) and (b then a). Which of the
following conditions will produce different outcomes for each ordering?
P is in pre(a) and also in del-effects(b).
P is in add-effects(a) and also in del-effects(b).
None of these.
A published solution is not available for this question yet.
Question 19 MSQ · 1.0 marks
**AUTOMATED PLANNING 1**
Answer the given subquestions.
In planning graphs constructed by GraphPlan, actions a and b in layer n are mutex __________ .
if P in pre(a) and Q in pre(b) are mutex
if P is in pre(a), in del-effects(a), in pre(b) and also in del-effects(b)
if P is in pre(a) and also in del-effects(b)
if P is in add-effects(a) and also in del-effects(b)
A published solution is not available for this question yet.
Question 20 MCQ · 1.0 marks
**AUTOMATED PLANNING 1**
Answer the given subquestions.
In planning graphs constructed by GraphPlan, propositions P and Q in layer n are mutex __________
.
if every action pair (a,b) with P in add-effects(a) and Q in add-effects(b) in layer
n is mutex
if at least one action pair (a,b) with P in add-effects(a) and Q in add-effects(b) in
layer n is mutex
none of these
A published solution is not available for this question yet.
Question 21 MCQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:93b86d00fec429a7_16_17]]
The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two
consecutive propositional layers (layer k and k+1) are presented in the figure.
Both proposition layers are fully populated (no missing propositions).
[[IMAGE:93b86d00fec429a7_17_18]]
Mutex proposition pairs in layer k are:
(on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)).
Populate the action layer and mutex links, then answer the sub-questions.
What can you conclude about layer k?
Layer k describes the start state of the planning problem.
Layer k cannot describe the start state of the planning problem.
There is insufficient information to comment on layer k.
A published solution is not available for this question yet.
Question 22 MSQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:93b86d00fec429a7_16_17]]
The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two
consecutive propositional layers (layer k and k+1) are presented in the figure.
Both proposition layers are fully populated (no missing propositions).
[[IMAGE:93b86d00fec429a7_17_18]]
Mutex proposition pairs in layer k are:
(on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)).
Populate the action layer and mutex links, then answer the sub-questions.
Which of the following are **applicable** actions in layer k+1?
Putdown(A)
Stack(A,B)
Unstack(A,B)
Unstack(B,C)
A published solution is not available for this question yet.
Question 23 MSQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:93b86d00fec429a7_16_17]]
The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two
consecutive propositional layers (layer k and k+1) are presented in the figure.
Both proposition layers are fully populated (no missing propositions).
[[IMAGE:93b86d00fec429a7_17_18]]
Mutex proposition pairs in layer k are:
(on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)).
Populate the action layer and mutex links, then answer the sub-questions.
Which of the following are **mutex** pairs in layer k+1?
Putdown(A) and Stack(A,B)
Stack(A,B) and Unstack(A,B)
nop-3 and nop-4
A published solution is not available for this question yet.
Question 24 MCQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:93b86d00fec429a7_16_17]]
The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two
consecutive propositional layers (layer k and k+1) are presented in the figure.
Both proposition layers are fully populated (no missing propositions).
[[IMAGE:93b86d00fec429a7_17_18]]
Mutex proposition pairs in layer k are:
(on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)).
Populate the action layer and mutex links, then answer the sub-questions.
armEmpty and clear(B) in layer k+1 are non mutex because __________ .
nop-3 and nop-4 are non mutex
PutDown(A) and nop-4 are non mutex
None of these
A published solution is not available for this question yet.
Question 25 MCQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C (processed in that order)
with domains and constraints as shown below.
[[IMAGE:93b86d00fec429a7_19_19]]
Draw the constraint graph and matching-diagram then answer the sub-questions.
Is the given CSP arc consistent?
Yes
No
Cannot be determined
A published solution is not available for this question yet.
Question 26 MCQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C (processed in that order)
with domains and constraints as shown below.
[[IMAGE:93b86d00fec429a7_19_19]]
Draw the constraint graph and matching-diagram then answer the sub-questions.
If the given CSP is not already arc consistent, make it arc consistent, then check if it is path
consistent.
It is path consistent.
It is not path consistent.
Path consistency does not apply because the constraint graph is cyclic.
A published solution is not available for this question yet.
Question 27 SHORT_TEXT · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C (processed in that order)
with domains and constraints as shown below.
[[IMAGE:93b86d00fec429a7_19_19]]
Draw the constraint graph and matching-diagram then answer the sub-questions.
Does the given CSP have a solution?
Enter the solution for the variables A,B,C as a comma separated list.
Enter NIL if there is no solution.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 1,2,3**
A published solution is not available for this question yet.