AI: Search Methods for Problem Solving End Term: 10 May 2026, Set 1 (January 2026 term)

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.

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 Answers Case Sensitive : No

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.

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 Answers Case Sensitive : No

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?

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?

SEARCH ALGORITHMS Answer the given subquestions.

If w is set to zero then wA* algorithm will __________ .

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.

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 Answers Case Sensitive : No

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.

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.

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.

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 Answers Case Sensitive : No

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.

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 Answers Case Sensitive : No

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.

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 Answers Case Sensitive : No

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.

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 Answers Case Sensitive : No

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.

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 Answers Case Sensitive : No

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.

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 Answers Case Sensitive : No

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.

Use AO* algorithm to solve S, then answer the sub-questions.

What can you conclude about the given AND-OR decomposition?

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.

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.

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?

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.

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.

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?

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.

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.

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?

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?

AUTOMATED PLANNING 1 Answer the given subquestions.

In planning graphs constructed by GraphPlan, actions a and b in layer n are mutex __________ .

AUTOMATED PLANNING 1 Answer the given subquestions.

In planning graphs constructed by GraphPlan, which of the following are true?

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

Based on the above data, answer the given subquestions.

Which of the following are applicable actions for FSSP?

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

Based on the above data, answer the given subquestions.

Which of the following are relevant actions for BSSP?

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

Based on the above data, answer the given subquestions.

In the planning graph, which of the following are mutex action pairs in layer 1?

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

Based on the above data, answer the given subquestions.

In the planning graph, which of the following are mutex proposition pairs in layer 1?

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

Based on the above data, answer the given subquestions.

In the planning graph, which of the following are applicable actions in layer 2?

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

Based on the above data, answer the given subquestions.

For the given planning problem, does a plan exist?

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

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 Answers Case Sensitive : No

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C where the domains and constraints are:

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?

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C where the domains and constraints are:

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?

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C where the domains and constraints are:

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?

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C where the domains and constraints are:

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.

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C where the domains and constraints are:

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 Answers Case Sensitive : No

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.

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.

SEARCH ALGORITHMS Answer the given subquestions.

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.

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.

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.

Run SSS* algorithm on the game tree, then answer the sub-questions.

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.

Use AO* algorithm to solve S, then answer the sub-questions.

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.

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.

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.

AUTOMATED PLANNING 1 Answer the given subquestions.

AUTOMATED PLANNING 2 The domain description of a Blocks World with a single one-armed robot is given below.

Consider the following planning problem.

Based on the above data, answer the given subquestions.

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C where the domains and constraints are:

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.