Figure from the original question paper

(A) Printed graph sheets were provided to me.

(B) Printed graph sheets were not provided to me.

(C) I did not use graph sheets.

September 2024 term · AI: Search Methods for Problem Solving · BSCS3003

AI: Search Methods for Problem Solving Quiz 1: 27 October 2024 (September 2024 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 1 paper sat on 27 Oct 2024, in the September 2024 term: 21 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: 21
Marks: 25
Duration: 120 min
MCQ: 2
MSQ: 5
Written: 12
Numerical: 2

Take as mock test Practise with answers

Updated 25 Sept 2026

Official paper: IIT M DEGREE AN EXAM QDB2 27 Oct 2024 · No negative marking.

Question 1

+0 marksOne correct option

A
Printed graph sheets were provided to me.
B
Printed graph sheets were not provided to me.
C
I did not use graph sheets.

Show answer

Correct answer

A
Printed graph sheets were provided to me.

Question 1 on its own page

Question 2

+1 markOne or more correct options

STATE SPACE
Which of these algorithms are complete?

Select all that apply.

A
Depth-First Search
B
Breadth-First Search
C
Best-First Search
D
Hill Climbing

Show answer

Correct answers

A
Depth-First Search
B
Breadth-First Search
C
Best-First Search

Question 2 on its own page

Question 3

+2 marksOne or more correct options

STATE SPACE

Select all that apply.

A
102/453
B
130/425
C
023/145
D
201/354

Show answer

Correct answers

B
130/425
C
023/145

Question 3 on its own page

Question 4

+1 markOne or more correct options

STATE SPACE
Which of the following is true about the 5-Puzzle state space that is reachable from 123/450?

Select all that apply.

A
Every move is reversible.
B
There is at least one move that is not reversible.
C
There is a path from every state to every other state.
D
Every state has at most three neighbours.

Show answer

Correct answers

A
Every move is reversible.
C
There is a path from every state to every other state.
D
Every state has at most three neighbours.

Question 4 on its own page

Question 5

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the first 4 nodes inspected by Depth First Search. List the nodes in the order they were 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

Show answer

Correct answer: S,A,B,C

Question 5 on its own page

Question 6

+1 markWritten answer

Based on the above data, answer the given subquestions.

What is the path found by Depth First Search?
Enter the path as a comma separated list of node labels.
Enter NIL if there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G

Show answer

Correct answer: S,A,B,C,G

Question 6 on its own page

Question 7

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the first 4 nodes inspected by Breadth First Search. List the nodes in the order they were 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

Show answer

Correct answer: S,A,D,H

Question 7 on its own page

Question 8

+2 marksWritten answer

Based on the above data, answer the given subquestions.

What is the path found by Breadth First Search?
Enter the path as a comma separated list of node labels.
Enter NIL if there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G

Show answer

Correct answer: S,H,F,G

Question 8 on its own page

Question 9

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the first 4 nodes inspected by Best First Search. List the nodes in the order they were 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

Show answer

Correct answer: S,D,E,B

Question 9 on its own page

Question 10

+2 marksWritten answer

Based on the above data, answer the given subquestions.

What is the path found by Best First Search?
Enter the path as a comma separated list of node labels.
Enter NIL if there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G

Show answer

Correct answer: S,D,E,B,C,G

Question 10 on its own page

Question 11

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the first 4 nodes inspected by Hill Climbing. List the nodes in the order they were 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

Show answer

Correct answer: S,D,E

Question 11 on its own page

Question 12

+1 markWritten answer

Based on the above data, answer the given subquestions.

What is the path found by Hill Climbing?
Enter the path as a comma separated list of node labels.
Enter NIL if there is no path.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G

Show answer

Correct answer: NIL

Question 12 on its own page

Question 13

+1 markOne or more correct options

Based on the above data, answer the given subquestions.

Select the valid path representations of the tour.

Select all that apply.

A
J,F,K,H,E,L,D,I,M,G
B
J,F,K,H,E,L,D,I,M,G,J
C
D,I,M,G,J,F,K,H,E,L
D
D,I,M,G,J,F,K,H,E,L,D

Show answer

Correct answers

A
J,F,K,H,E,L,D,I,M,G
C
D,I,M,G,J,F,K,H,E,L

Question 13 on its own page

Question 14

+1 markOne or more correct options

Based on the above data, answer the given subquestions.

Select the valid adjacency representations of the tour.

Select all that apply.

A
E,L,K,J,M,H,F,D,I,G
B
I,L,K,J,E,M,F,H,D,G
C
K,D,J,M,I,L,G,F,E,H
D
L,H,J,M,K,D,G,F,E,I

Show answer

Correct answers

B
I,L,K,J,E,M,F,H,D,G
D
L,H,J,M,K,D,G,F,E,I

Question 14 on its own page

Question 15

+2 marksOne correct option

Based on the above data, answer the given subquestions.

Convert the path representation E,J,L,K,F,H,I,M,G,D to ordinal representation.

A
2,6,7,6,2,4,1,2,2,1
B
2,6,7,6,2,3,3,3,2,1
C
7,3,6,4,2,4,1,2,2,1
D
7,3,6,4,2,3,3,3,2,1

Show answer

Correct answer

B
2,6,7,6,2,3,3,3,2,1

Question 15 on its own page

Question 16

+2 marksWritten answer

Based on the above data, answer the given subquestions.

Two tours in path representation are given below. Generate offspring using Cycle Crossover. Enter one of the child tours in the textbox.

Enter a comma separated list of cities.
DO NOT ENTER SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Show answer

Correct answer: J,F,L,K,E,H,D,I,M,G or E,J,K,H,F,L,I,M,G,D

Question 16 on its own page

Question 17

+1 markWritten answer

TSP

The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided below. Use this information to construct TSP tours.

	A	B	C	D	E
A	-	81	33	98	19
B	81	-	50	60	56
C	33	50	-	42	25
D	98	60	42	-	66
E	19	56	25	66	-

AE	CE	AC	CD	BC
19	25	33	42	50

BE	BD	DE	AB	AD
56	60	66	81	98

Based on the above data, answer the given subquestions.

Start from city B and construct a tour using Nearest Neighbour Heuristic. Enter the path representation of the tour starting from city B. Use the same order in which cities were added to the tour.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: B,X,Y,Z

Show answer

Correct answer: B,C,E,A,D

Question 17 on its own page

Question 18

+1 markNumerical answer

TSP

The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided below. Use this information to construct TSP tours.

	A	B	C	D	E
A	-	81	33	98	19
B	81	-	50	60	56
C	33	50	-	42	25
D	98	60	42	-	66
E	19	56	25	66	-

AE	CE	AC	CD	BC
19	25	33	42	50

BE	BD	DE	AB	AD
56	60	66	81	98

Based on the above data, answer the given subquestions.

What is the cost of the tour generated by Nearest Neighbour Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: 17

Show answer

Correct answer: 252

Question 18 on its own page

Question 19

+1 markWritten answer

TSP

The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided below. Use this information to construct TSP tours.

	A	B	C	D	E
A	-	81	33	98	19
B	81	-	50	60	56
C	33	50	-	42	25
D	98	60	42	-	66
E	19	56	25	66	-

AE	CE	AC	CD	BC
19	25	33	42	50

BE	BD	DE	AB	AD
56	60	66	81	98

Based on the above data, answer the given subquestions.

Construct a tour using Greedy Heuristic. Enter the path representation of the tour starting from city B.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: B,X,Y,Z

Show answer

Correct answer: B,D,C,E,A or B,A,E,C,D

Question 19 on its own page

Question 20

+1 markNumerical answer

TSP

The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided below. Use this information to construct TSP tours.

	A	B	C	D	E
A	-	81	33	98	19
B	81	-	50	60	56
C	33	50	-	42	25
D	98	60	42	-	66
E	19	56	25	66	-

AE	CE	AC	CD	BC
19	25	33	42	50

BE	BD	DE	AB	AD
56	60	66	81	98

Based on the above data, answer the given subquestions.

What is the cost of the tour generated by Greedy Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: 17

Show answer

Correct answer: 227

Question 20 on its own page

Question 21

+1 markWritten answer

TSP

The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided below. Use this information to construct TSP tours.

	A	B	C	D	E
A	-	81	33	98	19
B	81	-	50	60	56
C	33	50	-	42	25
D	98	60	42	-	66
E	19	56	25	66	-

AE	CE	AC	CD	BC
19	25	33	42	50

BE	BD	DE	AB	AD
56	60	66	81	98

Based on the above data, answer the given subquestions.

Take B as the fulcrum node and compute the two missing values in the savings list (full list) given below. Construct the savings tour. Enter the path representation of the tour starting from city B.

Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: B,X,Y,Z

Show answer

Correct answer: B,D,C,A,E or B,E,A,C,D

Question 21 on its own page