**1) Which of the following algorithm(s) always terminate(s) on a finite search space? **

a) DFS

b) BFS

c) DFID

d) None of the above

Answer(s) : a) DFS b) BFS c) DFID

**2) Which of the following search algorithm(s) always find(s) a path to the goal (if there exists one) in a finite search space. **

a) DFS

b) BFS

c) DFID

d) None of the above.

Answer(s) : a) DFS b) BFS c) DFID

**3) Which of the following search algorithm(s) always find(s) a path to the goal (if there exists one) in an infinite search space. **

a) DFS

b) BFS

c) DFID

d) None of the above.

Answer(s) : b) BFS c) DFID

**4) Mark the algorithm(s) for which space requirements grow linearly with depth. **

a) DFS

b) BFS

c) DFID

d) None of the above.

Answer(s) : a) DFS c) DFID

**5) Mark the algorithm(s) that always find(s) the shortest path from start state to goal state in any search space. **

a) DFS

b) BFS

c) DFID

d) None of the above.

Answer(s) : b) BFS c) DFID

**6) Which data-structures are used by the search algorithms, DFS and BFS, respectively? **

a) Queue, Stack

b) Tree, Stack

c) Queue, Tree

d) Stack, Queue

Answer(s) : d) Stack, Queue

**7) Which of the following is/are configuration problem(s)?**

a) Travelling Salesman Problem (TSP)

b) 8-Puzzle

c) Boolean Satisfiability Problem (SAT)

d) 5-Queens

e) Rubik’s Cube

f) ‘Man, Lion, Goat, Cabbage’ Problem

Answer(s) : a) Travelling Salesman Problem (TSP) c) Boolean Satisfiability Problem (SAT) d) 5-Queens

**8) The 8-Puzzle problem has been discussed in the class. What would be the minimum number of moves required to bring tiles 1 and 2 to their correct positions in the goal state for the configuration shown in Figure 2.1? **

Answer(s) : 6

**9) The ‘Man, Lion, Goat, Cabbage’ problem has been discussed in the class. Mark the state(s) returned by the moveGen function for state ((MLC)(G)). The first list corresponds to the left bank of the river and the second list corresponds to the right bank of the river.**

a) ((LC) (MG))

b) ((C) (MLG))

c) ((L) (MCG))

d) ((MG) (LC))

Answer(s) : a) ((LC) (MG)) b) ((C) (MLG)) c) ((L) (MCG))

Figure 2.2 depicts a search space in which the nodes are labeled with names like A, B, A1, B1. Node S is the start node. The goal nodes are drawn as square boxes and the other nodes in circles.

**10) List the order in which the Depth First Search algorithm explores the graph till termination, searching from left to right. **

Answer(s) : S,A,D,K,U,V,L,W

**11) What is the path found by the algorithm in the previous question? (Use the above Fig 2.2)**

Answer(s) : S,A,D,L,W

**12) List the order in which the Depth First Search algorithm explores the graph till termination, searching from right to left. (Use the above Fig 2.2)**

Answer(s) : S,C,J,T,J1,I1

**13) What is the path found by the algorithm in the previous question?(Use the above Fig 2.2)**

Answer(s) : S,C,J,T,I1

**14) List the order in which the Breadth First Search algorithm explores the graph till termination, searching from left to right.(Use the above Fig 2.2)**

Answer(s) : S,A,B,C,D,E,F,G

**15) What is the path found by the algorithm in the previous question?(Use the above Fig 2.2)**

Answer(s) : S,B,G

**16) List the order in which the Depth First Iterative Deepening (DFID) algorithm explores the graph till termination, searching from left to right.(Use the above Fig 2.2)**

Answer(s) : S,S,A,B,C,S,A,D,E,B,F,G

**17) What is the path found by the algorithm in the previous question?(Use the above Fig 2.2)**

Answer(s) : S,B,G

## 3 Comments

## SHAUNAK BHATTACHARJEE · August 13, 2017 at 4:42 PM

Thanks. Can you please post the solution of Week 3 as well for AI Search methods? 14th August is the last date. Thanks!

## tony · August 17, 2017 at 7:56 PM

need help with week 4 for the AI assignment

## hank · August 20, 2017 at 6:01 PM

the assignment 4 solutions would be very helpful.

thank you for the first two.