CS502 Quiz 4 Set 2 by VU Topper RM

For each vertex u ϵ (V − S) ,we associate a key ____________. A. key[v-s] B. key[s] C.

key[u]

D. key[v]

In Kruskal’s algorithm, the vertices will be stored in ________. A. loops B.

sets

C. nodes D. links

An edge (u, v) _______ E − A is safe if A _______{(u, v)} is viable. A. ϵ,U B. U,ϵ C.

ϵ,П

D. П,U

Which of the following statement is true. A. Kruskal’s algorithm is used to find minimum spanning tree of a graph, time complexity of this algorithm is O(EV) B. Kruskal algorithm is multiple source technique for finding MST. C. Both I and II D. Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best Tree edge) when the graph has relatively few edges

Q1. Vu-Topper RM (1 marks)

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

B. Bellman-Ford Page 159

C. Dijkstra’s D. Print

Q2. Vu-Topper RM (1 marks)

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

Q3. Vu-Topper RM (1 marks)

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

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

D. Θ((V+E)logE)

Q4. Vu-Topper RM (1 marks)

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

Q5. Vu-Topper RM (1 marks)

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

Q6. Vu-Topper RM (1 marks)

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

Q7. Vu-Topper RM (1 marks)

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

Q8. Vu-Topper RM (1 marks)

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

Q9. Vu-Topper RM (1 marks)

Dijkstra’s algorithm : 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.

Q10. Vu-Topper RM (1 marks)

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)