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

AI Search · Quiz 2 · 3 Aug 2025 (Afternoon)

25 questions · 25 marks · 60 min

Answer key Take as mock

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

Quiz 2 · 3 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–Q6
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
Q1MCQ1 Mark·Choose one option
Key ↓
Does the Breadth First Search find the path to the goal?
1. AYes
2. BNo
3. CCannot be determined
Q2MCQ1 Mark·Choose one option
Key ↓
Does the Best First Search find the path to the goal?
1. AYes
2. BNo
3. CCannot be determined
Q3MCQ1 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
Q4MCQ1 Mark·Choose one option
Key ↓
1. AYes
2. BNo
3. CCannot be determined
Q5MCQ1 Mark·Choose one option
Key ↓
1. AYes
2. BNo
3. CCannot be determined
Q6MCQ1 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 Q7–Q11
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.
Q7NAT1 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:
Q8Short 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:
Q9NAT1 Mark·Write the number
Key ↓
Your answer:
Q10NAT1 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:
Q11NAT1 Mark·Write the number
Key ↓
Your answer:
Read the passage below, then answer Q12–Q18
GAMES
Based on the above data, answer the given subquestions
Q12Short 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:
Q13Short 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:
Q14Short answer1 Mark·Write the answer
Key ↓
Your answer:
Q15Short answer1 Mark·Write the answer
Asked 3 times Key ↓
Your answer:
Q16MSQ1 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.
Q17MCQ1 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
Q18MCQ1 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 Q19–Q25
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
Q19NAT1 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:
Q20MSQ1 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)
Q21MSQ1 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)
Q22MCQ1 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
Q23MCQ1 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)
Q24MCQ1 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
Q25MCQ1 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

Q1A

Q2A

Q3B

Q4B

Q5A

Q6A

Q7182

Q8AB / BA

Q9206

Q100

Q11320

Q12D,E,F

Q13H,I

Q14A,D,G

Q15E,F

Q16A, B, C, D

Q17A

Q18B

Q196

Q20B, D, E

Q21B, C

Q22C

Q23A

Q24B

Q25A

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