edited by
2,852 views
0 votes
0 votes

Consider the following terminology and match List I with List II and choose the correct answer from the code given below.

b= branching factor

d = depth of the shallowest solution

m= maximum depth of the search tree

l=depth limit

$\begin{array} \textbf{List I} & \textbf{(Algorithms)} & \textbf{List II} & \textbf{(Space Complexity)} \\ (a) & \text{BFS search} & (i) & O(bd) \\ (b) & \text{DFS search} & (ii) &  O(b^d) \\ (c ) &  \text{Depth-limited search} & (iii) & O(bm) \\ (d) & \text{Iterative deepening search} & (iv) & O(bl) \end{array}$

Code:

  1. (a) – (i), (b)-(ii), (c)-(iv), (d)-(iii)
  2. (a) – (ii), (b)-(iii), (c)-(iv), (d)-(i)
  3. (a) – (iii), (b)-(ii), (c)-(iv), (d)-(i)
  4. (a) – (i), (b)-(iii), (c)-(iv), (d)-(ii)
edited by

3 Answers

1 votes
1 votes

All these things are related to DFS & BFS and question is based on space complexity of those.

Answer :-

BFS → O(bd) worst case space complexity
DFS → O(bm) worst case space complexity
Depth - Limited Search → O(bl)
Iterative deepening Search → O(bd)

Some point which help you ------

Branching factor - The average number of children of the nodes in the space.

Solution depth - The length of the shortest path from the initial node to a goal node.

Maximum depth -  The maximum number of nodes along the longest path from the root node down to the farthest leaf node

Depth limit - The unbounded tree problem appeared in DFS can be fixed by imposing a limit on the depth that DFS can reach, this limit we will call depth limit.

0 votes
0 votes

The space complexity of BFS is O(b^d).

So answer must be B.

Unlike BFS, Depth-limited search algorithm has a very modest memory requirements, it needs to store only the path from the root to the leaf node, beside the siblings of each node on the path. DLS requires storage of only O(bl) nodes thus space complexity is O(bl).

 

Related questions

1 votes
1 votes
0 answers
3
0 votes
0 votes
2 answers
4
Arjun asked Jan 2, 2019
4,324 views
Consider the graph shown below:Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is$17$$14$$16$$13$