BTechibtechi.in
Loading Loading
Free IIT Madras BS notes, PYQs and mock tests at btechi.in

AI Search · All 2025 papers

99 questions · 99 marks · 4 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

All 2025 papers

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MCQ: Exactly 1 option is correct. Negative marking applies.
MSQ: One or more options correct. Select all to score.
NAT: Numerical response. No negative marking.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

Quiz 1 · 26 Oct 2025 (AN)Quiz 1

Read the passage below, then answer Q1–Q3
STATE SPACE
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide one position either horizontally or vertically into the adjacent empty spot, effectively swapping the tile and the adjacent empty spot. A tile cannot slide diagonally.
Begin from the start state and build the state space graph by generating valid moves, call it Graph- 1230, use this graph to answer the sub-questions.
Q1MSQ1 Mark·Choose all correct options
Key ↓
1. AState A
2. BState B
3. CState C
4. DState D
Q2MSQ1 Mark·Choose all correct options
Key ↓
Select the statements that are true about Graph-1230.
1. AEvery move is reversible.
2. BEvery state has a path to every other state.
3. CSome states have more than two neighbours.
4. DEvery state has exactly two neighbours.
5. EEvery state has exactly one neighbour.
Q3MCQ1 Mark·Choose one option
Key ↓
The number of unique states in Graph-1230 is __________ .
1. Aless than 8
2. Bequal to 8
3. Cmore than 8
Read the passage below, then answer Q4–Q11
SEARCH
The MoveGen function and the heuristic function for a state space is provided below. Take S as the start node and G as the goal node.
When required use alphabetical order to break ties.
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
Q4Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Depth First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q5Short answer1 Mark·Write the answer
Key ↓
What is the path found by Depth First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q6Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Breadth First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q7Short answer1 Mark·Write the answer
Key ↓
What is the path found by Breadth First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q8Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Best First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q9Short answer1 Mark·Write the answer
Asked 3 times Key ↓
What is the path found by Best First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q10Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Hill Climbing. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q11Short answer1 Mark·Write the answer
Key ↓
What is the path found by Hill Climbing? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Read the passage below, then answer Q12–Q15
Genetic Algorithm
Answer the given subquestions.
Q12MCQ1 Mark·Choose one option
Key ↓
Convert the path representation A,C,K,F,B,H,G,I,D,L,E,J to ordinal representation. Use A,B,C,...,L as the reference (index) sequence.
1. A1,2,9,4,1,4,3,3,1,3,1,1
2. B9,4,10,4,2,1,1,5,3,3,1,1
3. C1,2,9,8,1,3,3,4,1,3,1,1
4. D3,10,8,3,2,2,5,1,3,3,2,1
Q13MSQ1 Mark·Choose all correct options
Key ↓
Path representations of two tours are given below. Generate offspring using Cycle Crossover. P1: I,D,L,E,J,A,C,K,F,B,H,G P2: C,K,I,D,B,E,J,A,H,L,G,F Select the child tours.
1. AI,K,L,D,J,E,C,A,F,B,H,G
2. BC,D,I,E,B,A,J,K,H,L,G,F
3. CI,D,L,K,B,A,E,H,C,J,F,G
4. DA,L,I,E,J,D,C,K,H,F,G,B
Q14MCQ1 Mark·Choose one option
Key ↓
Single-point crossover can be used with __________ .
1. AAdjacency Representation.
2. BPath Representation
3. COrdinal Representation
4. DAll of these
Q15NAT1 Mark·Write the number
Key ↓
For the case of 3-edge exchange, how many child tours are possible? Enter the number of child tours in the text box. (Assume that no pair of edges from the selected 3 edges share any city in common.) Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: 17
Your answer:
Read the passage below, then answer Q16–Q20
TSP
Use the distance matrix to construct TSP tours.
Based on the above data, answer the given subquestions.
Q16Short answer1 Mark·Write the answer
Key ↓
Use “A” as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is __________ . Enter the path representation of the tour, starting from “A” and tracing the cities as selected by the Nearest Neighbour Heuristic. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z
Your answer:
Q17Short answer1 Mark·Write the answer
Key ↓
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Identify the new edge added in the first merge operation. Enter the new edge and its savings. Enter an edge XY and an integer as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: XY,17
Your answer:
Q18Short answer1 Mark·Write the answer
Key ↓
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Enter the path representation of the Savings tour, starting from “A”. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z
Your answer:
Q19NAT1 Mark·Write the number
Key ↓
What is the cost of the tour generated by Savings Heuristic? Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: 17
Your answer:
Q20MSQ1 Mark·Choose all correct options
Key ↓
Consider N cities in a Euclidean plane and use the Euclidean Distance as the distance measure. For each city, take that city as the fulcrum (base) city and compute its Savings tour. From the resulting N Savings tours, select the cheapest tour. What can you conclude about the above procedure?
1. AThis procedure can be used to compute the optimal TSP tour.
2. BThis procedure is not suitable for computing the optimal TSP tour.
3. CThis procedure may not always terminate.
4. DThis procedure will always terminate.

