Day 7

Question 1

Depth-first search is a recursive algorithm for traversing a tree or graph data structure

Question 2

o It is called the depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path

Answer 2

o It is called the depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path

Question 3

Advantages of DFS:

Answer 3

DFS requires very less memory as it only needs to store a stack of the nodes on the path from root node to the current node.

Question 4

Advantages of DFS:

Answer 4

It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path).

Question 5

Disadvantages of DFS

Answer 5

There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution

Question 6

Disadvantages of DFS

Answer 6

DFS algorithm goes for deep down searching and sometimes it may go to the infinite loop.

Question 7

The process of the DFS algorithm is similar to the BFS algorithm.

Answer 7

صح

Question 8

DFS uses a stack data structure for its implementation

Answer 8

DFS uses a stack data structure for its implementation

Question 9

A variant of depth-first search called backtracking search uses even less memory.

Answer 9

A variant of depth-first search called backtracking search uses even less memory.

Question 10

Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the algorithm. It is given by:
T(n)= 1+ n2+ n3 +………+ n^m=O(n^m)

Answer 10

Where, m= maximum depth of any node and this can be much larger than d (Shallowest solution depth)

Question 11

Space Complexity: DFS algorithm needs to store only single path from the root node, hence space complexity of DFS is equivalent to the size of the fringe set, which is O(bm)

Answer 11

Space Complexity: DFS algorithm needs to store only single path from the root node, hence space complexity of DFS is equivalent to the size of the fringe set, which is O(bm)

Question 12

Completeness: DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree. In infinite state spaces, depth-first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete.

Answer 12

Completeness: DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree. In infinite state spaces, depth-first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete.

Question 13

Optimality: DFS search algorithm is non-optimal, as it may generate a large number of steps or high cost to reach to the goal node

Answer 13

Optimality: DFS search algorithm is non-optimal, as it may generate a large number of steps or high cost to reach to the goal node

Question 14

o A depth-limited search algorithm is similar to depth-first search with a predetermined limit ℓ. Depth-limited search can solve the drawback of the infinite path in the Depth-first search. In this algorithm, the node at the depth limit will treat as it has no successor nodes further

Answer 14

o A depth-limited search algorithm is similar to depth-first search with a predetermined limit ℓ. Depth-limited search can solve the drawback of the infinite path in the Depth-first search. In this algorithm, the node at the depth limit will treat as it has no successor nodes further

Question 15

Depth-limited search can be terminated with two Conditions of failure:
➢Standard failure value: It indicates that problem does not have any solution.
➢Cutoff failure value: It defines no solution for the problem within a given depth limit

Question 16

Advantages of depth-limited search

o Depth-limited search is Memory efficient.

Question 17

Time Complexity: Time complexity of DLS algorithm is O(bℓ).

Answer 17

Time Complexity: Time complexity of DLS algorithm is O(bℓ).

Question 18

Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).

Answer 18

Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).

Question 19

Completeness: DLS search algorithm is complete if the solution is above the depth-limit

Answer 19

Completeness: DLS search algorithm is complete if the solution is above the depth-limit

Question 20

The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found.

Answer 20

The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found.

Question 21

This algorithm performs depth-first search up to a certain “depth limit”, and it keeps increasing the depth limit after each iteration until the goal node is found.

Question 22

The iterative search algorithm is useful uninformed search when search space is large, and depth of goal node is unknown.

Question 23

It combines the benefits of BFS and DFS search algorithm in terms of fast search and memory efficiency

Question 24

The main drawback of IDDFS is that it repeats all the work of the previous phase.

Question 25

Bidirectional search algorithm runs two simultaneous searches, one form initial state called as forward-search and other from goal node called as backward-search, to find the goal node. The search stops when these two graphs intersect each other

Question 26

Bidirectional search replaces one single search graph with two small subgraphs in which one starts the search from an initial vertex and other starts from goal vertex

Question 27

Advantages
o Bidirectional search is fast.
o Bidirectional search requires less memory

Question 28

Disadvantages
o Implementation of the bidirectional search tree is difficult.
o In bidirectional search, one should know the goal state in advance.

Question 29

Bidirectional search can use search techniques such as BFS, DFS, DLS, etc