Virtual Labs

What happens when visited nodes are not kept track of in DFS?

a: The DFS algorithm will still find the optimal solution. Explanation

Explanation

b: The DFS algorithm may get stuck in an infinite loop. Explanation

Explanation

c: The DFS algorithm will terminate but may not find the optimal solution. Explanation

Explanation

d: The DFS algorithm will be faster but may miss some nodes. Explanation

Explanation

e: The DFS algorithm will not work at all and fail to find any solution. Explanation

Explanation

Assuming that nodes at the same depth as the goal node have no successors, what is the space complexity of DFS? (Here b is the branching factor and d is the depth of the goal node)

a: O(b^d) Explanation

Explanation

b: O(bd) Explanation

Explanation

c: O(b+d) Explanation

Explanation

d: O(blog(d)) Explanation

Explanation

What if a FIFO queue is used instead of a LIFO queue (stack) in DFS?

a: The algorithm becomes more memory efficient. Explanation

Explanation

b: The algorithm would become equivalent to BFS (Breadth First Search) Explanation

Explanation

c: The algorithm would not work properly, i.e, it will not traverse the graph properly and/or completely Explanation

Explanation

d: No change in the algorithm, i.e, it remains unaffected Explanation

Explanation

Iterative Deepening Depth First Search (IDDFS) is a variation of DFS in which search is performed using a series of depth-limited DFS iterations. It starts with a depth limit of 0 and performs a DFS with that limit. If the solution is not found, it incrementally increases the depth limit by 1 and performs another DFS and so on. Which of the following is true about IDFFS?

a: Not complete, not optimal, O(bd) space complexity, O(b^d) time complexity Explanation

Explanation

b: Complete, not optimal, O(b^d) space complexity, O(b^d) time complexity Explanation

Explanation

c: Not complete, optimal, O(bd) space complexity, O(bd) time complexity Explanation

Explanation

d: Complete, optimal, O(bd) space complexity, O(b^d) time complexity Explanation

Explanation