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
