Which of the following statements is false ?

Correct answer: Breadth-first search cannot be used to find connected components of a graph. is false because breadth-first search can be used to find connected components.

• Optimal binary search tree construction can be performed efficiently using dynamic programming: True. Dynamic programming computes the minimum expected search cost for all key intervals and chooses optimal roots. The basic DP is O(n^3); with Knuth optimization it can be improved to O(n^2).

• Breadth-first search cannot be used to find connected components of a graph: False. For an undirected graph, repeatedly run BFS from any unvisited vertex to mark all vertices in that component; repeat until all vertices are visited. This identifies all connected components in O(V + E) time.

• Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely: True in general. Preorder and postorder traversals alone can be ambiguous (for example, nodes with a single child can be arranged left or right and produce the same traversals). Reconstruction becomes unique with extra information, for example if the tree is known to be full or if inorder traversal is available.

• Depth-first-search can be used to find the connected components of a graph: True. DFS from each unvisited vertex discovers all vertices in that component; repeating until all vertices are visited finds every connected component in O(V + E) time.

Simple algorithm sketch to find connected components using BFS or DFS:

1. Initialize all vertices as unvisited.

2. For each vertex that is unvisited, start a BFS or DFS from it and mark all reachable vertices as visited; those vertices form one connected component.

3. Repeat until all vertices are visited. Total runtime is O(V + E).