uiz Space

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

AI: Search Methods for Problem Solving Quiz 1: 25 February 2024 (January 2024 term)

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

Updated

Official paper: IIT M DEGREE AN2 EXAM QDB2 25 Feb 2024 · No negative marking.

Question 1

+0 marksOne correct option
  1. A

    Printed graph sheets were provided to me.`

  2. B

    Printed graph sheets were not provided to me.

  3. 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 correct option

STATE SPACE
One needs to count the number of nodes visited in each cycle of DFID __________ .

  1. A

    to compute the complexity of search

  2. B

    to make sure that the path returned is the shortest

  3. C

    to prevent the algorithm from getting into an infinite loop on an INFINITE graph when a goal node exists in the connected component

  4. D

    to prevent the algorithm from getting into an infinite loop on a FINITE graph when the goal node does not exist in the connected component

Show answer

Correct answer

  • D

    to prevent the algorithm from getting into an infinite loop on a FINITE graph when the goal node does not exist in the connected component

Question 2 on its own page

Question 3

+1 markOne correct option

STATE SPACE
In the Ant Colony Optimisation algorithm for solving the TSP __________ .

  1. A

    all the ants in the colony start from the same start city and then go in different directions

  2. B

    all ants construct the solution using a collaborative filtering approach

  3. C

    each ant constructs a tour independently

  4. D

    each ant constructs a tour using follow the leader principle

Show answer

Correct answer

  • C

    each ant constructs a tour independently

Question 3 on its own page

Question 4

+2 marksOne or more correct options

STATE SPACE

Select all that apply.

  1. A

    (13,NIL,2)

  2. B

    (NIL,3,21)

  3. C

    (1,3,2)

  4. D

    (NIL,NIL,123)

Show answer

Correct answers

  • A

    (13,NIL,2)

  • B

    (NIL,3,21)

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.

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 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,G

Show answer

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

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

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.

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

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,I,D

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 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,I,D,E,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 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,I

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

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • A

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

  • B

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

Question 13 on its own page

Question 14

+1 markOne or more correct options

Genetic Algorithm
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,...,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,G,K,B,H,I,F,A,L,D,J,E

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • A

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

  • B

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

Question 14 on its own page

Question 15

+2 marksOne correct option

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

Based on the above data, answer the given subquestions.

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

  1. A

    5,1,3,2,6,7,6,2,2,3,2,1

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answer

  • A

    5,1,3,2,6,7,6,2,2,3,2,1

Question 15 on its own page

Question 16

+2 marksWritten answer

Genetic Algorithm
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,...,L 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 Partially Mapped Crossover (PMX), use the locations from 5 to 8 as the mapping segment. Enter one of the child tours in the textbox.

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

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

Enter a comma separated list of cities.

DO NOT ENTER SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Show answer

Correct answer: E,L,D,F,H,A,C,K,G,I,J,B or C,I,A,E,J,L,K,F,H,D,B,G

Question 16 on its own page

Question 17

+1 markWritten answer

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

ABCDEF
A-6632187340
B66-92148160
C3292-261652
D181426-6880
E73811668-84
F4060528084-
BDCEADCDAC
1416182632
AFCFBFABDE
4052606668
AEDFBEEFBC
7380818492

Based on the above data, answer the given subquestions.

Start from city E and construct a tour using Nearest Neighbour Heuristic. Enter the path representation of the tour starting from city E.
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,C,D,B,F,A

Question 17 on its own page

Question 18

+1 markNumerical answer

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

ABCDEF
A-6632187340
B66-92148160
C3292-261652
D181426-6880
E73811668-84
F4060528084-
BDCEADCDAC
1416182632
AFCFBFABDE
4052606668
AEDFBEEFBC
7380818492

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

Question 18 on its own page

Question 19

+1 markWritten answer

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

ABCDEF
A-6632187340
B66-92148160
C3292-261652
D181426-6880
E73811668-84
F4060528084-
BDCEADCDAC
1416182632
AFCFBFABDE
4052606668
AEDFBEEFBC
7380818492

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

Question 19 on its own page

Question 20

+1 markNumerical answer

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

ABCDEF
A-6632187340
B66-92148160
C3292-261652
D181426-6880
E73811668-84
F4060528084-
BDCEADCDAC
1416182632
AFCFBFABDE
4052606668
AEDFBEEFBC
7380818492

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

Question 20 on its own page

Question 21

+1 markWritten answer

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

ABCDEF
A-6632187340
B66-92148160
C3292-261652
D181426-6880
E73811668-84
F4060528084-
BDCEADCDAC
1416182632
AFCFBFABDE
4052606668
AEDFBEEFBC
7380818492

Based on the above data, answer the given subquestions.

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

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,B,D,A,F,C or E,C,F,A,D,B

Question 21 on its own page