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

AI Search · Quiz 1 · 26 Oct 2025 (Afternoon)

20 questions · 20 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 1 · 26 Oct 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–Q3
STATE SPACE
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide one position either horizontally or vertically into the adjacent empty spot, effectively swapping the tile and the adjacent empty spot. A tile cannot slide diagonally.
Begin from the start state and build the state space graph by generating valid moves, call it Graph- 1230, use this graph to answer the sub-questions.
Q1MSQ1 Mark·Choose all correct options
Key ↓
1. AState A
2. BState B
3. CState C
4. DState D
Q2MSQ1 Mark·Choose all correct options
Key ↓
Select the statements that are true about Graph-1230.
1. AEvery move is reversible.
2. BEvery state has a path to every other state.
3. CSome states have more than two neighbours.
4. DEvery state has exactly two neighbours.
5. EEvery state has exactly one neighbour.
Q3MCQ1 Mark·Choose one option
Key ↓
The number of unique states in Graph-1230 is __________ .
1. Aless than 8
2. Bequal to 8
3. Cmore than 8
Read the passage below, then answer Q4–Q11
SEARCH
The MoveGen function and the heuristic function for a state space is provided below. Take S as the start node and G as the goal node.
When required use alphabetical order to break ties.
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
Q4Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Depth First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q5Short answer1 Mark·Write the answer
Key ↓
What is the path found by Depth First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q6Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Breadth First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q7Short answer1 Mark·Write the answer
Key ↓
What is the path found by Breadth First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q8Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Best First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q9Short answer1 Mark·Write the answer
Asked 3 times Key ↓
What is the path found by Best First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q10Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Hill Climbing. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q11Short answer1 Mark·Write the answer
Key ↓
What is the path found by Hill Climbing? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Read the passage below, then answer Q12–Q15
Genetic Algorithm
Answer the given subquestions.
Q12MCQ1 Mark·Choose one option
Key ↓
Convert the path representation A,C,K,F,B,H,G,I,D,L,E,J to ordinal representation. Use A,B,C,...,L as the reference (index) sequence.
1. A1,2,9,4,1,4,3,3,1,3,1,1
2. B9,4,10,4,2,1,1,5,3,3,1,1
3. C1,2,9,8,1,3,3,4,1,3,1,1
4. D3,10,8,3,2,2,5,1,3,3,2,1
Q13MSQ1 Mark·Choose all correct options
Key ↓
Path representations of two tours are given below. Generate offspring using Cycle Crossover. P1: I,D,L,E,J,A,C,K,F,B,H,G P2: C,K,I,D,B,E,J,A,H,L,G,F Select the child tours.
1. AI,K,L,D,J,E,C,A,F,B,H,G
2. BC,D,I,E,B,A,J,K,H,L,G,F
3. CI,D,L,K,B,A,E,H,C,J,F,G
4. DA,L,I,E,J,D,C,K,H,F,G,B
Q14MCQ1 Mark·Choose one option
Key ↓
Single-point crossover can be used with __________ .
1. AAdjacency Representation.
2. BPath Representation
3. COrdinal Representation
4. DAll of these
Q15NAT1 Mark·Write the number
Key ↓
For the case of 3-edge exchange, how many child tours are possible? Enter the number of child tours in the text box. (Assume that no pair of edges from the selected 3 edges share any city in common.) Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: 17
Your answer:
Read the passage below, then answer Q16–Q20
TSP
Use the distance matrix to construct TSP tours.
Based on the above data, answer the given subquestions.
Q16Short answer1 Mark·Write the answer
Key ↓
Use “A” as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is __________ . Enter the path representation of the tour, starting from “A” and tracing the cities as selected by the Nearest Neighbour Heuristic. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z
Your answer:
Q17Short answer1 Mark·Write the answer
Key ↓
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Identify the new edge added in the first merge operation. Enter the new edge and its savings. Enter an edge XY and an integer as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: XY,17
Your answer:
Q18Short answer1 Mark·Write the answer
Key ↓
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Enter the path representation of the Savings tour, starting from “A”. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z
Your answer:
Q19NAT1 Mark·Write the number
Key ↓
What is the cost of the tour generated by Savings Heuristic? Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: 17
Your answer:
Q20MSQ1 Mark·Choose all correct options
Key ↓
Consider N cities in a Euclidean plane and use the Euclidean Distance as the distance measure. For each city, take that city as the fulcrum (base) city and compute its Savings tour. From the resulting N Savings tours, select the cheapest tour. What can you conclude about the above procedure?
1. AThis procedure can be used to compute the optimal TSP tour.
2. BThis procedure is not suitable for computing the optimal TSP tour.
3. CThis procedure may not always terminate.
4. DThis procedure will always terminate.

Official Key

Master Answer Key & Explanations

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

Reveal Key

Q1B, C

Q2A, B, D

Q3C

Q4S,F,C,A

Q5S,F,C,A,B,G

Q6S,F,H,C

Q7S,H,E,I,G

Q8S,H,E,D

Q9S,H,E,D,B,G

Q10S,H,E,D

Q11Nil

Q12A

Q13A, B

Q14C

Q154

Q16A,B,E,D,C

Q17DE,120 / ED,120

Q18A,B,E,D,C / A,C,D,E,B

Q19168

Q20B, D

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