uiz Space

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

AI: Search Methods for Problem Solving Quiz 2: 24 March 2024 (January 2024 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 2 paper sat on 24 Mar 2024, in the January 2024 term: 26 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
26
Marks
25
Duration
120 min
MCQ
6
Written
11
Numerical
7
MSQ
2
Take as mock testPractise with answers

Updated

Official paper: IIT M DEGREE AN EXAM QDB2 24 Mar 2024 · No negative marking.

Question 1

+0 marksOne correct option

ASK FOR PRINTED GRAPH SHEETS

8 PAGES TWO-SIDE PRINT

  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 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 (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the given subquestions.

In the map, S is the first node to be refined, determine the next 3 nodes from the 2nd to 4th node refined by A*. Enter the nodes in the order they are refined.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: W,X,Y,Z

Show answer

Correct answer: A,B,D

Question 2 on its own page

Question 3

+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 (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the given subquestions.

For the 3 nodes from the 2nd to 4th node refined by A*, list the f-values of those nodes as a comma separated list.
Enter a comma separated list of natural numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 2,7,1,8

Show answer

Correct answer: 22,24,26

Question 3 on its own page

Question 4

+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 (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the given subquestions.

For the 3 nodes from the 2nd to 4th node refined by A*, list the parent nodes assigned by A*. Enter a comma separated list of parent node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: W,X,Y,Z

Show answer

Correct answer: S,A,A

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 (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the given subquestions.

What is the final path found by A*?
Enter the path as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,G

Show answer

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

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 (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the given subquestions.

For w=3, what is the final path found by WA* algorithm?
Enter the path as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,Z,G

Show answer

Correct answer: S,D,E,G

Question 6 on its own page

Question 7

+1 markNumerical 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 (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the given subquestions.

What is the cost of the path found by Branch-and-Bound algorithm?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 28

Question 7 on its own page

Question 8

+1 markOne correct option

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 (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.
The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.
Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.

Emulate A*, WA* and Branch-and-Bound on the given map, then answer the given subquestions.

Is the heuristic admissible in the given map?

  1. A

    Yes

  2. B

    No

  3. C

    Cannot be determined

Show answer

Correct answer

  • A

    Yes

Question 8 on its own page

Question 9

+1 markNumerical answer

The distance matrix for 5 cities are provided below.

ABCDE
A-80786850
B80-1527838
C78152-98114
D687898-44
E503811444-

Solve the sub-questions using the TSP Branch-and-Bound algorithm.
Attention: Infer as much as possible (and as early as possible) about the permanent segments in the partial solutions. A segment is a two-way edge between two cities.

What is the lower bound on the cost of the tours (S0) as per the TSP BnB algorithm discussed in class?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 302

Question 9 on its own page

Question 10

+1 markNumerical answer

The distance matrix for 5 cities are provided below.

ABCDE
A-80786850
B80-1527838
C78152-98114
D687898-44
E503811444-

Solve the sub-questions using the TSP Branch-and-Bound algorithm.
Attention: Infer as much as possible (and as early as possible) about the permanent segments in the partial solutions. A segment is a two-way edge between two cities.

Infer all the permanently included segments in the node (S0,BE,~DE,AE) in the TSP BnB search tree. Enter the total number of permanently included segments in the text box.
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 3

Question 10 on its own page

Question 11

+1 markNumerical answer

The distance matrix for 5 cities are provided below.

ABCDE
A-80786850
B80-1527838
C78152-98114
D687898-44
E503811444-

Solve the sub-questions using the TSP Branch-and-Bound algorithm.
Attention: Infer as much as possible (and as early as possible) about the permanent segments in the partial solutions. A segment is a two-way edge between two cities.

Infer all the permanently excluded segments in the node (S0,BE,~DE,AE) in the TSP BnB search tree. Enter the total number of permanently excluded segments in the text box.
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 3

Question 11 on its own page

Question 12

+1 markNumerical answer

The distance matrix for 5 cities are provided below.

ABCDE
A-80786850
B80-1527838
C78152-98114
D687898-44
E503811444-

Solve the sub-questions using the TSP Branch-and-Bound algorithm.
Attention: Infer as much as possible (and as early as possible) about the permanent segments in the partial solutions. A segment is a two-way edge between two cities.

How many tours are represented by the node (S0,BE,~DE,AE) in the TSP BnB search tree? Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 2

Question 12 on its own page

Question 13

+1 markNumerical answer

The distance matrix for 5 cities are provided below.

ABCDE
A-80786850
B80-1527838
C78152-98114
D687898-44
E503811444-

Solve the sub-questions using the TSP Branch-and-Bound algorithm.
Attention: Infer as much as possible (and as early as possible) about the permanent segments in the partial solutions. A segment is a two-way edge between two cities.

What is the cost of the node (S0,BE,~DE,AE) in the TSP BnB search tree?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 173

Show answer

Correct answer: 332

Question 13 on its own page

Question 14

+1 markWritten answer

The figure shows a game tree with evaluations W (win), L (loss) and D (draw) from Max's perspective. The nodes are labeled in a level-by-level (a,b,...,e) left-to-right (1,2,...) manner as indicated in the game tree.

Based on the above data, answer the given subquestions.

What is the outcome (W, D or L) of the game when both players play perfectly?
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X

Show answer

Correct answer: W

Question 14 on its own page

Question 15

+1 markWritten answer

The figure shows a game tree with evaluations W (win), L (loss) and D (draw) from Max's perspective. The nodes are labeled in a level-by-level (a,b,...,e) left-to-right (1,2,...) manner as indicated in the game tree.

Based on the above data, answer the given subquestions.

Change the value of only one leaf node such that the outcome of the game changes. Which leaf node will you change and what will be its new value? Enter the label of the leaf node and the new value as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: a1,X

Show answer

Correct answer: c6,D or d4,D or e3,D or e4,D or c6,L or d4,L or e3,L or e4,L

Question 15 on its own page

Question 16

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the horizon nodes in the best strategy.
Enter the node labels as a comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,C

Question 16 on its own page

Question 17

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the horizon nodes pruned by Alpha-Beta algorithm.
Enter the node labels as a comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: D,G,H,K,L

Question 17 on its own page

Question 18

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the horizon nodes in the initial cluster formed by SSS* algorithm.
Enter the node labels as a comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,B,E,F,I,J

Question 18 on its own page

Question 19

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the horizon nodes assigned SOLVED status by the SSS* algorithm.
Enter the node labels as a comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,B,C,E,F,I,J or A,B,E,F,I,J,C

Question 19 on its own page

Question 20

+1 markNumerical answer

The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

Based on the above data, answer the given subquestions.

What is the length of the optimal plan? Enter the number of actions in the optimal plan. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 5

Question 20 on its own page

Question 21

+1 markOne or more correct options

The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

Based on the above data, answer the given subquestions.

Which of the following are applicable actions in the start state for the given planning problem?

Select all that apply.

  1. A

    Pickup(A)

  2. B

    Putdown(A)

  3. C

    Stack(A,B)

  4. D

    Stack(A,C)

  5. E

    Unstack(A,C)

  6. F

    Unstack(A,B)

Show answer

Correct answers

  • B

    Putdown(A)

  • C

    Stack(A,B)

  • D

    Stack(A,C)

Question 21 on its own page

Question 22

+1 markOne or more correct options

The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

Based on the above data, answer the given subquestions.

Which of the following are relevant actions for the goal description in the given planning problem?

Select all that apply.

  1. A

    Pickup(B)

  2. B

    Pickup(C)

  3. C

    Putdown(A)

  4. D

    Stack(B,C)

  5. E

    Stack(C,A)

  6. F

    Unstack(C,D)

Show answer

Correct answers

  • D

    Stack(B,C)

  • E

    Stack(C,A)

Question 22 on its own page

Question 23

+1 markOne correct option

The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

Based on the above data, answer the given subquestions.

For the subgoal ordering given in the goal description (and using the given tie breaking rules) which of the following can be pushed as the first three elements onto the stack by the Goal Stack Planning algorithm? In the representation below, the bottom of the stack is on the right end, marked by BOTTOM.

  1. A

    { on(C,A), on(B,C) }; on(C,A); on(B,C); BOTTOM

  2. B

    { on(C,A), on(B,C) }; on(B,C); on(C,A); BOTTOM

  3. C

    on(B,C); on(C,A); { on(C,A), on(B,C) }; BOTTOM

  4. D

    on(C,A); on(B,C); { on(C,A), on(B,C) }; BOTTOM

Show answer

Correct answer

  • C

    on(B,C); on(C,A); { on(C,A), on(B,C) }; BOTTOM

Question 23 on its own page

Question 24

+1 markOne correct option

The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

Based on the above data, answer the given subquestions.

For the subgoal ordering given in the goal description (and using the given tie breaking rules), which of the following is the first action popped out of the stack in Goal Stack Planning?

  1. A

    Putdown(A)

  2. B

    Pickup(B)

  3. C

    Stack(B,C)

  4. D

    Stack(A,B)

  5. E

    Unstack(C,D)

Show answer

Correct answer

  • A

    Putdown(A)

Question 24 on its own page

Question 25

+1 markOne correct option

The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

Based on the above data, answer the given subquestions.

For the subgoal ordering given in the goal description (and using the given tie breaking rules), does the Goal Stack Planning algorithm find an optimal plan?

  1. A

    Yes

  2. B

    No

  3. C

    Cannot be determined

Show answer

Correct answer

  • B

    No

Question 25 on its own page

Question 26

+1 markOne correct option

The domain description of a blocks-world with a single one-armed robot is provided below. Note: this is the same domain description used in the weekly assignments.

Based on the above data, answer the given subquestions.

If the subgoals in the goal description are swapped places then does the Goal Stack Planning algorithm find an optimal plan?

  1. A

    Yes

  2. B

    No

  3. C

    Cannot be determined

Show answer

Correct answer

  • A

    Yes

Question 26 on its own page