The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.3k views

Which of the following statements is false?

  1. Optimal binary search tree construction can be performed efficiently using dynamic programming

  2. Breadth-first search cannot be used to find connected components of a graph

  3. Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.

  4. Depth-first search can be used to find connected components of a graph

asked in Algorithms by Veteran (52k points)
retagged by | 2.3k views
+3
I think B should be connected components in place of converted components.
0

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum. for more information click here

5 Answers

+12 votes
Best answer

Answer is $B$.

  1. True.
  2. False.
  3. True.
  4. True.
answered by Boss (33.8k points)
edited by
+4
Elaborate (a) part..
0
anybody explain A part
0
explain this "Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed."
+1
Without inorder we can't  construct binary tree.
0
Inorder of a bonarbtree can be obtain from sorted sequence right ? Then why option c is true.
0
@Chintan Patel  That will be in case of binary search tree not in binary tree
0
got it bro tq !!
+6 votes
Answer B, We can randomly select a source vertex and run BFS algorithm, after that we need to check each vertex whether it's distance from source is still infinite or not(note: BFS algorithm first initializes each vertex's distance  from source as infinite and source's distance as 0) . If we find any vertex  having infinite distance then the graph is not connected(Assuming the graph is undirected)
answered by Active (2.4k points)
–1
For directed graph Dfs is also applied in most cases ...
0
How?
+5 votes

https://gateoverflow.in/113167/ugcnet-dec2016-ii-25 

Refer this link for the explanation 

answered by Active (1.3k points)
+4 votes

$A.$ An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum and it can be performed efficiently using Dynamic programming.click here

                          when $j\geq i $ $\bigg\{E = E[i,r-1] + E[r+1,j] + W(i,j)\bigg\} $

                            when $j\geq i $ $\Big\{W(i,j) = \Sigma^j_{l=i} p_l + \Sigma^l_{l=i-1} q_l \Big\}$

$B.$ To find Connected components we can start with either BFS or DFS but DFS is preffered over BFS because BFS takes exponential amount of memory whereas DFS takes linear amount of memory

$C.$ Using prefix and postfix the binary tree cannot be uniquely constructed check here

$D.$ It can be used and it consumes linear amount of memory 

So $B$ is right answer

answered by Boss (10.5k points)
edited by
+1 vote

Option B is false. We can use BFS to find connected components.  

https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

answered by Active (3.9k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,540 questions
54,100 answers
187,271 comments
71,007 users