uiz Space

January 2025 term · AI: Search Methods for Problem Solving · BSCS3003

AI: Search Methods for Problem Solving Quiz 1: 23 February 2025 (January 2025 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 1 paper sat on 23 Feb 2025, in the January 2025 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
MSQ
5
MCQ
2
Written
12
Numerical
2
Take as mock testPractise with answers

Updated

Official paper: IIT M DEGREE AN EXAM QDB2 23 Feb 2025 · No negative marking.

Question 1

+0 marksOne or more correct options

Select all that apply.

  1. A

    Printed graph sheets were provided on time.

  2. B

    Printed graph sheets were provided late.

  3. C

    Printed graph sheets were not provided.

  4. D

    I used the graph sheets.

  5. E

    I did not use graph sheets.

Show answer

Correct answers

  • A

    Printed graph sheets were provided on time.

  • D

    I used the graph sheets.

Question 1 on its own page

Question 2

+1 markOne or more correct options

STATE SPACE
Select the algorithms that find the shortest path (measured in number of hops).

Select all that apply.

  1. A

    Breadth-First Search

  2. B

    Best-First Search

  3. C

    Depth-First Search

  4. D

    DFID-N (opens only new nodes)

  5. E

    DFID-C (reopens closed nodes)

  6. F

    Hill Climbing

Show answer

Correct answers

  • A

    Breadth-First Search

  • E

    DFID-C (reopens closed nodes)

Question 2 on its own page

Question 3

+2 marksOne correct option

STATE SPACE

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • D
Question 3 on its own page

Question 4

+1 markOne or more correct options

STATE SPACE

Select all that apply.

  1. A

    Every move is reversible.

  2. B

    There is at least one move that is not reversible.

  3. C

    There is a path from every state to every other state.

  4. D

    Every state has two 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 two neighbours.

Question 4 on its own page

Question 5

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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,B,A,C

Question 5 on its own page

Question 6

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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,B,C,F,G

Question 6 on its own page

Question 7

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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,B,D,E

Question 7 on its own page

Question 8

+2 marksWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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,E,I,G

Question 8 on its own page

Question 9

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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,H,F

Question 9 on its own page

Question 10

+2 marksWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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,H,F,G

Question 10 on its own page

Question 11

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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,H

Question 11 on its own page

Question 12

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node.
The MoveGen function returns neighbours in alphabetical order.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed.

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.
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

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use D, E, F,..., M as the reference (index) sequence to prepare tour representations.

Based on the above data, answer the given subquestions.

Select the valid path representations of the tour.

Select all that apply.

  1. A

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • A

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

  • C

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

Question 13 on its own page

Question 14

+1 markOne or more correct options

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use D, E, F,..., M as the reference (index) sequence to prepare tour representations.

Based on the above data, answer the given subquestions.

Select the valid adjacency representations of the tour.

Select all that apply.

  1. A

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • B

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

  • D

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

Question 14 on its own page

Question 15

+2 marksOne correct option

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use D, E, F,..., M as the reference (index) sequence to prepare tour representations.

Based on the above data, answer the given subquestions.

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

  1. A

    7, 4, 3, 4, 5, 5, 2, 1, 1, 1

  2. B

    6, 8, 4, 1, 2, 2, 2, 1, 1, 1

  3. C

    6, 4, 8, 2, 1, 5, 2, 1, 1, 1

  4. D

    7, 3, 6, 4, 2, 3, 3, 3, 2, 1

Show answer

Correct answer

  • B

    6, 8, 4, 1, 2, 2, 2, 1, 1, 1

Question 15 on its own page

Question 16

+2 marksWritten answer

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use D, E, F,..., M as the reference (index) sequence to prepare tour representations.

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,L,G,I,F,M,E,D,H,K or I,G,F,D,L,H,J,E,K,M

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.

ABCDE
A-58923481
B58-204670
C9220-2853
D344628-12
E81705312-
DEBCCDADBD
1220283446
CEABBEAEAC
5358708192

Based on the above data, answer the given subquestions.

Start from city C and construct a tour using Nearest Neighbour Heuristic. Enter the path representation of the tour starting from city C. 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: C,X,Y,Z

Show answer

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

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.

ABCDE
A-58923481
B58-204670
C9220-2853
D344628-12
E81705312-
DEBCCDADBD
1220283446
CEABBEAEAC
5358708192

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: 251

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.

ABCDE
A-58923481
B58-204670
C9220-2853
D344628-12
E81705312-
DEBCCDADBD
1220283446
CEABBEAEAC
5358708192

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 C.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: C,X,Y,Z

Show answer

Correct answer: C,D,E,A,B or C,B,A,E,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.

ABCDE
A-58923481
B58-204670
C9220-2853
D344628-12
E81705312-
DEBCCDADBD
1220283446
CEABBEAEAC
5358708192

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: 199

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.

ABCDE
A-58923481
B58-204670
C9220-2853
D344628-12
E81705312-
DEBCCDADBD
1220283446
CEABBEAEAC
5358708192

Based on the above data, answer the given subquestions.

Take C 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 C.

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

Show answer

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

Question 21 on its own page