End Term · 31 Aug 2025 (FN)End Term

Read the passage below, then answer Q21–Q25
SEARCH
Based on the above data, answer the given subquestions.
Q21Short answer1 Mark·Write the answer
Asked 3 times Key ↓
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
Your answer:
Q22Short answer1 Mark·Write the answer
Asked 2 times Key ↓
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: S,X,Y,Z
Your answer:
Q23Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q24MCQ1 Mark·Choose one option
Asked 2 times Key ↓
For the given map, which algorithm finds the shortest path from S to G?
1. A
2. B
3. C
4. D
Q25MCQ1 Mark·Choose one option
Asked 3 times Key ↓
Select the correct statement(s) about the given graph.
1. AHeuristic is admissible.
2. BHeuristic is not admissible.
3. CHeuristic is admissible in some cases and not admissible in other cases.
4. DThere is not enough information to determine admissibility.
Read the passage below, then answer Q26–Q30
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.
Q26Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q27Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q28Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q29Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q30Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Read the passage below, then answer Q31–Q34
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.
Based on the above data, answer the given subquestions.
Q31MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
Which of the following is a strategy for the MAX player?
1. AD,E,F,G
2. BH,I,J,K
3. CD,E,F
4. DH,I
Q32Short answer1 Mark·Write the answer
Asked 3 times Key ↓
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
Your answer:
Q33Short answer1 Mark·Write the answer
Asked 3 times Key ↓
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
Your answer:
Q34Short answer1 Mark·Write the answer
Asked 3 times Key ↓
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
Your answer:
Read the passage below, then answer Q35–Q37
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
Q35Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: X,Y,Z
Your answer:
Q36Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q37NAT1 Mark·Write the number
Asked 2 times Key ↓
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
Your answer:
Read the passage below, then answer Q38–Q40
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.
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.
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.
Q38MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
Which of the following rule-data tuples occur in the conflict set?
1. A(Diesel-Engine, 101, 107)
2. B(Petrol-Engine, 107, 102)
3. C(Engine, 107)
4. D(Single-Phase-Motor, 105, 104)
5. E(Motor, 104)
6. F(Motor, 106)
Q39MCQ1 Mark·Choose one option
Asked 2 times Key ↓
If the Inference Engine uses Specificity for conflict resolution then which rule-data tuple will fire in the first round?
1. A(Diesel-Engine, 101, 107)
2. B(Petrol-Engine, 107, 102)
3. C(Engine, 107)
4. D(Single-Phase-Motor, 105, 104)
5. E(Motor, 104)
6. F(Motor, 106)
Q40MCQ1 Mark·Choose one option
Asked 2 times Key ↓
If the Inference Engine uses Recency for conflict resolution which rule-data tuple will fire in the first round?
1. A(Diesel-Engine, 101, 107)
2. B(Petrol-Engine, 107, 102)
3. C(Engine, 107)
4. D(Single-Phase-Motor, 105, 104)
5. E(Motor, 104)
6. F(Motor, 106)
Read the passage below, then answer Q41–Q44
AUTOMATED PLANNING
The domain description of a Blocks World with a single one-armed robot is given below.
Based on the above data, answer the given subquestions.
Q41MSQ1 Mark·Choose all correct options
Asked 3 times Key ↓
Which of the following are applicable actions in the start state?
1. APutdown(D)
2. BUnstack(D, B)
3. CUnstack(C, A)
4. DPickup(E)
5. EPickup(A)
6. FStack(B, A)
7. GStack(A, C)
Q42MSQ1 Mark·Choose all correct options
Asked 3 times Key ↓
Which of the following are relevant actions in the goal state?
1. APutdown(D)
2. BUnstack(D, B)
3. CUnstack(C, A)
4. DPickup(E)
5. EPickup(A)
6. FStack(B, A)
7. GStack(A , C)
Q43MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
In the planning graph, which of the following are mutex action pairs in Layer 1?
1. AUnstack(D, B), Pickup(E)
2. BUnstack(D, B), Unstack(C, A)
3. CPickup(E), Stack(B, A)
4. DPickup(E), Stack(A, C)
Q44MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
In the planning graph, which of the following are mutex proposition pairs in Layer 1?
1. Aclear(B), holding(C)
2. Bclear(B), clear(A)
3. Cclear(E), on(D, B)
4. Dclear(E), holding(D)
Read the passage below, then answer Q45–Q47
CONSTRAINT SATISFACTION
Q45MCQ1 Mark·Choose one option
Asked 2 times Key ↓
Is the given CSP arc consistent?
1. AYes
2. BNo
3. CCannot be determined
Q46MCQ1 Mark·Choose one option
Asked 2 times Key ↓
Is the given CSP path consistent?
1. ANo
2. BYes
3. CCannot be determined
Q47Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:

