cs3003_2026T1_ET_FN.pdf
AI: Search Methods for Problem Solving · End Term · Jan 2026 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:b985b053c5c2456d_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**
Consider a water-jug puzzle with three jugs a, b and c of capacities 5L, 3L and 2L, respectively.
A state, encoded as a digit string ABC, denotes volume of water in jugs a, b and c, respectively.
For example, state 212 denotes that jugs a, b and c contain 2L, 1L and 2L of water, respectively.
[[IMAGE:b985b053c5c2456d_3_3]]
MoveGen takes a state ABC and returns a set of neighbours that are one move away from ABC.
For example, MoveGen(212) = { 032, 302, 410, 230 }.
Based on the above data, answer the given subquestions.
Let 320 be the start state and 401 be the goal state, find the shortest path from start to goal. Enter
the path starting with 320 as a comma separated list of states.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 320,302,500**
A published solution is not available for this question yet.
Question 4 SHORT_TEXT · 1.0 marks
**SEARCH**
Consider a water-jug puzzle with three jugs a, b and c of capacities 5L, 3L and 2L, respectively.
A state, encoded as a digit string ABC, denotes volume of water in jugs a, b and c, respectively.
For example, state 212 denotes that jugs a, b and c contain 2L, 1L and 2L of water, respectively.
[[IMAGE:b985b053c5c2456d_3_3]]
MoveGen takes a state ABC and returns a set of neighbours that are one move away from ABC.
For example, MoveGen(212) = { 032, 302, 410, 230 }.
Based on the above data, answer the given subquestions.
Let 320 be the start state and 401 be the goal state, find the sequence of moves that produce the
shortest path from start to goal. Enter the sequence of moves as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: aEb,aTc,bETa,cETb**
A published solution is not available for this question yet.
Question 5 MCQ · 1.0 marks
**SEARCH ALGORITHMS**
Answer the given subquestions.
Which of the following variants of Depth First Iterative Deepening (DFID) is guaranteed to find the
shortest path if one exists?
DFID that inspects only new nodes.
DFID that inspects new as well as open nodes.
DFID that inspects new as well as closed nodes.
None of these.
A published solution is not available for this question yet.
Question 6 MSQ · 1.0 marks
**SEARCH ALGORITHMS**
Answer the given subquestions.
Given a finite state space with edge costs that may or may not be Euclidean and a heuristic
function whose properties are not known, which of the following algorithms are suitable for
finding the optimal path?
Depth First Search
Breadth First Search
Dijkstra's algorithm
Branch and Bound Search
A*
WA* for some w
Sparse Memory Graph Search (SMGS)
A published solution is not available for this question yet.
Question 7 MSQ · 1.0 marks
**SEARCH ALGORITHMS**
Answer the given subquestions.
If w is set to zero then wA* algorithm will __________ .
behave like Best-First Search
behave like Dijkstra's algorithm
always find the optimal path
sometimes find a suboptimal path
A published solution is not available for this question yet.
Question 8 SHORT_TEXT · 1.0 marks
**GAMES: ALPHA-BETA**
Consider a game tree with the root node as MAX, where an arbitrary path from the root reaches
the subtree shown in the figure.
[[IMAGE:b985b053c5c2456d_5_4]]
Each leaf node A to D takes a **UNIQUE EVAL VALUE** from the set {1, 2, 3, 4}.
Alpha-Beta algorithm is entering the subtree with alpha=2 and beta=4;
find an optimal eval assignment (for nodes A to D) that maximizes the number of leaves pruned;
find the minimax value, the type of cuts and the leaves pruned for that assignment.
Based on the above data, answer the given subquestions.
Enter the optimal eval assignment (evals of nodes A to D) in the text box.
Enter a comma separated list of evals.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 1,2,3,4**
A published solution is not available for this question yet.
Question 9 NAT · 1.0 marks
**GAMES: ALPHA-BETA**
Consider a game tree with the root node as MAX, where an arbitrary path from the root reaches
the subtree shown in the figure.
[[IMAGE:b985b053c5c2456d_5_4]]
Each leaf node A to D takes a **UNIQUE EVAL VALUE** from the set {1, 2, 3, 4}.
Alpha-Beta algorithm is entering the subtree with alpha=2 and beta=4;
find an optimal eval assignment (for nodes A to D) that maximizes the number of leaves pruned;
find the minimax value, the type of cuts and the leaves pruned for that assignment.
Based on the above data, answer the given subquestions.
The minimax value of the subtree for the optimal eval assignment is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
A published solution is not available for this question yet.
Question 10 SHORT_TEXT · 1.0 marks
**GAMES: ALPHA-BETA**
Consider a game tree with the root node as MAX, where an arbitrary path from the root reaches
the subtree shown in the figure.
[[IMAGE:b985b053c5c2456d_5_4]]
Each leaf node A to D takes a **UNIQUE EVAL VALUE** from the set {1, 2, 3, 4}.
Alpha-Beta algorithm is entering the subtree with alpha=2 and beta=4;
find an optimal eval assignment (for nodes A to D) that maximizes the number of leaves pruned;
find the minimax value, the type of cuts and the leaves pruned for that assignment.
Based on the above data, answer the given subquestions.
Enter the number of alpha-cuts followed by the number of beta-cuts as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 1,2**
A published solution is not available for this question yet.
Question 11 SHORT_TEXT · 1.0 marks
**GAMES: ALPHA-BETA**
Consider a game tree with the root node as MAX, where an arbitrary path from the root reaches
the subtree shown in the figure.
[[IMAGE:b985b053c5c2456d_5_4]]
Each leaf node A to D takes a **UNIQUE EVAL VALUE** from the set {1, 2, 3, 4}.
Alpha-Beta algorithm is entering the subtree with alpha=2 and beta=4;
find an optimal eval assignment (for nodes A to D) that maximizes the number of leaves pruned;
find the minimax value, the type of cuts and the leaves pruned for that assignment.
Based on the above data, answer the given subquestions.
Enter the label of leaf nodes pruned by Alpha-Beta algorithm, or enter NIL if no leaves were
pruned.
Enter a comma separated list of labels (A to D), or enter NIL.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: W,X,Y,Z**
A published solution is not available for this question yet.
Question 12 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 J.
Where applicable, use these labels 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:b985b053c5c2456d_8_5]]
Run SSS* algorithm on the game tree, then answer the sub-questions.
Find the horizon nodes that are assigned SOLVED status by SSS* algorithm. Enter the labels of
those nodes in the textbox, or enter NIL if no nodes are assigned SOLVED status.
Enter node labels as a comma separated list in **alphabetical** order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: X,Y,Z**
A published solution is not available for this question yet.
Question 13 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 J.
Where applicable, use these labels 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:b985b053c5c2456d_8_5]]
Run SSS* algorithm on the game tree, then answer the sub-questions.
Find the SOLVED horizon nodes that are pruned from the queue by SSS* algorithm, i.e., SOLVED
horizon nodes removed from the queue when a MAX-ancestor is SOLVED. Enter the labels of those
nodes in the textbox, or enter NIL if SOLVED nodes were never pruned.
Enter node labels as a comma separated list in **alphabetical** order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: X,Y,Z**
A published solution is not available for this question yet.
Question 14 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:b985b053c5c2456d_10_6]]
Use AO* algorithm to solve S, then answer the sub-questions.
List the nodes expanded by AO* algorithm. List the nodes in the order they are expanded.
Observe that primitive nodes are not expanded.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: S,X,Y,Z**
A published solution is not available for this question yet.
Question 15 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:b985b053c5c2456d_10_6]]
Use AO* algorithm to solve S, then answer the sub-questions.
For each node expanded by AO* algorithm, determine the value propagated to the start node S.
Enter the values of S as a list.
Enter a comma separated list of numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 12,42,17**
A published solution is not available for this question yet.
Question 16 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:b985b053c5c2456d_10_6]]
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 17 MSQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A part of the Rete Net that classifies mushrooms (as edible or poisonous) is shown in the figure.
The labels A1, A2, ..., A10, A16, ..., B1, B2, B3, R1, …, R4 uniquely identify the nodes in the network.
When required, use the above label ordering to **break ties** and to enter short answers.
**Note:** "attribute <> x" is true when that attribute exists and its value is not equal to x.
[[IMAGE:b985b053c5c2456d_12_7]]
Run the Rete algorithm for the Working Memory shown below, the WMEs are in timestamp order.
Assume that WMEs reside at appropriate Alpha nodes, and the Beta nodes point to WMEs residing
in Alpha nodes.
[[IMAGE:b985b053c5c2456d_12_8]]
For each WME identify its location (node label) in the Rete Net, and prepare the conflict set for the
first cycle, then answer the given subquestions.
Which of the following rule-data tuples are in the conflict-set?
R1,205,206
R2,209
R3,204,207
R4,203,208
R1,203,206
R4,205,208
A published solution is not available for this question yet.
Question 18 MSQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A part of the Rete Net that classifies mushrooms (as edible or poisonous) is shown in the figure.
The labels A1, A2, ..., A10, A16, ..., B1, B2, B3, R1, …, R4 uniquely identify the nodes in the network.
When required, use the above label ordering to **break ties** and to enter short answers.
**Note:** "attribute <> x" is true when that attribute exists and its value is not equal to x.
[[IMAGE:b985b053c5c2456d_12_7]]
Run the Rete algorithm for the Working Memory shown below, the WMEs are in timestamp order.
Assume that WMEs reside at appropriate Alpha nodes, and the Beta nodes point to WMEs residing
in Alpha nodes.
[[IMAGE:b985b053c5c2456d_12_8]]
For each WME identify its location (node label) in the Rete Net, and prepare the conflict set for the
first cycle, then answer the given subquestions.
If the Inference Engine uses **Specificity** as the conflict resolution strategy then which of the
following rule-data tuples will qualify?
R1,205,206
R2,209
R3,204,207
R4,203,208
R1,203,206
R4,205,208
A published solution is not available for this question yet.
Question 19 MCQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A part of the Rete Net that classifies mushrooms (as edible or poisonous) is shown in the figure.
The labels A1, A2, ..., A10, A16, ..., B1, B2, B3, R1, …, R4 uniquely identify the nodes in the network.
When required, use the above label ordering to **break ties** and to enter short answers.
**Note:** "attribute <> x" is true when that attribute exists and its value is not equal to x.
[[IMAGE:b985b053c5c2456d_12_7]]
Run the Rete algorithm for the Working Memory shown below, the WMEs are in timestamp order.
Assume that WMEs reside at appropriate Alpha nodes, and the Beta nodes point to WMEs residing
in Alpha nodes.
[[IMAGE:b985b053c5c2456d_12_8]]
For each WME identify its location (node label) in the Rete Net, and prepare the conflict set for the
first cycle, then answer the given subquestions.
If the Inference Engine uses **Recency** as the conflict resolution strategy then which of the
following rule-data tuples will qualify?
R1,205,206
R2,209
R3,204,207
R4,203,208
R1,203,206
R4,205,208
A published solution is not available for this question yet.
Question 20 MSQ · 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 (each taken independently) will produce different outcomes for each
ordering?
P is in pre(a) and Q is 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 21 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 __________ .
only if every P in pre(a) is mutex with every Q in pre(b)
only if every P in pre(a) is present 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 22 MCQ · 1.0 marks
**AUTOMATED PLANNING 1**
Answer the given subquestions.
In planning graphs constructed by GraphPlan, which of the following are true?
If actions A and B are non mutex in a layer n then it will remain non mutex in
all future layers.
If actions A and B are non mutex in a layer n then it can become mutex in
some future layer.
If actions A and B are non mutex in a layer n then it must be mutex in a past
layer.
None of these.
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:b985b053c5c2456d_16_9]]
Consider the following planning problem.
[[IMAGE:b985b053c5c2456d_16_10]]
Based on the above data, answer the given subquestions.
Which of the following are **applicable** actions for FSSP?
Putdown(C)
Stack(B,C)
Stack(C,D)
Stack(C,E)
Unstack(D,A)
Unstack(E,B)
A published solution is not available for this question yet.
Question 24 MSQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:b985b053c5c2456d_16_9]]
Consider the following planning problem.
[[IMAGE:b985b053c5c2456d_16_10]]
Based on the above data, answer the given subquestions.
Which of the following are **relevant** actions for BSSP?
Putdown(C)
Stack(B,C)
Stack(C,D)
Stack(C,E)
Unstack(D,A)
Unstack(E,B)
A published solution is not available for this question yet.
Question 25 MSQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:b985b053c5c2456d_16_9]]
Consider the following planning problem.
[[IMAGE:b985b053c5c2456d_16_10]]
Based on the above data, answer the given subquestions.
In the planning graph, which of the following are mutex action pairs in layer 1?
Stack(C,D) and nop for armEmpty
Stack(C,D) and nop for clear(E)
Stack(C,D) and nop for holding(C)
Stack(C,D) and Putdown(C)
A published solution is not available for this question yet.
Question 26 MSQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:b985b053c5c2456d_16_9]]
Consider the following planning problem.
[[IMAGE:b985b053c5c2456d_16_10]]
Based on the above data, answer the given subquestions.
In the planning graph, which of the following are mutex proposition pairs in layer 1?
armEmpty and clear(E)
armEmpty and holding(C)
on(C,D) and clear(E)
on(C,D) and onTable(C)
A published solution is not available for this question yet.
Question 27 MSQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:b985b053c5c2456d_16_9]]
Consider the following planning problem.
[[IMAGE:b985b053c5c2456d_16_10]]
Based on the above data, answer the given subquestions.
In the planning graph, which of the following are **applicable** actions in layer 2?
Pickup(C)
Putdown(C)
Unstack(D,A)
Unstack(E,B)
A published solution is not available for this question yet.
Question 28 MCQ · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:b985b053c5c2456d_16_9]]
Consider the following planning problem.
[[IMAGE:b985b053c5c2456d_16_10]]
Based on the above data, answer the given subquestions.
For the given planning problem, does a plan exist?
Yes
No
Cannot be determined
A published solution is not available for this question yet.
Question 29 SHORT_TEXT · 1.0 marks
**AUTOMATED PLANNING 2**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:b985b053c5c2456d_16_9]]
Consider the following planning problem.
[[IMAGE:b985b053c5c2456d_16_10]]
Based on the above data, answer the given subquestions.
For the given planning problem, the length of the plan found by GraphPlan is __________ .
Enter an integer or enter NIL if GraphPlan cannot find a plan.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 12**
A published solution is not available for this question yet.
Question 30 MSQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C where the domains and constraints are:
[[IMAGE:b985b053c5c2456d_19_11]]
where, mod(n,d) returns the remainder after dividing n by d, for example, mod(8,3)=2,
mod(12,4)=0, mod(9,4)=1.
Compute the three relations to match the domain constraints, then draw the constraint graph and
matching-diagram, and then answer the sub-questions.
Which of the following tuples occur in R_AC?
(1,2)
(2,1)
(2,4)
(4,2)
A published solution is not available for this question yet.
Question 31 MSQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C where the domains and constraints are:
[[IMAGE:b985b053c5c2456d_19_11]]
where, mod(n,d) returns the remainder after dividing n by d, for example, mod(8,3)=2,
mod(12,4)=0, mod(9,4)=1.
Compute the three relations to match the domain constraints, then draw the constraint graph and
matching-diagram, and then answer the sub-questions.
Which of the following tuples occur in R_BA?
(1,3)
(2,2)
(3,1)
(4,2)
A published solution is not available for this question yet.
Question 32 MCQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C where the domains and constraints are:
[[IMAGE:b985b053c5c2456d_19_11]]
where, mod(n,d) returns the remainder after dividing n by d, for example, mod(8,3)=2,
mod(12,4)=0, mod(9,4)=1.
Compute the three relations to match the domain constraints, then draw the constraint graph and
matching-diagram, and 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 33 MCQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C where the domains and constraints are:
[[IMAGE:b985b053c5c2456d_19_11]]
where, mod(n,d) returns the remainder after dividing n by d, for example, mod(8,3)=2,
mod(12,4)=0, mod(9,4)=1.
Compute the three relations to match the domain constraints, then draw the constraint graph and
matching-diagram, and then answer the sub-questions.
If the given CSP is not already arc-consistent, then make it arc-consistent, and then check if the
resulting network is path consistent.
It is path consistent.
It is not path consistent.
Path consistency does not apply because the constraint graph has a cycle.
A published solution is not available for this question yet.
Question 34 SHORT_TEXT · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C where the domains and constraints are:
[[IMAGE:b985b053c5c2456d_19_11]]
where, mod(n,d) returns the remainder after dividing n by d, for example, mod(8,3)=2,
mod(12,4)=0, mod(9,4)=1.
Compute the three relations to match the domain constraints, then draw the constraint graph and
matching-diagram, and 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.