cs3003_2026T2_ET_FN.pdf
AI: Search Methods for Problem Solving · End Term · May 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:963e2e7fd70bbf2a_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**
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion
trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use
unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit
squares each 1m x 1m.
The grid (intersection points and unit sides) forms a graph (nodes and undirected edges).
Start node (S) is at the center of the plane.
Goal node (G) is at the north east corner of the plane.
MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South].
Take h(X) as the square of the Euclidean distance.
[[IMAGE:963e2e7fd70bbf2a_3_3]]
Answer the sub-questions based on the above problem using algorithms presented in the
lectures.
How many distinct TSP tours can be constructed by traversing only along the edges in the graph?
Give a precise and concise answer.
A published solution is not available for this question yet.
Question 4 SHORT_TEXT · 1.0 marks
**SEARCH**
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion
trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use
unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit
squares each 1m x 1m.
The grid (intersection points and unit sides) forms a graph (nodes and undirected edges).
Start node (S) is at the center of the plane.
Goal node (G) is at the north east corner of the plane.
MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South].
Take h(X) as the square of the Euclidean distance.
[[IMAGE:963e2e7fd70bbf2a_3_3]]
Answer the sub-questions based on the above problem using algorithms presented in the
lectures.
What will be the depth of the shallowest leaf node in the Breadth First search tree when GoalTest
returns true? Give a precise and concise answer. (Note: nodes already seen are not reopened.)
A published solution is not available for this question yet.
Question 5 SHORT_TEXT · 1.0 marks
**SEARCH**
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion
trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use
unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit
squares each 1m x 1m.
The grid (intersection points and unit sides) forms a graph (nodes and undirected edges).
Start node (S) is at the center of the plane.
Goal node (G) is at the north east corner of the plane.
MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South].
Take h(X) as the square of the Euclidean distance.
[[IMAGE:963e2e7fd70bbf2a_3_3]]
Answer the sub-questions based on the above problem using algorithms presented in the
lectures.
What will be the cost of the path found by the A* algorithm? Use Big-O notation.
A published solution is not available for this question yet.
Question 6 MCQ · 1.0 marks
**SEARCH**
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion
trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use
unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit
squares each 1m x 1m.
The grid (intersection points and unit sides) forms a graph (nodes and undirected edges).
Start node (S) is at the center of the plane.
Goal node (G) is at the north east corner of the plane.
MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South].
Take h(X) as the square of the Euclidean distance.
[[IMAGE:963e2e7fd70bbf2a_3_3]]
Answer the sub-questions based on the above problem using algorithms presented in the
lectures.
The heuristic is __________ .
admissible
inadmissible
A published solution is not available for this question yet.
Question 7 SHORT_TEXT · 1.0 marks
**SEARCH**
A finite 2D plane of square shape has each side of length (D) exactly equal to 100 trillion trillion
trillion trillion lightyears rounded-down to the nearest meter that is an EVEN NUMBER. Use
unlimited-precision arithmetic for all operations. The plane is covered end to end by a grid of unit
squares each 1m x 1m.
The grid (intersection points and unit sides) forms a graph (nodes and undirected edges).
Start node (S) is at the center of the plane.
Goal node (G) is at the north east corner of the plane.
MoveGen(X) returns neighbours in counterclockwise order [East, North, West, South].
Take h(X) as the square of the Euclidean distance.
[[IMAGE:963e2e7fd70bbf2a_3_3]]
Answer the sub-questions based on the above problem using algorithms presented in the
lectures.
What is the full form of DCBSS?
A published solution is not available for this question yet.
Question 8 SHORT_TEXT · 1.0 marks
**GAMES**
Consider any k-ply game tree having MAX as root, where k is an EVEN number, and each player
having exactly 2 moves at all levels except the leaf level, and the evals of the leaf nodes (from left
to right) form a sequence starting from zero, incremented by 1.
The minimax value is __________ . Give a precise and concise answer.
A published solution is not available for this question yet.
Question 9 SHORT_TEXT · 1.0 marks
Let the AlphaBeta algorithm process the subtree with alpha=60 and beta=80, identify the leaf
node(s) explored by the algorithm, and enter those nodes in the text box.
[[IMAGE:963e2e7fd70bbf2a_6_4]]
Enter a comma separated list of node labels.
NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS.
A published solution is not available for this question yet.
Question 10 SHORT_TEXT · 1.0 marks
Let the SSS* algorithm process the subtree with h=20, identify the leaf node(s) that never made it
to the queue, and enter those nodes in the text box. (Note: when nodes have the same h-value
break ties in Depth-First search order.)
[[IMAGE:963e2e7fd70bbf2a_7_5]]
Enter a comma separated list of node labels.
NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS.
A published solution is not available for this question yet.
Question 11 SHORT_TEXT · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR decomposition of problem S into subproblems. The nodes are
uniquely identified by labels (S, A, B, C, …). Each node displays its heuristic cost, but primitive
nodes (double border) display the actual cost. Primitive nodes attain SOLVED status when their
parent is expanded, so primitive nodes are 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:963e2e7fd70bbf2a_8_6]]
Use AO* algorithm to solve S, then answer the sub-questions.
For each node expanded by AO* algorithm, determine the value assigned/propagated to the start
node S. Enter the values of S in the time order, in the order it was updated.
Enter a comma separated list of integers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
A published solution is not available for this question yet.
Question 12 MCQ · 1.0 marks
**PROBLEM DECOMPOSITION**
The figure shows an AND-OR decomposition of problem S into subproblems. The nodes are
uniquely identified by labels (S, A, B, C, …). Each node displays its heuristic cost, but primitive
nodes (double border) display the actual cost. Primitive nodes attain SOLVED status when their
parent is expanded, so primitive nodes are 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:963e2e7fd70bbf2a_8_6]]
Use AO* algorithm to solve S, then answer the sub-questions.
Did AO* return the optimal solution for the given problem?
Yes
No
Cannot be determined
A published solution is not available for this question yet.
Question 13 SHORT_TEXT · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for classification of properties is shown in the figure. The labels A1, A2, A3, ..., A10, A11,
A12, A13, ..., and B1, B2, B3, B4 uniquely identify nodes in the network. When required, use the
above label ordering to **break ties** and to enter short answers.
[[IMAGE:963e2e7fd70bbf2a_10_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:963e2e7fd70bbf2a_10_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 sub-questions.
Identify the rule-data tuples in the conflict-set. Enter one rule data tuple from the conflict-set as a
comma separated list in the text box: rule name followed by timestamps in **ascending order**.
NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: R9,201,202,203,204**
A published solution is not available for this question yet.
Question 14 SHORT_TEXT · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for classification of properties is shown in the figure. The labels A1, A2, A3, ..., A10, A11,
A12, A13, ..., and B1, B2, B3, B4 uniquely identify nodes in the network. When required, use the
above label ordering to **break ties** and to enter short answers.
[[IMAGE:963e2e7fd70bbf2a_10_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:963e2e7fd70bbf2a_10_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 sub-questions.
If the Inference Engine uses **Specificity** as the conflict resolution strategy then which rule-data
tuple(s) will qualify? Enter one rule data tuple as a comma separated list in the text box: rule name
followed by timestamps in **ascending order**.
NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: R9,201,202,203,204**
A published solution is not available for this question yet.
Question 15 SHORT_TEXT · 1.0 marks
**RULE BASED EXPERT SYSTEMS**
A Rete Net for classification of properties is shown in the figure. The labels A1, A2, A3, ..., A10, A11,
A12, A13, ..., and B1, B2, B3, B4 uniquely identify nodes in the network. When required, use the
above label ordering to **break ties** and to enter short answers.
[[IMAGE:963e2e7fd70bbf2a_10_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:963e2e7fd70bbf2a_10_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 sub-questions.
If the Inference Engine uses **Recency** as the conflict resolution strategy then which rule-data
tuple(s) will qualify? Enter one rule data tuple as a comma separated list in the text box: rule name
followed by timestamps in **ascending order**.
NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS.
**Answer format: R9,201,202,203,204**
A published solution is not available for this question yet.
Question 16 SHORT_TEXT · 1.0 marks
**GOAL STACK PLANNING**
The domain description of Blocks World with a single one-armed robot is given below.
[[IMAGE:963e2e7fd70bbf2a_13_9]]
[[IMAGE:963e2e7fd70bbf2a_13_10]]
**Tie-breaker 1:** Treat the goal description, preconditions and effects as lists that are accessed from
left to right.
**Tie-breaker 2:** When list elements are pushed one by one to a stack, the last element in the list will
be at the top of the stack.
The GSP stack shown below grows downwards, so the last line is the top of the stack, it shows the
first three actions pushed and no other action has been pushed/popped yet, and the plan is
currently empty.
[[IMAGE:963e2e7fd70bbf2a_14_11]]
Analyze the stack, determine the three actions and then answer the sub-questions.
After ACTION-2 is pushed to the stack, determine the propositions in the current state that caused
ACTION-3 to be pushed to the stack. Enter those propositions (in sorted order) in the text box.
Enter NIL or enter a comma separated list of propositions in alphabetical order.
NO SPACES, TABS OR EXTRANEOUS CHARACTERS.
**Answer format: armEmpty,clear(X),holding(X),on(X,Y),onTable(X)**
A published solution is not available for this question yet.
Question 17 SHORT_TEXT · 1.0 marks
**GOAL STACK PLANNING**
The domain description of Blocks World with a single one-armed robot is given below.
[[IMAGE:963e2e7fd70bbf2a_13_9]]
[[IMAGE:963e2e7fd70bbf2a_13_10]]
**Tie-breaker 1:** Treat the goal description, preconditions and effects as lists that are accessed from
left to right.
**Tie-breaker 2:** When list elements are pushed one by one to a stack, the last element in the list will
be at the top of the stack.
The GSP stack shown below grows downwards, so the last line is the top of the stack, it shows the
first three actions pushed and no other action has been pushed/popped yet, and the plan is
currently empty.
[[IMAGE:963e2e7fd70bbf2a_14_11]]
Analyze the stack, determine the three actions and then answer the sub-questions.
Determine the proposition(s) in the current state that will trigger the popping of ACTION-3 and
ACTION-2 in that order. Enter those propositions (in sorted order) in the text box.
Enter NIL or enter a comma separated list of propositions in alphabetical order.
NO SPACES, TABS OR EXTRANEOUS CHARACTERS.
**Answer format: armEmpty,clear(X),holding(X),on(X,Y),onTable(X)**
A published solution is not available for this question yet.
Question 18 SHORT_TEXT · 1.0 marks
**GRAPH-PLAN**
The domain description of Blocks World with a single one-armed robot is given below.
[[IMAGE:963e2e7fd70bbf2a_16_12]]
[[IMAGE:963e2e7fd70bbf2a_16_13]]
The GraphPlan algorithm is in flight constructing the planning graph (P0, A1, P1, A2, P2, ...); the
propositions and mutex pairs in k-th propositional layer (Pk) are provided.
[[IMAGE:963e2e7fd70bbf2a_17_14]]
Based on the above data, answer the given subquestions.
Find the applicable actions in layer k+1? Enter one of the applicable actions in the text box.
A published solution is not available for this question yet.
Question 19 SHORT_TEXT · 1.0 marks
**GRAPH-PLAN**
The domain description of Blocks World with a single one-armed robot is given below.
[[IMAGE:963e2e7fd70bbf2a_16_12]]
[[IMAGE:963e2e7fd70bbf2a_16_13]]
The GraphPlan algorithm is in flight constructing the planning graph (P0, A1, P1, A2, P2, ...); the
propositions and mutex pairs in k-th propositional layer (Pk) are provided.
[[IMAGE:963e2e7fd70bbf2a_17_14]]
Based on the above data, answer the given subquestions.
Find the new propositions that will be added to layer k+1? Enter one of the new propositions in the
text box.
A published solution is not available for this question yet.
Question 20 SHORT_TEXT · 1.0 marks
**AUTOMATED PLANNING**
Consider a planning problem in the multiarm blocks-world domain, with 2^(2^k) blocks and 2^k
arms, for k greater than 5, where multiple empty arms cannot simultaneously pick up
(respectively, unstack) the same block, and multiple arms holding different blocks cannot
simultaneously stack on the same block, but multiple arms can simultaneously perform
independent tasks.
Extend the operators from single-arm case to multiarm case by adding an arm parameter. In the
multiarm case, Pickup(n,X) and Unstack(n,X,Y) actions will delete clear(X), and Putdown(n,X) and
Stack(n,X,Y) actions will add clear(X).
The start state which is a valid state is not given to us.
The goal state has all the blocks as a single tower resting on the table.
Compute the worst case makespan. Give a precise and concise answer.
A published solution is not available for this question yet.
Question 21 SUBJECTIVE · 1.0 marks
Given a planning problem, under what conditions will GraphPlan report that a plan does not exist?
Give a precise and concise answer.
**NOTE:** Your answer should not exceed 64 words.
A published solution is not available for this question yet.
Question 22 MCQ · 1.0 marks
Can GraphPlan solve the Sussman anomaly?
Yes
No
It cannot because GraphPlan is not allowed to delete propositions in the new
layers.
It can, but GraphPlan will take time proportional to the age of the universe.
A published solution is not available for this question yet.
Question 23 MCQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C, where the domains and constraints are:
[[IMAGE:963e2e7fd70bbf2a_20_15]]
where, mod(n,d) returns the remainder after dividing integer n by integer d, for example,
mod(8,3)=2, mod(12,3)=0, mod(16,3)=1.
Compute the three constraints such that the values are from respective domains, draw the
constraint graph and matching-diagram, then answer the sub-questions.
Is the given CSP network 3-consistent?
Yes
No
Cannot be determined because 3-consistency requires a 4th variable.
A published solution is not available for this question yet.
Question 24 NAT · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C, where the domains and constraints are:
[[IMAGE:963e2e7fd70bbf2a_20_15]]
where, mod(n,d) returns the remainder after dividing integer n by integer d, for example,
mod(8,3)=2, mod(12,3)=0, mod(16,3)=1.
Compute the three constraints such that the values are from respective domains, draw the
constraint graph and matching-diagram, then answer the sub-questions.
Count the number of solutions to the given CSP. Enter the count in the text box.
Enter an integer.
A published solution is not available for this question yet.
Question 25 MSQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C, where the domains and constraints are:
[[IMAGE:963e2e7fd70bbf2a_20_15]]
where, mod(n,d) returns the remainder after dividing integer n by integer d, for example,
mod(8,3)=2, mod(12,3)=0, mod(16,3)=1.
Compute the three constraints such that the values are from respective domains, draw the
constraint graph and matching-diagram, then answer the sub-questions.
In the given CSP, constraints are defined between every pair of variables. But in general, for Binary
CSPs of n variables, if the number of binary constraints is less than nC2 then __________ .
that network can be solved
that network cannot be solved
that network may or may not have a solution
that network will always have a solution
that network will never have a solution
A published solution is not available for this question yet.
Question 26 SUBJECTIVE · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C, where the domains and constraints are:
[[IMAGE:963e2e7fd70bbf2a_20_15]]
where, mod(n,d) returns the remainder after dividing integer n by integer d, for example,
mod(8,3)=2, mod(12,3)=0, mod(16,3)=1.
Compute the three constraints such that the values are from respective domains, draw the
constraint graph and matching-diagram, then answer the sub-questions.
When is a CSP network considered to be i-Consistent? Give a precise and concise answer.
**NOTE:** Your answer should not exceed 64 words.
A published solution is not available for this question yet.
Question 27 MSQ · 1.0 marks
**CONSTRAINT SATISFACTION**
Consider a CSP over 3 variables A, B, C, where the domains and constraints are:
[[IMAGE:963e2e7fd70bbf2a_20_15]]
where, mod(n,d) returns the remainder after dividing integer n by integer d, for example,
mod(8,3)=2, mod(12,3)=0, mod(16,3)=1.
Compute the three constraints such that the values are from respective domains, draw the
constraint graph and matching-diagram, then answer the sub-questions.
The Waltz Algorithm __________
can process 2D drawings showing cracks and shadows
can process vertices with more than 3 edges
cannot process objects with cracks and shadows
can only process trihedral objects without cracks or shadows
can detect and remove cracks and shadows from the 2D line drawing
runs in time proportional to log(Edge Count) + log(Vertex Count)
A published solution is not available for this question yet.