End Term · 31 Aug 2025 (AN)End Term

Read the passage below, then answer Q48–Q52
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.
Based on the above data, answer the given subquestions.
Q48Short answer1 Mark·Write the answer
Asked 3 times Key ↓
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
Your answer:
Q49Short answer1 Mark·Write the answer
Asked 2 times Key ↓
What is the path found by A* 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
Your answer:
Q50Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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,B,S,B,S,B,... NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: S,X,Y,Z
Your answer:
Q51MCQ1 Mark·Choose one option
Asked 2 times Key ↓
For the given map, which algorithm finds the shortest path from S to G?
1. A
2. B
3. C
4. D
Q52MCQ1 Mark·Choose one option
Asked 3 times Key ↓
Select the correct statement(s) about the given graph.
1. AHeuristic is admissible.
2. BHeuristic is not admissible.
3. CHeuristic is admissible in some cases and not admissible in other cases.
4. DThere is not enough information to determine admissibility.
Read the passage below, then answer Q53–Q57
TSP BnB
TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below. Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties. When required, use 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.
Q53Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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 BnB 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
Your answer:
Q54Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q55Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q56Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q57Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Read the passage below, then answer Q58–Q61
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.
Based on the above data, answer the given subquestions.
Q58MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
Which of the following is a strategy for the MAX player?
1. AI,K
2. BE,F,G
3. CE,F
4. DI,J,K
Q59Short answer1 Mark·Write the answer
Asked 3 times Key ↓
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
Your answer:
Q60Short answer1 Mark·Write the answer
Asked 3 times Key ↓
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
Your answer:
Q61Short answer1 Mark·Write the answer
Asked 3 times Key ↓
Your answer:
Read the passage below, then answer Q62–Q64
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 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, expand the unsolved branch with the highest cost.
Use AO* algorithm to solve S, then answer the subquestions.
Q62Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Your answer:
Q63Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q64NAT1 Mark·Write the number
Asked 2 times Key ↓
Your answer:
Read the passage below, then answer Q65–Q67
RULE BASED EXPERT SYSTEMS
A Rete Net for a rule based system to identify engines, turbines and motors is shown in the figure. Here, 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.
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.
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 given sub-questions.
Q65MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
Which of the following rule-data tuples occur in the conflict set?
1. A(Liquid-Fuel-Rocket, 102, 107)
2. B(Solid-Fuel-Rocket, 107, 101)
3. C(Windmill, 105, 104)
4. D(Generator, 104)
5. E(Generator, 106)
6. F(Rocket, 107)
Q66MCQ1 Mark·Choose one option
Asked 2 times Key ↓
If the Inference Engine uses Specificity for conflict resolution then which rule-data tuple will fire in the first round?
1. A(Liquid-Fuel-Rocket, 102, 107)
2. B(Solid-Fuel-Rocket, 107, 101)
3. C(Windmill, 105, 104)
4. D(Generator, 104)
5. E(Generator, 106)
6. F(Rocket, 107)
Q67MCQ1 Mark·Choose one option
Asked 2 times Key ↓
If the Inference Engine uses Recency for conflict resolution which rule-data tuple will fire in the first round?
1. A(Liquid-Fuel-Rocket, 102, 107)
2. B(Solid-Fuel-Rocket, 107, 101)
3. C(Windmill, 105, 104)
4. D(Generator, 104)
5. E(Generator, 106)
6. F(Rocket, 107)
Read the passage below, then answer Q68–Q71
AUTOMATED PLANNING
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.
Q68MSQ1 Mark·Choose all correct options
Asked 3 times Key ↓
Which of the following are applicable actions in the start state?
1. APutdown(D)
2. BUnstack(D,A)
3. CUnstack(E,B)
4. DPickup(C)
5. EPickup(A)
6. FStack(A,B)
7. GStack(B,C)
Q69MSQ1 Mark·Choose all correct options
Asked 3 times Key ↓
Which of the following are relevant actions in the goal state?
1. APutdown(D)
2. BUnstack(D,A)
3. CUnstack(E,B)
4. DPickup(C)
5. EPickup(A)
6. FStack(A,B)
7. GStack(B,C)
Q70MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
In the planning graph, which of the following are mutex action pairs in Layer 1?
1. AUnstack(D,A), Pickup(C)
2. BUnstack(D,A), Unstack(E,B)
3. CPickup(C), Stack(A,B)
4. DPickup(C), Stack(B,C)
Q71MSQ1 Mark·Choose all correct options
Asked 2 times Key ↓
In the planning graph, which of the following are mutex proposition pairs in Layer 1?
1. Aclear(A), holding(E)
2. Bclear(A), clear(B)
3. Cclear(C), on(D,A)
4. Dclear(C), holding(E)
Read the passage below, then answer Q72–Q74
CONSTRAINT SATISFACTION
Q72MCQ1 Mark·Choose one option
Asked 2 times Key ↓
Is the given CSP arc consistent?
1. AYes
2. BNo
3. CCannot be determined
Q73MCQ1 Mark·Choose one option
Asked 2 times Key ↓
Is the given CSP path consistent?
1. ANo
2. BYes
3. CCannot be determined
Q74Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:

