CS502 Quiz # 4 spring 2012( current)

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 32 sec(s) Question # 1 of 10 ( Start time: 07:15:26 PM ) Total Marks: 1 The relationship between number of back edges and number of cycles in DFS is, Select correct option: Both are equal Back edges are half of cycles Back edges are one quarter of cycles There is no relationship between no. of edges and cycles

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 6 sec(s) Question # 2 of 10 ( Start time: 07:16:53 PM ) Total Marks: 1 What algorithm technique is used in the implementation of Kruskal solution for the MST? Select correct option: Greedy Technique Divide-and-Conquer Technique Dynamic Programming Technique The algorithm combines more than one of the above techniques v:shapes="_x0000_i1036"> Saving...

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 3 sec(s) Question # 3 of 10 ( Start time: 07:18:27 PM ) Total Marks: 1 There is relationship between number of back edges and number of cycles in DFS Select correct option: Both are equal. Cycles are half of back edges. Cycles are one fourth of back edges. There is no relationship between back edges and number of cycles. v:shapes="_x0000_i1046">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 47 sec(s) Question # 4 of 10 ( Start time: 07:20:05 PM ) Total Marks: 1 Dijkstra’s algorithm : Select correct option: Has greedy approach to find all shortest paths Has both greedy and Dynamic approach to find all shortest paths Has greedy approach to compute single source shortest paths to all other vertices Has both greedy and dynamic approach to compute single source shortest paths to all other vertices. v:shapes="_x0000_i1056"> Saving...

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 6 sec(s) Question # 5 of 10 ( Start time: 07:20:58 PM ) Total Marks: 1 Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few edges. Select correct option: True False v:shapes="_x0000_i1066">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 11 sec(s) Question # 6 of 10 ( Start time: 07:22:40 PM ) Total Marks: 1 What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm? Select correct option: log (V) V.V E.E log (E) v:shapes="_x0000_i1072">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 2 sec(s) Question # 7 of 10 ( Start time: 07:24:10 PM ) Total Marks: 1 You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.? Select correct option: ? (V + E) ? (V E) ? (V) ? (V^2) v:shapes="_x0000_i1082">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 0 sec(s) Question # 8 of 10 ( Start time: 07:25:48 PM ) Total Marks: 1 A digraph is strongly connected under what condition? Select correct option: A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v . A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa. A digraph is strongly connected if for at least one pair of vertex u, v e V, u can reach v and vice versa. A digraph is strongly connected if at least one third pair of vertices u, v e V, u can reach v and vice versa. v:shapes="_x0000_i1092"> Saving...

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 45 sec(s) Question # 9 of 10 ( Start time: 07:27:25 PM ) Total Marks: 1 You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ? Select correct option: (V+E) V.E V E

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 51 sec(s) Question # 10 of 10 ( Start time: 07:28:23 PM ) Total Marks: 1 What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm? Select correct option: O (log E) ? (V) ? (V+E) O (log V) Saving...