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

AI Search · Branch & Bound and A* search

16 questions · 16 marks · 3 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

Branch & Bound and A* search

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MCQ: Exactly 1 option is correct. Negative marking applies.
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–Q5
SEARCH
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 ↓
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,E,S,E,S,E,... 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.

End Term · 31 Aug 2025 (AN)End Term

Read the passage below, then answer Q6–Q10
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.
Q6Short 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:
Q7Short 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:
Q8Short 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:
Q9MCQ1 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
Q10MCQ1 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.

Quiz 2 · 3 Aug 2025 (AN)Quiz 2

Read the passage below, then answer Q11–Q16
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
Q11MCQ1 Mark·Choose one option
Key ↓
Does the Breadth First Search find the path to the goal?
1. AYes
2. BNo
3. CCannot be determined
Q12MCQ1 Mark·Choose one option
Key ↓
Does the Best First Search find the path to the goal?
1. AYes
2. BNo
3. CCannot be determined
Q13MCQ1 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
Q14MCQ1 Mark·Choose one option
Key ↓
1. AYes
2. BNo
3. CCannot be determined
Q15MCQ1 Mark·Choose one option
Key ↓
1. AYes
2. BNo
3. CCannot be determined
Q16MCQ1 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

Official Key

Master Answer Key & Explanations

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

Reveal Key

Q1S,E,C,G

Q2S,F,B,A,G

Q3S,F,B,A,G

Q4C

Q5A

Q6S,C,F,G

Q7S,B,A,E,G

Q8S,B,A,E,G

Q9C

Q10A

Q11A

Q12A

Q13B

Q14B

Q15A

Q16A

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.