Please zoom in if image is not visible Select all the statements below which are

Question

Please zoom in if image is not visible

Select all the statements below which are TRUE: To show that a greedy algorithm always yields an optimal solution, we need to prove (i) the optimal substructure property, and (ii) the greedy-choice property. Dijkstra's algorithm can be used to compute single-source shortest paths when all edges have nonnegative weights. We are given two sequences: X with length 7 and Y with length 4. There are cases when the length of a Longest Common Subsequence (LCS) of X and Y is 5. Let G be a directed graph. In the adjacency-list representation of G, the sum of the lengths of adjacency lists is 2|E|. Let v be a vertex in the graph G. If v.d = infinity after we run Breadth First Search algorithm BFS(G.s), then it means that v is not reachable from the source vertex s. Let x be a node in a Binary Search Tree. If z is a node in the left subtree of x, then z.key lessthanorequalto x.key.

Explanation / Answer

1, True

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

2. True

Yes it is used to find only a single path

3. False

There can be multiple possibilities not only 5.

4. False

When a directed graph has an adjacent edges, the length will be E only as its parallel.

5. True

v.d= infinity,

v= infinity/d = infinity.

Here d is depth of the graph

6. False

It is actually z key > x key as Z will have a larger key index value as its depth is larger than X’s depth

Hope your question has been resloved now. Please do not forget to give a positive like to the answer. Thank you.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---