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

AI Search · End Term · 31 Aug 2025 (Afternoon)

27 questions · 27 marks · 90 min

Answer key Take as mock

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

End Term · 31 Aug 2025 (Afternoon)

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.

Read the passage below, then answer Q1–Q5
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.
Q1Short 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:
Q2Short 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:
Q3Short 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:
Q4MCQ1 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
Q5MCQ1 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 Q6–Q10
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.
Q6Short 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:
Q7Short 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:
Q8Short 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:
Q9Short 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:
Q10Short 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 Q11–Q14
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.
Q11MSQ1 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
Q12Short 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:
Q13Short 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:
Q14Short answer1 Mark·Write the answer
Asked 3 times Key ↓
Your answer:
Read the passage below, then answer Q15–Q17
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.
Q15Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Your answer:
Q16Short 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:
Q17NAT1 Mark·Write the number
Asked 2 times Key ↓
Your answer:
Read the passage below, then answer Q18–Q20
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.
Q18MSQ1 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)
Q19MCQ1 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)
Q20MCQ1 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 Q21–Q24
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.
Q21MSQ1 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)
Q22MSQ1 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)
Q23MSQ1 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)
Q24MSQ1 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 Q25–Q27
CONSTRAINT SATISFACTION
Q25MCQ1 Mark·Choose one option
Asked 2 times Key ↓
Is the given CSP arc consistent?
1. AYes
2. BNo
3. CCannot be determined
Q26MCQ1 Mark·Choose one option
Asked 2 times Key ↓
Is the given CSP path consistent?
1. ANo
2. BYes
3. CCannot be determined
Q27Short 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:

Official Key

Master Answer Key & Explanations

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

Reveal Key

Q1S,C,F,G

Q2S,B,A,E,G

Q3S,B,A,E,G

Q4C

Q5A

Q6b1,c1,d2,b2

Q7d5

Q8366

Q95

Q10A,B,D,C,E / A,E,C,D,B

Q11A, C

Q12A,C,D

Q13A,B,E,I

Q14A,B,E,I / A,E,I,B / I,E,A,B

Q15S,B,A / B,A

Q1634,37,56 / 37,56

Q1756

Q18C, D, E, F

Q19C

Q20F

Q21B, C, D

Q22F, G

Q23A, B

Q24A, B

Q25A

Q26A

Q27g,r,b / g,b,r

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