Quiz 2 · 3 Aug 2025 (AN)Quiz 2

Read the passage below, then answer Q75–Q80
SEARCH
Figure shows an infinite state space with finite branching, where S is the start node and G is the goal node, and G is at the center of a unit circle, and the remaining nodes are on the unit circle. (Note: circular grid is shown by dashed lines which are not part of the state space.)
Take the radial distance as the heuristic value:
h(G)=0; h(S)=1; and h(Ak)=1, for all k in {1, 2, . . .}.
MoveGen returns neighbours in alphabetical order (A1,A2,..., G,S).
Tie-breaker: use alphabetical order to break ties.
Note: sum(1, a, a^2, a^3, ..., a^(n-1)) is given by ((1 - a^n)/(1 - a)).
Based on the above data, answer the given subquestions
Q75MCQ1 Mark·Choose one option
Key ↓
Does the Breadth First Search find the path to the goal?
1. AYes
2. BNo
3. CCannot be determined
Q76MCQ1 Mark·Choose one option
Key ↓
Does the Best First Search find the path to the goal?
1. AYes
2. BNo
3. CCannot be determined
Q77MCQ1 Mark·Choose one option
Key ↓
Does the Branch and Bound algorithm find the path to the goal?
1. AYes
2. BNo
3. CCannot be determined
Q78MCQ1 Mark·Choose one option
Key ↓
1. AYes
2. BNo
3. CCannot be determined
Q79MCQ1 Mark·Choose one option
Key ↓
1. AYes
2. BNo
3. CCannot be determined
Q80MCQ1 Mark·Choose one option
Asked 3 times Key ↓
Is the heuristic admissible in the given state space?
1. AYes
2. BNo
3. CCannot be determined
Read the passage below, then answer Q81–Q85
TSP
The distance matrix for 5 cities (A to E) and the sorted edge list is provided below.
For each city the distances to other cities are listed in ascending order.
For example, in row one, the distance from A to B is 30, A to C is 32 and so on.
The search tree traversed by TSP BnB shows four segments.
Identify the four segments xy, uv, rs, pq and then answer the given sub-questions.
Attention: A segment is a two-way edge between two cities. After adding/dropping a permanent segment, infer as many new permanent segments as possible before computing the lower bound.
Q81NAT1 Mark·Write the number
Key ↓
What is the lower bound on the cost of the tour as per the TSP BnB algorithm discussed in class? Enter a natural number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 17
Your answer:
Q82Short answer1 Mark·Write the answer
Key ↓
What is the first segment (XY) selected for refining S0? Enter edge label XY NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: XY
Your answer:
Q83NAT1 Mark·Write the number
Key ↓
Your answer:
Q84NAT1 Mark·Write the number
Key ↓
How many tours are represented in the node rs? Enter a natural number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42
Your answer:
Q85NAT1 Mark·Write the number
Key ↓
Your answer:
Read the passage below, then answer Q86–Q92
GAMES
Based on the above data, answer the given subquestions
Q86Short answer1 Mark·Write the answer
Asked 3 times Key ↓
List the horizon nodes in the best strategy. Enter the node labels as a comma separated list in ASCENDING order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: X,Y,Z
Your answer:
Q87Short answer1 Mark·Write the answer
Asked 3 times Key ↓
List the horizon nodes pruned by Alpha-Beta algorithm. Enter the node labels as a comma separated list in ASCENDING order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: X,Y,Z
Your answer:
Q88Short answer1 Mark·Write the answer
Key ↓
Your answer:
Q89Short answer1 Mark·Write the answer
Asked 3 times Key ↓
Your answer:
Q90MSQ1 Mark·Choose all correct options
Key ↓
Select the correct statements about the Alpha-Beta algorithm.
1. AAlpha-Cut prunes MAX nodes.
2. BAlpha-Cut is made by a MIN node.
3. CBeta-Cut prunes MIN nodes.
4. DBeta-Cut is made by a MAX node.
Q91MCQ1 Mark·Choose one option
Key ↓
Select the condition that triggers an Alpha-Cut.
1. Aeval(child) <= Alpha
2. BAlpha < eval(child) < Beta
3. CBeta <= eval(child)
4. DCannot be determined
Q92MCQ1 Mark·Choose one option
Key ↓
For a 2-ply game tree with branching factor 3, the number of strategies for MAX-player is __________ .
1. A2
2. B3
3. C2^2
4. D2^3
5. E3^2
6. F3^3
Read the passage below, then answer Q93–Q99
AUTOMATED PLANNING
The domain description of a Blocks World with a single one-armed robot is given below. Note: this is the same domain description used in the weekly assignments.
Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to dead-ends or cycles.
Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.
A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.
Based on the above data, answer the given subquestions
Q93NAT1 Mark·Write the number
Key ↓
What is the length of the optimal plan? Enter the number of actions in the optimal plan. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42
Your answer:
Q94MSQ1 Mark·Choose all correct options
Asked 3 times Key ↓
Which of the following are applicable actions for the given planning problem?
1. APickup(D)
2. BPickup(G)
3. CPickup(M)
4. DUnstack(C,M)
5. EUnstack(E,D)
Q95MSQ1 Mark·Choose all correct options
Asked 3 times Key ↓
Which of the following are relevant actions for the given planning problem?
1. APickup(G)
2. BStack(E,M)
3. CStack(G,E)
4. DUnstack(C,M)
5. EUnstack(E,D)
Q96MCQ1 Mark·Choose one option
Key ↓
Which of the following can be pushed as the first three elements onto the stack by the Goal Stack Planning algorithm? In the representation below the stack has a bottom on the right marked by the entry END. Use appropriate tie-breakers listed in the main data.
1. A{ on(E,M), on(G,E) }; on(E,M); on(G,E); END
2. B{ on(E,M), on(G,E) }; on(G,E); on(E,M); END
3. Con(G,E); on(E,M); { on(E,M), on(G,E) }; END
4. Don(E,M); on(G,E); { on(E,M), on(G,E) }; END
Q97MCQ1 Mark·Choose one option
Key ↓
For the subgoal ordering given in the goal description (and using the given tie breaking rules), which of the following is the first action popped out of the stack in Goal Stack Planning?
1. APickup(G)
2. BStack(G,E)
3. CUnstack(E,D)
4. DUnstack(C,M)
Q98MCQ1 Mark·Choose one option
Key ↓
For the subgoal ordering given in the goal description (and using the given tie breaking rules), does the Goal Stack Planning algorithm find an optimal plan?
1. AYes
2. BNo
3. CCannot be determined
Q99MCQ1 Mark·Choose one option
Key ↓
If the subgoals in the goal description are swapped places then does the Goal Stack Planning algorithm find an optimal plan?
1. AYes
2. BNo
3. CCannot be determined

