uiz Space

May 2026 term · AI: Search Methods for Problem Solving · BSCS3003

AI: Search Methods for Problem Solving Quiz 2: 16 August 2026 (May 2026 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 2 paper sat on 16 Aug 2026, in the May 2026 term: 13 questions for 25 marks in 120 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.

Questions
13
Marks
25
Duration
120 min
Written
8
Numerical
1
MCQ
3
MSQ
1
Take as mock testPractise with answers

Updated

Official paper: Ai: Search Methods For Problem Solving 16 Aug 26 · No negative marking.

Question 1

+2 marksWritten answer

SEARCH
Consider a state space where each move is reversible and has 6 states (S,A,B,C,D,G) with S as start and G as goal. The heuristic function is:

Wherever applicable use alphabetical order.
Branch-and-Bound (BnB) algorithm is in mid-flight, the search tree as of the current moment is shown in the figure, where each node displays state and g-value.

Answer the sub-questions based on the information provided.

Make the necessary node refinements to complete the search tree like how Branch-and-Bound algorithm would have done before halting. How many times does each state occur in the final search tree? Enter the counts for S,A,B,C,D,G in the text box.
Enter a comma separated list of integers. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answers Case Sensitive : No

Show answer

Correct answer: 1,2,2,3,3,4

Question 1 on its own page

Question 2

+2 marksWritten answer

SEARCH
Consider a state space where each move is reversible and has 6 states (S,A,B,C,D,G) with S as start and G as goal. The heuristic function is:

Wherever applicable use alphabetical order.
Branch-and-Bound (BnB) algorithm is in mid-flight, the search tree as of the current moment is shown in the figure, where each node displays state and g-value.

Answer the sub-questions based on the information provided.

What is the path found by A* for the given state space?
Enter the path as a comma separated list, or enter NIL. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answers Case Sensitive : No

Show answer

Correct answer: S,B,D,G

Question 2 on its own page

Question 3

+2 marksWritten answer

SEARCH
Consider a state space where each move is reversible and has 6 states (S,A,B,C,D,G) with S as start and G as goal. The heuristic function is:

Wherever applicable use alphabetical order.
Branch-and-Bound (BnB) algorithm is in mid-flight, the search tree as of the current moment is shown in the figure, where each node displays state and g-value.

Answer the sub-questions based on the information provided.

For w=2, what is the path found by WA* for the given state space?
Enter the path as a comma separated list, or enter NIL. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answers Case Sensitive : No

Show answer

Correct answer: S,A,C,G

Question 3 on its own page

Question 4

+1 markNumerical answer

TSP
Answer the given subquestions.

Consider 6 cities A to F, how many tours are represented by the TSP BnB node (S_0, ~AB, ~AC, BE, ~DB, ~DA)? Infer the permanent segments before counting the tours.

Show answer

Correct answer: 1

Question 4 on its own page

Question 5

+2 marksOne correct option

TSP
Answer the given subquestions.

The TSP BnB procedure will return the optimal tour __________ .

  1. A

    even if node refinement step disables segment inferencing

  2. B

    only when node refinement step uses segment inferencing

Show answer

Correct answer

  • A

    even if node refinement step disables segment inferencing

Question 5 on its own page

Question 6

+2 marksWritten answer

TSP
Answer the given subquestions.

Let N be the number of cities. For the purpose of analysis, construct a relaxed (version of TSP BnB) tree in the following manner: expand S_0 by adding 2 children (one with XY and another with ~XY), similarly expand the children, and continue expanding until all branches are fully expanded, without ever applying cost estimates, tour constraints, or inferences. The number of leaf nodes in the relaxed tree will be of the order of __________ . Give your answer in Big-O notation. Answers Case Sensitive : No

Show answer

Correct answer: O(2^(N^2))

Question 6 on its own page

Question 7

+2 marksWritten answer

TSP
Answer the given subquestions.

Consider the relaxed tree generated in the PREVIOUS question. If we prune all nodes that violate the tour condition, the number of leaf nodes in the pruned tree will be of the order of __________ . Give your answer in Big-O notation. Answers Case Sensitive : No

Show answer

Correct answer: O(N!)

Question 7 on its own page

Question 8

+2 marksWritten answer

GAMES

Answer the given subquestions.

Identify the horizon nodes pruned by beta-cuts. Enter their node labels in the text box.
Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answers Case Sensitive : No

Show answer

Correct answer: G,H

Question 8 on its own page

Question 9

+2 marksWritten answer

GAMES

Answer the given subquestions.

Solve the game tree using SSS* algorithm. Identify the SOLVED horizon nodes that are removed from the queue by the pruning step. Not popped from the queue but pruned from the queue. Enter the node labels as a comma separated list in ASCENDING order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answers Case Sensitive : No

Show answer

Correct answer: C,I,K

Question 9 on its own page

Question 10

+2 marksWritten answer

GAMES

Answer the given subquestions.

What is the horizon effect? Give a concise and clear answer. Stay on point.
NOTE: Your answer should not exceed 100 words.

Show answer

A written answer, not marked automatically.

Question 10 on its own page

Question 11

+2 marksOne correct option

AUTOMATED PLANNING
Answer the given subquestions.

Can the Forward State Space Planning algorithm discussed in the lecture solve Sussman Anomaly?

  1. A

    Yes

  2. B

    No

Show answer

Correct answer

  • A

    Yes

Question 11 on its own page

Question 12

+2 marksOne correct option

AUTOMATED PLANNING
Answer the given subquestions.

Can the Goal Stack Planning algorithm discussed in the lecture solve Sussman Anomaly?

  1. A

    Yes

  2. B

    No

Show answer

Correct answer

  • A

    Yes

Question 12 on its own page

Question 13

+2 marksOne or more correct options

AUTOMATED PLANNING
Answer the given subquestions.

What is true about the Goal Stack Planning algorithm? (Note: a unit goal cannot be decomposed into subgoals.)

Select all that apply.

  1. A

    During the plan building phase, it will solve every unit goal exactly once.

  2. B

    It will never repeat the same action twice in the final plan.

  3. C

    It will build the plan in a linear fashion without backtracking.

  4. D

    None of these.

Show answer

Correct answer

  • D

    None of these.

Question 13 on its own page