1. The time and space complexity of BFS is (For time and space complexity problems consider b as branching factor and d as depth of the search tree.)
a) O(bd+1) and O(bd+1)
b) O(b2) and O(d2)
c) O(d2) and O(b2)
d) O(d2) and O(d2)
Explanation: We consider a hypothetical state space where every state has b successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. Now suppose that the solution is at depth d. In the worst case, we would expand all but the last node at level d (since the goal itself is not expanded), generating bd+1- b nodes at level d+1.
2. Breadth-first search is not optimal when all step costs are equal, because it always expands the shallowest unexpanded node.
a) true
b) false
Explanation: Breadth-first search is optimal when all step costs are equal, because it always expands the shallowest unexpanded node. If the solution exists in shallowest node no irrelevant nodes are expanded.
3. uniform-cost search expands the node n with the __________
a) Lowest path cost
b) Heuristic cost
c) Highest path cost
d) Average path cost
Explanation: Uniform-cost search expands the node n with the lowest path cost. Note that if all step costs are equal, this is identical to breadth-first search.
4. Depth-first search always expands the ______ node in the current fringe of the search tree.
a) Shallowest
b) Child node
c) Deepest
d) Minimum cost
Explanation: Depth-first search always expands the deepest/leaf node in the current fringe of the search tree.
5. Breadth-first search always expands the ______ node in the current fringe of the search tree.
a) Shallowest
b) Child node
c) Deepest
d) Minimum cost
Explanation: Breadth-first search always expands the shallowest node in the current fringe of the search tree. Traversal is performed level wise.
6. Optimality of BFS is ___________
a) When there is less number of nodes
b) When all step costs are equal
c) When all step costs are unequal
d) None of the mentioned
Explanation: It always expands the shallowest unexpanded node.
7. LIFO is ______ where as FIFO is ________
a) Stack, Queue
b) Queue, Stack
c) Priority Queue, Stack
d) Stack. Priority Queue
Explanation: LIFO is last in first out – Stack. FIFO is first in first out – Queue.
8. For general graph, how one can get rid of repeated states?
a) By maintaining a list of visited vertices
b) By maintaining a list of traversed edges
c) By maintaining a list of non-visited vertices
d) By maintaining a list of non-traversed edges
Explanation: Other techniques are costly.
9. DFS is ______ efficient and BFS is __________ efficient.
a) Space, Time
b) Time, Space
c) Time, Time
d) Space, Space
Explanation: Space, Time
10. The main idea of Bidirectional search is to reduce the time complexity by searching two way simultaneously from start node and another from goal node.
a) true
b) false
Explanation: The idea behind bidirectional search is to run two simultaneous searches-one forward from the initial state and the other backward from the goal, stopping when the two searches meet in the middle. The motivation is that bd/2 + bd/2 is much less than bd.