Quiz Space

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

AI Search Methods Quiz 1: 16 October 2022, Set QPG3 (September 2022 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 1 paper sat on 16 Oct 2022, in the September 2022 term, set QPG3: 20 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
20
Marks
25
Duration
120 min
MCQ
2
Written
12
MSQ
4
Numerical
2
Take as mock testPractise with answers

Updated

Official paper: 2022 Oct: IIT M QUIZ 1 DEGREE QPG3 · No negative marking.

Question 1

+1 markOne correct option

STATE SPACE
In the 8-puzzle, use the combination of tile-number (1 to 8) and the direction (Up, Down,Left, Right) of tile movement to denote a move, for example:
6U — move tile 6 up 2D — move tile 2 down 4L — move tile 4 left 8R — move tile 8 right
Based on the above data, answer the given subquestions.

Starting from board G, the sequence of moves 8D,7R,6U,5U will result in __________ .

Starting from board G, the sequence of moves 8D,7R,6U,5U will result in __________ .

  1. A

    Board G

  2. B

    Board A

  3. C

    Board B

  4. D

    Board C

  5. E

    Board D

Show answer

Correct answer

  • C

    Board B

Question 1 on its own page

Question 2

+1 markWritten answer

STATE SPACE
In the 8-puzzle, use the combination of tile-number (1 to 8) and the direction (Up, Down,Left, Right) of tile movement to denote a move, for example:
6U — move tile 6 up 2D — move tile 2 down 4L — move tile 4 left 8R — move tile 8 right
Based on the above data, answer the given subquestions.

Starting from board S, what is the shortest sequence of moves that will result in board G?

Starting from board S, what is the shortest sequence of moves that will result in board G?

Show answer

Correct answer: 6D,8R,7U,6L

Question 2 on its own page

Question 3

+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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,F,C,A

Question 3 on its own page

Question 4

+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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,Z,G

Show answer

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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,F,H,C

Question 5 on its own page

Question 6

+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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,Z,G

Show answer

Correct answer: S,H,E,I,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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,H,E,D

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,Z,G

Show answer

Correct answer: S,H,E,D,B,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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,H,E,D

Question 9 on its own page

Question 10

+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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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,Z,G

Show answer

Correct answer: Nil

Question 10 on its own page

Question 11

+2 marksOne or more correct options

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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

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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
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.

Select all that apply.

  1. A

    State Space 1

  2. B

    State Space 2

  3. C

    State Space 3

  4. D

    State Space 4

Show answer

Correct answers

  • A

    State Space 1

  • D

    State Space 4

Question 11 on its own page

Question 12

+1 markOne or more correct options

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L 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

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • A

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

  • B

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

Question 12 on its own page

Question 13

+1 markOne or more correct options

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L 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

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • A

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

  • B

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

Question 13 on its own page

Question 14

+2 marksOne correct option

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.

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

  1. A

    1,2,9,4,1,4,3,3,1,3,1,1

  2. B

    9,4,10,4,2,1,1,5,3,3,1,1

  3. C

    1,2,9,4,1,3,3,4,1,3,1,1

  4. D

    3,10,8,3,2,2,5,1,3,3,2,1

Show answer

Correct answer

  • A

    1,2,9,4,1,4,3,3,1,3,1,1

Question 14 on its own page

Question 15

+2 marksOne or more correct options

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.

GENETIC ALGORITHM
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.

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.

Select all that apply.

  1. A

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • A

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

  • B

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

Question 15 on its own page

Question 16

+1 markWritten answer

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.

Use E as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is __________ . Enter the path representation of the tour, starting from E and tracing the cities 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: E,X,Y,Z

Show answer

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

Question 16 on its own page

Question 17

+1 markNumerical answer

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
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: 513

Question 17 on its own page

Question 18

+1 markWritten answer

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
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 A.
Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z

Show answer

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

Question 18 on its own page

Question 19

+1 markNumerical answer

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
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: 575

Question 19 on its own page

Question 20

+1 markWritten answer

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

TSP
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.

Savings heuristic: the initial set of 6 tours with A as the fulcrum node is shown in the figure. Identify the first two edges that will be removed and the first new edge that will be added, and compute the savings. Enter the first edge added and the savings in the text box.

Savings heuristic: the initial set of 6 tours with A as the fulcrum node is shown in the figure. Identify the first two edges that will be removed and the first new edge that will be added, and compute the savings. Enter the first edge added and the savings in the text box.
An edge from X to Y is named as XY. Enter an edge name XY and a number as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: XY,17

Show answer

Correct answer: BG,172

Question 20 on its own page