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

AI Search · Problem decomposition & AO*

6 questions · 6 marks · 2 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

Problem decomposition & AO*

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
NAT: Numerical response. No negative marking.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

End Term · 31 Aug 2025 (FN)End Term

Read the passage below, then answer Q1–Q3
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
Q1Short 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:
Q2Short 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:
Q3NAT1 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:

End Term · 31 Aug 2025 (AN)End Term

Read the passage below, then answer Q4–Q6
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.
Q4Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Your answer:
Q5Short 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:
Q6NAT1 Mark·Write the number
Asked 2 times Key ↓
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,B / C,B

Q245,50,80 / 50,80

Q380

Q4S,B,A / B,A

Q534,37,56 / 37,56

Q656

Questions and answer keys are reproduced from the official IIT Madras BS papers. Topics and repeated question types are BTechi’s own grouping. BTechi is not affiliated with IIT Madras.