uiz Space

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

AI: Search Methods for Problem Solving Quiz 1: 7 July 2024 (May 2024 term)

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

Updated

Official paper: IIT M DEGREE AN EXAM QDB2 7 July 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

Which of the following is/are guaranteed in any state space?

  1. A

    Each move is reversible.

  2. B

    Each state is reachable from every other state.

  3. C

    The goal state is reachable from the start state.

  4. D

    None of these.

Show answer

Correct answer

  • D

    None of these.

Question 2 on its own page

Question 3

+2 marksOne or more correct options

Consider the 3-2-1 Water Jug puzzle with three jugs A, B and C of capacities 3L, 2L and 1L, respectively.
A state is uniquely represented by the amount of water present in the three jugs, for example, the tuple (3,0,0) describes the state where jug A contains 3L of water and jugs B and C are empty. Two basic (atomic) moves are allowed: (1.) pick up a jug and fill up (top up) another jug, and (2.) pick up a jug and empty it into another jug, without spilling any water in the process. Start from (3,0,0) and construct the state space graph of this puzzle.
Which of the following states occur in the state space graph?

Select all that apply.

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

Correct answers

  • A
  • B
Question 3 on its own page

Question 4

+1 markOne or more correct options

Which of the following is true about the 3-2-1 Water Jug state space?

Select all that apply.

  1. A

    Every move is reversible.

  2. B

    Every state is reachable from every other state.

  3. C

    From (3,0,0) there is a path to (1,1,1).

Show answer

Correct answers

  • B

    Every state is reachable from every other state.

  • C

    From (3,0,0) there is a path to (1,1,1).

Question 4 on its own page

Question 5

+1 markWritten answer

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

Question 5 on its own page

Question 6

+1 markWritten answer

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,A,E,D,G

Question 6 on its own page

Question 7

+1 markWritten answer

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

Question 7 on its own page

Question 8

+2 marksWritten answer

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

Question 8 on its own page

Question 9

+1 markWritten answer

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,C,E,H

Question 9 on its own page

Question 10

+2 marksWritten answer

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,C,E,D,G

Question 10 on its own page

Question 11

+1 markWritten answer

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,C,E,H

Question 11 on its own page

Question 12

+1 markWritten answer

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

A tour of 12 cities is shown below. The edges are bi-directional. Use K,L,M,...,V 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

    M,U,S,K,O,V,R,T,P,L,N,Q

  2. B

    K,S,U,M,Q,N,L,P,T,R,V,O

  3. C

    M,U,S,K,O,V,R,T,P,L,N,Q,M

  4. D

    K,S,U,M,Q,N,L,P,T,R,V,O,K

Show answer

Correct answers

  • A

    M,U,S,K,O,V,R,T,P,L,N,Q

  • B

    K,S,U,M,Q,N,L,P,T,R,V,O

Question 13 on its own page

Question 14

+1 markOne or more correct options

A tour of 12 cities is shown below. The edges are bi-directional. Use K,L,M,...,V 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

    O,N,U,Q,V,L,M,T,K,P,S,R

  2. B

    S,P,Q,L,K,T,N,V,U,R,M,O

  3. C

    P,N,U,Q,V,L,O,T,K,M,S,R

  4. D

    S,P,T,L,Q,K,N,V,U,R,M,O

Show answer

Correct answers

  • A

    O,N,U,Q,V,L,M,T,K,P,S,R

  • B

    S,P,Q,L,K,T,N,V,U,R,M,O

Question 14 on its own page

Question 15

+2 marksOne correct option

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

Based on the above data, answer the given subquestions.

Convert the path representation O,T,M,L,U,P,K,N,R,V,S,Q to ordinal representation.

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

Correct answer

  • A
Question 15 on its own page

Question 16

+2 marksWritten answer

A tour of 12 cities is shown below. The edges are bi-directional. Use K,L,M,...,V 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.

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

Show answer

Correct answer: U,N,M,L,O,V,R,T,K,P,S,Q or M,O,S,R,U,P,K,N,V,L,T,Q

Question 16 on its own page

Question 17

+1 markWritten answer

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

ABCDEF
A-7596137759
B75-74152622
C9674-602954
D131560-2550
E77262925-52
F5922545052-
ADBDBFDEBE
1315222526
CEDFEFCFAF
2950525459
CDBCABAEAC
6074757796

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

Question 17 on its own page

Question 18

+1 markNumerical answer

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

ABCDEF
A-7596137759
B75-74152622
C9674-602954
D131560-2550
E77262925-52
F5922545052-
ADBDBFDEBE
1315222526
CEDFEFCFAF
2950525459
CDBCABAEAC
6074757796

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

Question 18 on its own page

Question 19

+1 markWritten answer

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

ABCDEF
A-7596137759
B75-74152622
C9674-602954
D131560-2550
E77262925-52
F5922545052-
ADBDBFDEBE
1315222526
CEDFEFCFAF
2950525459
CDBCABAEAC
6074757796

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

Question 19 on its own page

Question 20

+1 markNumerical answer

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

ABCDEF
A-7596137759
B75-74152622
C9674-602954
D131560-2550
E77262925-52
F5922545052-
ADBDBFDEBE
1315222526
CEDFEFCFAF
2950525459
CDBCABAEAC
6074757796

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

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

ABCDEF
A-7596137759
B75-74152622
C9674-602954
D131560-2550
E77262925-52
F5922545052-
ADBDBFDEBE
1315222526
CEDFEFCFAF
2950525459
CDBCABAEAC
6074757796

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

Question 21 on its own page