Official Key

Master Answer Key & Explanations

Official answer keys from IIT Madras BS past papers. Click any question to review.

Reveal Key

Q1B, C

Q2A, B, D

Q3C

Q4S,F,C,A

Q5S,F,C,A,B,G

Q6S,F,H,C

Q7S,H,E,I,G

Q8S,H,E,D

Q9S,H,E,D,B,G

Q10S,H,E,D

Q11Nil

Q12A

Q13A, B

Q14C

Q154

Q16A,B,E,D,C

Q17DE,120 / ED,120

Q18A,B,E,D,C / A,C,D,E,B

Q19168

Q20B, D

Q21S,E,C,G

Q22S,F,B,A,G

Q23S,F,B,A,G

Q24C

Q25A

Q26b1,c2,b2,c3

Q27d3

Q28434

Q295

Q30A,B,D,E,C / A,C,E,D,B

Q31C, D

Q32A,C

Q33A,B,D,H

Q34A,B,D,H / A,D,H,B / D,H,A,B

Q35S,C,B / C,B

Q3645,50,80 / 50,80

Q3780

Q38C, D, E, F

Q39D

Q40C

Q41B, C, D

Q42F, G

Q43A, B

Q44A, B

Q45A

Q46A

Q47g,r,b / g,b,r

Q48S,C,F,G

Q49S,B,A,E,G

Q50S,B,A,E,G

Q51C

Q52A

Q53b1,c1,d2,b2

Q54d5

Q55366

Q565

Q57A,B,D,C,E / A,E,C,D,B

Q58A, C

Q59A,C,D

Q60A,B,E,I

Q61A,B,E,I / A,E,I,B / I,E,A,B

Q62S,B,A / B,A

Q6334,37,56 / 37,56

Q6456

Q65C, D, E, F

Q66C

Q67F

Q68B, C, D

Q69F, G

Q70A, B

Q71A, B

Q72A

Q73A

Q74g,r,b / g,b,r

Q75A

Q76A

Q77B

Q78B

Q79A

Q80A

Q81182

Q82AB / BA

Q83206

Q840

Q85320

Q86D,E,F

Q87H,I

Q88A,D,G

Q89E,F

Q90A, B, C, D

Q91A

Q92B

Q936

Q94B, D, E

Q95B, C

Q96C

Q97A

Q98B

Q99A

Questions and answer keys are reproduced from the official IIT Madras BS papers. BTechi is not affiliated with IIT Madras.