cs3003_2025T2_ET_FN.pdf
AI: Search Methods for Problem Solving · End Term · May 2025 FN
← Course papers · Start practice / exam
This page contains the reliably extracted subset, not the complete original paper.
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 63 MSQ · 0.0 marks
[[IMAGE:f1707c1d7585ad06_2_0]]
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 64 SHORT_TEXT · 1.0 marks
**SEARCH**
[[IMAGE:f1707c1d7585ad06_2_1]]
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**
A published solution is not available for this question yet.
Question 65 SHORT_TEXT · 1.0 marks
**SEARCH**
[[IMAGE:f1707c1d7585ad06_2_1]]
Based on the above data, answer the given subquestions.
[[IMAGE:f1707c1d7585ad06_3_2]]
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 66 SHORT_TEXT · 1.0 marks
**SEARCH**
[[IMAGE:f1707c1d7585ad06_2_1]]
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.
Use the Branch-and-Bound variation that avoids cyclic expansions like S,E,S,E,S,E,...
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 67 MCQ · 1.0 marks
**SEARCH**
[[IMAGE:f1707c1d7585ad06_2_1]]
Based on the above data, answer the given subquestions.
For the given map, which algorithm finds the shortest path from S to G?
[[IMAGE:f1707c1d7585ad06_4_3]]
[[IMAGE:f1707c1d7585ad06_4_4]]
[[IMAGE:f1707c1d7585ad06_4_5]]
[[IMAGE:f1707c1d7585ad06_4_6]]
A published solution is not available for this question yet.
Question 68 MCQ · 1.0 marks
**SEARCH**
[[IMAGE:f1707c1d7585ad06_2_1]]
Based on the above data, answer the given subquestions.
Select the correct statement(s) 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 69 SHORT_TEXT · 1.0 marks
**TSP Branch-and-Bound**
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and
so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the
optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique
reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties.
When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the
information gleaned from the search tree.
[[IMAGE:f1707c1d7585ad06_5_7]]
Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes (2nd to 5th node) that
are refined by the TSP Branch-and-Bound algorithm. Enter the nodes (node reference numbers) in
the order they are refined.
Enter a comma separated list of node reference numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: a9,b9,c9,d9**
A published solution is not available for this question yet.
Question 70 SHORT_TEXT · 1.0 marks
**TSP Branch-and-Bound**
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and
so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the
optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique
reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties.
When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the
information gleaned from the search tree.
[[IMAGE:f1707c1d7585ad06_5_7]]
Which node represents the optimal tour? Enter the node reference number in the text box, or
enter NIL if it is not possible to determine the optimal tour.
Enter a node reference number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: a9**
A published solution is not available for this question yet.
Question 71 SHORT_TEXT · 1.0 marks
**TSP Branch-and-Bound**
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and
so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the
optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique
reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties.
When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the
information gleaned from the search tree.
[[IMAGE:f1707c1d7585ad06_5_7]]
What is the cost of the optimal tour? Enter the cost of the optimal tour in the text box, or enter NIL
if it is not possible to determine the optimal tour.
Enter an integer.
NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 42**
A published solution is not available for this question yet.
Question 72 SHORT_TEXT · 1.0 marks
**TSP Branch-and-Bound**
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and
so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the
optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique
reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties.
When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the
information gleaned from the search tree.
[[IMAGE:f1707c1d7585ad06_5_7]]
Determine the number of cities in the TSP instance. Enter the number of cities in the text box, or
enter NIL if it is not possible to determine the number of cities.
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 42**
A published solution is not available for this question yet.
Question 73 SHORT_TEXT · 1.0 marks
**TSP Branch-and-Bound**
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and
so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the
optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique
reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties.
When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the
information gleaned from the search tree.
[[IMAGE:f1707c1d7585ad06_5_7]]
Start from city A, what is the path representation of the optimal tour? Enter the path
representation in the text box, or enter NIL if it is not possible to determine the optimal tour.
Enter a comma separated list of cities (city labels).
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: A,B,C**
A published solution is not available for this question yet.
Question 74 MSQ · 1.0 marks
**GAMES**
The figure shows a game tree with evaluation function values at the leaf nodes.
The leaf nodes are labeled from A to K.
Use these labels to enter a leaf node or a list of leaf nodes in short answers (textbox).
**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:f1707c1d7585ad06_8_8]]
Based on the above data, answer the given subquestions.
Which of the following is a strategy for the MAX player?
D,E,F,G
H,I,J,K
D,E,F
H,I
A published solution is not available for this question yet.
Question 75 SHORT_TEXT · 1.0 marks
**GAMES**
The figure shows a game tree with evaluation function values at the leaf nodes.
The leaf nodes are labeled from A to K.
Use these labels to enter a leaf node or a list of leaf nodes in short answers (textbox).
**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:f1707c1d7585ad06_8_8]]
Based on the above data, answer the given subquestions.
List the leaf nodes in the best strategy for MAX. Enter the node labels in alphabetical order.
Enter a comma separated list of node labels 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 76 SHORT_TEXT · 1.0 marks
**GAMES**
The figure shows a game tree with evaluation function values at the leaf nodes.
The leaf nodes are labeled from A to K.
Use these labels to enter a leaf node or a list of leaf nodes in short answers (textbox).
**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:f1707c1d7585ad06_8_8]]
Based on the above data, answer the given subquestions.
List the leaf nodes inspected by Alpha-Beta algorithm.
Enter a comma separated list of node labels 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 77 SHORT_TEXT · 1.0 marks
**GAMES**
The figure shows a game tree with evaluation function values at the leaf nodes.
The leaf nodes are labeled from A to K.
Use these labels to enter a leaf node or a list of leaf nodes in short answers (textbox).
**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:f1707c1d7585ad06_8_8]]
Based on the above data, answer the given subquestions.
List the leaf nodes SOLVED by SSS*.
Enter a comma separated list of node labels 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 78 SHORT_TEXT · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or
more smaller problems. Nodes are uniquely identified by labels (S, A, B, …). The number in each
node is the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a
primitive node is added to the graph by its parent when the parent is expanded, and the primitive
node is labeled as SOLVED and it will not be expanded subsequently.
**The cost of each edge is 10 units.**
**Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels.
**Tie-breaker 2:** For AND nodes, expand the unsolved branch with the highest cost
[[IMAGE:f1707c1d7585ad06_11_9]]
[[IMAGE:f1707c1d7585ad06_11_10]]
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: X,Y,Z**
A published solution is not available for this question yet.
Question 79 SHORT_TEXT · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or
more smaller problems. Nodes are uniquely identified by labels (S, A, B, …). The number in each
node is the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a
primitive node is added to the graph by its parent when the parent is expanded, and the primitive
node is labeled as SOLVED and it will not be expanded subsequently.
**The cost of each edge is 10 units.**
**Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels.
**Tie-breaker 2:** For AND nodes, expand the unsolved branch with the highest cost
[[IMAGE:f1707c1d7585ad06_11_9]]
Determine the value of the start node S after each node is expanded. Enter the value of S after
each node is expanded.
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 80 NAT · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or
more smaller problems. Nodes are uniquely identified by labels (S, A, B, …). The number in each
node is the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a
primitive node is added to the graph by its parent when the parent is expanded, and the primitive
node is labeled as SOLVED and it will not be expanded subsequently.
**The cost of each edge is 10 units.**
**Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels.
**Tie-breaker 2:** For AND nodes, expand the unsolved branch with the highest cost
[[IMAGE:f1707c1d7585ad06_11_9]]
What is the final value of the start node S computed by AO*?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: 17**
A published solution is not available for this question yet.
Question 81 MSQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for a rule based system to identify engines, turbines and motors is shown in the figure.
BoM refers to Bill-of-Materials, which is a list of parts and their quantities needed for assembling a
machine.
The nodes in the network are uniquely identified by labels: A1,A2,... for Alpha nodes; B1,B2,... for
beta nodes; R1,R2,... for rules.
[[IMAGE:f1707c1d7585ad06_13_11]]
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 elements in the ancestor Alpha nodes.
[[IMAGE:f1707c1d7585ad06_13_12]]
The sub-questions are based on the first Match-Resolve-Execute cycle. Determine the locations of
the WMEs and compute the conflict set, then answer the sub-questions.
Which of the following rule-data tuples occur in the conflict set?
(Diesel-Engine, 101, 107)
(Petrol-Engine, 107, 102)
(Engine, 107)
(Single-Phase-Motor, 105, 104)
(Motor, 104)
(Motor, 106)
A published solution is not available for this question yet.
Question 82 MCQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for a rule based system to identify engines, turbines and motors is shown in the figure.
BoM refers to Bill-of-Materials, which is a list of parts and their quantities needed for assembling a
machine.
The nodes in the network are uniquely identified by labels: A1,A2,... for Alpha nodes; B1,B2,... for
beta nodes; R1,R2,... for rules.
[[IMAGE:f1707c1d7585ad06_13_11]]
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 elements in the ancestor Alpha nodes.
[[IMAGE:f1707c1d7585ad06_13_12]]
The sub-questions are based on the first Match-Resolve-Execute cycle. Determine the locations of
the WMEs and compute the conflict set, 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?
(Diesel-Engine, 101, 107)
(Petrol-Engine, 107, 102)
(Engine, 107)
(Single-Phase-Motor, 105, 104)
(Motor, 104)
(Motor, 106)
A published solution is not available for this question yet.
Question 83 MCQ · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for a rule based system to identify engines, turbines and motors is shown in the figure.
BoM refers to Bill-of-Materials, which is a list of parts and their quantities needed for assembling a
machine.
The nodes in the network are uniquely identified by labels: A1,A2,... for Alpha nodes; B1,B2,... for
beta nodes; R1,R2,... for rules.
[[IMAGE:f1707c1d7585ad06_13_11]]
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 elements in the ancestor Alpha nodes.
[[IMAGE:f1707c1d7585ad06_13_12]]
The sub-questions are based on the first Match-Resolve-Execute cycle. Determine the locations of
the WMEs and compute the conflict set, then answer the sub-questions.
If the Inference Engine uses **Recency** for conflict resolution which rule-data tuple will fire in the
first round?
(Diesel-Engine, 101, 107)
(Petrol-Engine, 107, 102)
(Engine, 107)
(Single-Phase-Motor, 105, 104)
(Motor, 104)
(Motor, 106)
A published solution is not available for this question yet.
Question 84 MSQ · 1.0 marks
**AUTOMATED PLANNING**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:f1707c1d7585ad06_15_13]]
[[IMAGE:f1707c1d7585ad06_16_14]]
Based on the above data, answer the given subquestions.
Which of the following are **applicable** actions in the start state?
Putdown(D)
Unstack(D, B)
Unstack(C, A)
Pickup(E)
Pickup(A)
Stack(B, A)
Stack(A, C)
A published solution is not available for this question yet.
Question 85 MSQ · 1.0 marks
**AUTOMATED PLANNING**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:f1707c1d7585ad06_15_13]]
[[IMAGE:f1707c1d7585ad06_16_14]]
Based on the above data, answer the given subquestions.
Which of the following are **relevant** actions in the goal state?
Putdown(D)
Unstack(D, B)
Unstack(C, A)
Pickup(E)
Pickup(A)
Stack(B, A)
Stack(A , C)
A published solution is not available for this question yet.
Question 86 MSQ · 1.0 marks
**AUTOMATED PLANNING**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:f1707c1d7585ad06_15_13]]
[[IMAGE:f1707c1d7585ad06_16_14]]
Based on the above data, answer the given subquestions.
In the planning graph, which of the following are mutex action pairs in Layer 1?
Unstack(D, B), Pickup(E)
Unstack(D, B), Unstack(C, A)
Pickup(E), Stack(B, A)
Pickup(E), Stack(A, C)
A published solution is not available for this question yet.
Question 87 MSQ · 1.0 marks
**AUTOMATED PLANNING**
The domain description of a Blocks World with a single one-armed robot is given below.
[[IMAGE:f1707c1d7585ad06_15_13]]
[[IMAGE:f1707c1d7585ad06_16_14]]
Based on the above data, answer the given subquestions.
In the planning graph, which of the following are mutex proposition pairs in Layer 1?
clear(B), holding(C)
clear(B), clear(A)
clear(E), on(D, B)
clear(E), holding(D)
A published solution is not available for this question yet.
Question 88 MCQ · 1.0 marks
**CONSTRAINT SATISFACTION**
[[IMAGE:f1707c1d7585ad06_18_15]]
Is the given CSP arc consistent?
Yes
No
Cannot be determined
A published solution is not available for this question yet.
Question 89 MCQ · 1.0 marks
**CONSTRAINT SATISFACTION**
[[IMAGE:f1707c1d7585ad06_18_15]]
Is the given CSP path consistent?
No
Yes
Cannot be determined
A published solution is not available for this question yet.
Question 90 SHORT_TEXT · 1.0 marks
**CONSTRAINT SATISFACTION**
[[IMAGE:f1707c1d7585ad06_18_15]]
Does the given CSP have a solution? Enter the solution for regions A,B,C as a comma separated list
of colours. Enter NIL if there is no solution.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: r,b,r**
A published solution is not available for this question yet.