Question 4 10 pts Select all the statements below which are TRUE: If BELLMAN-FOR

Question

Question 4 10 pts Select all the statements below which are TRUE: If BELLMAN-FORD(G,w,s) returns FALSE, then it means that the graph G has a negative-weight cycle reachable from s. Let G be an undirected graph. Then running Depth-First Search (DFS) on G can result in cross edges. To show that a greedy algorithm always yields an optimal solution, we need to prove the greedy-choice property. We do not need to prove the optimal substructure property O Let G be an undirected graph. In the adjacency-list representation of G, the sum of the lengths of adjacency lists is E In the worst-case, the height of a Binary Search Tree (BST) is O(n), where n is the number of nodes in the tree hA.

Explanation / Answer

statement 1 is True.

statement 2 is False. Edge is either a tree edge or back edge.

statement 3 is False. Both property required.

statement 4 is False. It is 2|E|

statement 5 is True.

statement 6 is True

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.