CS502 Quiz 4 Set 3 by VU Topper RM

______________ Algorithm allows negative weights edges and no negative cost cycles. A. Brute-force technique

B. Bellman-Ford Page 159

C. Dijkstra’s D. Print

In Prim's algorithm, we start with the _______ vertex r; it can be any vertex.

A. Root Page 149

B. Pivot C. Leaf D. Negative

Overall Running time of Prim's algorithm is _______. A. Θ(ElogE) B. Θ(ElogV)

C. Θ((V+E)logV) Page 152

D. Θ((V+E)logE)

Problems such as the shortest route between cities can be solved efficiently by modeling the road map as a______________. A. Tree B. Stack

C. Graph Google

D. Linked list

In Kruskal's algorithm, the next edge is added to viable set A, if its adding does not induce a/an __________ . A. Tree B. Edge

C. Cycle Page 147

D. Vertex

Bellman-Ford algorithm is used to solve ____________ problems. A. Flow of networking B. All pair shortest path

C. Single source shortest path Google

D. Double source shortest path

In Prim's algorithm, If the color of a vertex is __________,then it is in S otherwise not. A. Blue B. Gray

C. Black Page 151

D. White

Keeping in mind the shortest-path, if given scenarios occur in computer networks like the internet where data packets have to be routed. The vertices are_________and Edges are _____________which may be wired or wireless. A. Internet, routers B. Routers, internet C. Communication links, routers

D. Routers, communication links Page 153

A. Has greedy approach to find all shortest paths B. Has both greedy and Dynamic approach to find all shortest paths C. Has greedy approach to compute single source shortest paths to all other vertices Page 154 D. Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.

In Dijkstra’s algorithm, initially the estimated value from source vertex to any vertex v is: A. One (1) B. Zero (0)

C. Infinity (∞) Page 154

D. Minus one (-1)

From the given option’s which one is correct regarding the time complexity of Dijkstra’s algorithm: A. O(N)

B. O(N^2) Google

C. O(N^3) D. O(log N)

In Bellman-Ford Algorithm, relaxation applies to ____________ of the graph.

A. Every edge Page 159

B. Every Vertices C. Only First edge D. Only First Vertices

The key[u] is the weight of the __________ going from u to any vertex in S. A. Edge B. lighter edge

C. lightest edge Page 151

D. heavier edge

In Bellman-Ford Algorithm, path consists of at most _________ edges.

A. V-1 Page 160

B. E+1 C. V+1 D. E-1

Overall time for Kruskal algorithm is: A. Θ(logE) B. Θ(VlogE)

C. Θ(ElogV) Page 149

D. Θ(ElogE)

A graph may contain ------------------------. A. No MST B. One or zero MST C. Exactly one MST

D. More than one MST Google

In which algorithm, information of shortest path is propagated sequentially along each shortest path in the graph.