Search Algorithms Quiz

What is the time and space complexity of Breadth-First Search (BFS)?

• O(b^d)

• O(d)

• O(b^d) and O(b^d)

• O(b^d) and O(b)

Answer explanation

BFS explores all nodes at the present depth before moving on to nodes at the next depth level. The time complexity is O(b^d) where b is the branching factor and d is the depth of the tree. The space complexity is also O(b^d) due to storing nodes.

What is the main characteristic of Depth-First Search (DFS)?

• Explores all nodes at the current depth

• Explores as deep as possible in one branch

• Uses a queue data structure

• Guarantees the shortest path

Answer explanation

The main characteristic of Depth-First Search (DFS) is that it explores as deep as possible in one branch before backtracking, making it distinct from other search strategies like Breadth-First Search.

What does Depth-Limited Search (DLS) prevent?

• Infinite loops

• Optimal solutions

• Memory usage

• Local optima

Answer explanation

Depth-Limited Search (DLS) prevents infinite loops by limiting the depth of the search. This ensures that the algorithm does not get stuck in cycles, making it effective for exploring deep but finite search spaces.

What is the time complexity of Uniform Cost Search (UCS)?

• O(b^d)

• O(d)

• O(b^d) and O(d)

• O(b)

Answer explanation

Uniform Cost Search (UCS) explores the least cost path first, leading to a time complexity of O(b^d), where b is the branching factor and d is the depth of the shallowest goal. Thus, the correct answer is O(b^d).

What is the time complexity of Greedy Best-First Search?

• O(b^d)

• O(d)

• O(b^d) and O(d)

• O(b)

Answer explanation

The time complexity of Greedy Best-First Search is O(b^d), where b is the branching factor and d is the depth of the shallowest goal. This is because it explores all nodes at each depth level, leading to exponential growth.

What does A* Search guarantee if h(n) is admissible?

• Optimal solution

• Suboptimal solution

• Local optima

• Infinite loops

Answer explanation

A* Search guarantees an optimal solution when the heuristic function h(n) is admissible, meaning it never overestimates the true cost to reach the goal. This ensures that the best path is always found.

What does Bidirectional Search significantly reduce?

• Time complexity

• Space complexity

• Memory usage

• Optimal solutions

Answer explanation

Bidirectional Search significantly reduces time complexity by simultaneously searching from both the start and goal nodes, effectively halving the search space and leading to faster solutions compared to unidirectional search.

What is the primary advantage of using Greedy Search algorithms?

• Always finds the optimal solution

• Uses less memory

• Provides a quick solution

• Reduces time complexity

Answer explanation

The primary advantage of Greedy Search algorithms is that they provide a quick solution by making locally optimal choices at each step, which often leads to faster results compared to other methods, even if they don't guarantee the best overall solution.

What is the main limitation of Breadth-First Search (BFS)?

• Only works for unweighted graphs

• Slow execution time

• High memory usage

• Cannot find the shortest path

Answer explanation

The main limitation of BFS is its high memory usage, as it stores all nodes at the current level before moving to the next. This can lead to significant memory consumption, especially in wide graphs.

Which search algorithm is best suited for finding the shortest path in a weighted graph?

• Depth-First Search

• Bidirectional Search

• Uniform Cost Search

• Greedy Best-First Search

Answer explanation

Uniform Cost Search is best for finding the shortest path in a weighted graph because it expands the least costly node first, ensuring that the first time it reaches a node, it has found the shortest path to that node.