Cs502 Quiz NO 2 31-january-2018 (Today)
Cs502 Fundamentals of Algorithms Quiz # 2
1st
The running time of quick sort depends heavily on the selection of
No of inputs
No of inputs
Arrangement of elements in array
Size o elements
Pivot element (Right Answer)
In stable sorting algorithm
One array is used
In which duplicating elements are not handled.
More then one arrays are required.
Duplicating elements remain in same relative position after sorting. (Right Answer)
Which sorting algorithn is faster :
O(n^2)
O(nlogn)
O(n+k) (Right Answer)
O(n^3)
In Quick sort algorithm,constants hidden in T(n lg n) are
Large
Large
Medium
Not known
Small (Right Answer)
Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
There is explicit combine process as well to conquer the solutin. (Right Answer)
There is explicit combine process as well to conquer the solutin. (Right Answer)
No work is needed to combine the sub-arrays, the array is already sorted
Merging the subarrays
None of above.
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 cycle (Right Answer)
You have an adjacency list for G, what is the time complexity to compute Graph
transpose G^T ?
Select correct option:
(V+E) (Right Answer)
V.E
V
E
Question # 3 of 10 ( Start time: 06:54:27 PM ) Total Marks: 1
You have an adjacency list for G, what is the time complexity to compute Graph
transpose G^T.?
?(V + E) Right Answer)
?(V E)
?(V)
?(V^2)
What is the time complexity to extract a vertex from the priority queue in Prim's
algorithm?
Select correct option:
log (V) (Right Answer)
V.V
E.E
log (E)
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 (Right Answer)
Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.
2nd
Question # 1 of 10 ( Start time: 10:32:32 PM ) Total Marks: 1
In digraph G=(V,E) ;G has cycle if and only if
Select correct option:
The DFS forest has forward edge.
The DFS forest has back edge Ans
The DFS forest has both back and forward edge
BFS forest has forward edge
In digraph G=(V,E) ;G has cycle if and only if
Select correct option:
The DFS forest has forward edge.
The DFS forest has back edge Ans
The DFS forest has both back and forward edge
BFS forest has forward edge
Question # 2 of 10 ( Start time: 10:33:20 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. Ans
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.
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. Ans
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.
Question # 4 of 10 ( Start time: 10:33:59 PM ) Total Marks: 1
In strong components algorithm, the form of graph is used in which all the _________ of original graph G have been reversed in direction.
Select correct option:
Vertices
Edges Ans
Both edges & vertices
None of the above
In strong components algorithm, the form of graph is used in which all the _________ of original graph G have been reversed in direction.
Select correct option:
Vertices
Edges Ans
Both edges & vertices
None of the above
Question # 5 of 10 ( Start time: 10:34:33 PM ) Total Marks: 1
According to parenthesis lemma, vertex u is a descendent of v vertex if and only if;
Select correct option:
[d[u], f[u]] ⊆ [d[v], f[v]] Ans
[d[u], f[u]] ⊇ [d[v], f[v]]
Unrelated
Disjoint
According to parenthesis lemma, vertex u is a descendent of v vertex if and only if;
Select correct option:
[d[u], f[u]] ⊆ [d[v], f[v]] Ans
[d[u], f[u]] ⊇ [d[v], f[v]]
Unrelated
Disjoint
Question # 6 of 10 ( Start time: 10:35:12 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) Ans
? (V E)
? (V)
? (V^2)
You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.?
Select correct option:
? (V + E) Ans
? (V E)
? (V)
? (V^2)
Question # 7 of 10 ( Start time: 10:35:39 PM ) Total Marks: 1
For undirected graph, there is no distinction between forward and back edges.
Select correct option:
True Ans
False
For undirected graph, there is no distinction between forward and back edges.
Select correct option:
True Ans
False
Question # 8 of 10 ( Start time: 10:36:00 PM ) Total Marks: 1
In Generic approach determining of Greedy MST, we maintain a subset A of __________ .
Select correct option:
Edges Ans
Vertices
Cycles
Paths
In Generic approach determining of Greedy MST, we maintain a subset A of __________ .
Select correct option:
Edges Ans
Vertices
Cycles
Paths
Question # 9 of 10 ( Start time: 10:36:22 PM ) Total Marks: 1
Kruskal’s algorithm works by adding ________ in increasing order of weight (lightest edge first).
Select correct option:
Vertices
Edges Ans
Trees
Weights
Kruskal’s algorithm works by adding ________ in increasing order of weight (lightest edge first).
Select correct option:
Vertices
Edges Ans
Trees
Weights
Question # 10 of 10 ( Start time: 10:36:42 PM ) Total Marks: 1
What algorithm technique is used in the implementation of Kruskal solution for the MST?
Select correct option:
Greedy Technique Ans
Divide-and-Conquer Technique
Dynamic Programming Technique
The algorithm combines more than one of the above techniques
What algorithm technique is used in the implementation of Kruskal solution for the MST?
Select correct option:
Greedy Technique Ans
Divide-and-Conquer Technique
Dynamic Programming Technique
The algorithm combines more than one of the above techniques
3rd
Question # 1 of 10 ( Start time: 10:23:08 PM ) Total Marks: 1
Adding any edge to a free tree creates a unique cycle.
Select correct option:
True Ans
False
Adding any edge to a free tree creates a unique cycle.
Select correct option:
True Ans
False
Question # 2 of 10 ( Start time: 10:23:52 PM ) Total Marks: 1
Forward edge is:
Select correct option:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree. Ans
(u, v) where v is a proper ancesstor of u in the tree.
(u, v) where u is a proper ancesstor of v in the tree.
Forward edge is:
Select correct option:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree. Ans
(u, v) where v is a proper ancesstor of u in the tree.
(u, v) where u is a proper ancesstor of v in the tree.
Question # 3 of 10 ( Start time: 10:25:10 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. Ans
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. Ans
Question # 4 of 10 ( Start time: 10:25:31 PM ) Total Marks: 1
In undirected graph, by convention all the edges are called _________ edges.
Select correct option:
Forward
Back Ans
Cross
Both forward and back
In undirected graph, by convention all the edges are called _________ edges.
Select correct option:
Forward
Back Ans
Cross
Both forward and back
Question # 5 of 10 ( Start time: 10:26:38 PM ) Total Marks: 1
For undirected graph, there is no distinction between forward and back edges.
Select correct option:
True Ans
False
For undirected graph, there is no distinction between forward and back edges.
Select correct option:
True Ans
False
Question # 6 of 10 ( Start time: 10:26:55 PM ) Total Marks: 1
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle Ans
Strong component
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle Ans
Strong component
Question # 7 of 10 ( Start time: 10:27:09 PM ) Total Marks: 1
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
Question # 8 of 10 ( Start time: 10:27:23 PM ) Total Marks: 1
In strong components algorithm, the form of graph is used in which all the _________ of original graph G have been reversed in direction.
Select correct option:
Vertices
Edges Ans
Both edges & vertices
None of the above
In strong components algorithm, the form of graph is used in which all the _________ of original graph G have been reversed in direction.
Select correct option:
Vertices
Edges Ans
Both edges & vertices
None of the above
Question # 9 of 10 ( Start time: 10:28:31 PM ) Total Marks: 1
According to parenthesis lemma, vertex u is a descendent of v vertex if and only if;
Select correct option:
[d[u], f[u]] ⊆ [d[v], f[v]] Ans
[d[u], f[u]] ⊇ [d[v], f[v]]
Unrelated
Disjoint
According to parenthesis lemma, vertex u is a descendent of v vertex if and only if;
Select correct option:
[d[u], f[u]] ⊆ [d[v], f[v]] Ans
[d[u], f[u]] ⊇ [d[v], f[v]]
Unrelated
Disjoint
Question # 10 of 10 ( Start time: 10:29:23 PM ) Total Marks: 1
Strongly connected components are not affected by reversal of all edges in terms of vertices reachability.
Select correct option:
True Ans
False
Strongly connected components are not affected by reversal of all edges in terms of vertices reachability.
Select correct option:
True Ans
False
4th
Question # 1 of 10 ( Start time: 08:34:15 PM ) Total Marks: 1
According to parenthesis lemma, vertex u is unrelated to v vertex if and only if d[u],f[u]] and [d[v],f[v]] are disjoint.
Select correct option:
True Ans
False
According to parenthesis lemma, vertex u is unrelated to v vertex if and only if d[u],f[u]] and [d[v],f[v]] are disjoint.
Select correct option:
True Ans
False
Question # 2 of 10 ( Start time: 08:35:47 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 Ans
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 Ans
Question # 3 of 10 ( Start time: 08:37:05 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) Ans
? (V E)
? (V)
? (V^2)
You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.?
Select correct option:
? (V + E) Ans
? (V E)
? (V)
? (V^2)
Question # 4 of 10 ( Start time: 08:38:13 PM ) Total Marks: 1
Kruskal’s algorithm works by adding vertices in increasing order of weight (lightest edge first).
Select correct option:
True Ans
False
Kruskal’s algorithm works by adding vertices in increasing order of weight (lightest edge first).
Select correct option:
True Ans
False
Question # 5 of 10 ( Start time: 08:38:38 PM ) Total Marks: 1
In Prim's algorithm, we will make use of priority _______.
Select correct option:
Stack
Queue Ans
Array
Graph
In Prim's algorithm, we will make use of priority _______.
Select correct option:
Stack
Queue Ans
Array
Graph
Question # 6 of 10 ( Start time: 08:39:03 PM ) Total Marks: 1
If a vertex v is a descendent of vertex u, then v's start-finish interval is contained within u's start-finish interval.
Select correct option:
True Ans
False
If a vertex v is a descendent of vertex u, then v's start-finish interval is contained within u's start-finish interval.
Select correct option:
True Ans
False
Question # 7 of 10 ( Start time: 08:39:53 PM ) Total Marks: 1
Computing the strongly connected components of a digraph is a generalization of the problem to determine whether a digraph is strongly connected or not.
Select correct option:
True Ans
False
Computing the strongly connected components of a digraph is a generalization of the problem to determine whether a digraph is strongly connected or not.
Select correct option:
True Ans
False
Question # 8 of 10 ( Start time: 08:41:01 PM ) Total Marks: 1
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle Ans
Strong component
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle Ans
Strong component
Question # 9 of 10 ( Start time: 08:41:41 PM ) Total Marks: 1
Networks are complete in the sense that it is possible from any location in the network to reach any other location in the digraph.
Select correct option:
True Ans
False
Networks are complete in the sense that it is possible from any location in the network to reach any other location in the digraph.
Select correct option:
True Ans
False
Question # 10 of 10 ( Start time: 08:42:10 PM ) Total Marks: 1
By breaking any edge on a cycle created in free tree, the free _________ is restored.
Select correct option:
Edge
Tree Ans
Cycle
Vertex
By breaking any edge on a cycle created in free tree, the free _________ is restored.
Select correct option:
Edge
Tree Ans
Cycle
Vertex
5th
Question # 1 of 10 ( Start time: 10:23:08 PM ) Total Marks: 1
Adding any edge to a free tree creates a unique cycle.
Select correct option:
True
False
Adding any edge to a free tree creates a unique cycle.
Select correct option:
True
False
Question # 2 of 10 ( Start time: 10:23:52 PM ) Total Marks: 1
Forward edge is:
Select correct option:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree. Ans
(u, v) where v is a proper ancesstor of u in the tree.
(u, v) where u is a proper ancesstor of v in the tree.
Forward edge is:
Select correct option:
(u, v) where u is a proper descendent of v in the tree.
(u, v) where v is a proper descendent of u in the tree. Ans
(u, v) where v is a proper ancesstor of u in the tree.
(u, v) where u is a proper ancesstor of v in the tree.
Question # 3 of 10 ( Start time: 10:25:10 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. Ans
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. Ans
Question # 4 of 10 ( Start time: 10:25:31 PM ) Total Marks: 1
In undirected graph, by convention all the edges are called _________ edges.
Select correct option:
Forward
Back Ans
Cross
Both forward and back
In undirected graph, by convention all the edges are called _________ edges.
Select correct option:
Forward
Back Ans
Cross
Both forward and back
Question # 5 of 10 ( Start time: 10:26:38 PM ) Total Marks: 1
For undirected graph, there is no distinction between forward and back edges.
Select correct option:
True
False
For undirected graph, there is no distinction between forward and back edges.
Select correct option:
True
False
Question # 6 of 10 ( Start time: 10:26:55 PM ) Total Marks: 1
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle
Strong component
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle
Strong component
Question # 7 of 10 ( Start time: 10:27:09 PM ) Total Marks: 1
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
Question # 8 of 10 ( Start time: 10:27:23 PM ) Total Marks: 1
In strong components algorithm, the form of graph is used in which all the _________ of original graph G have been reversed in direction.
Select correct option:
Vertices
Edges Ans (not sure)
Both edges & vertices
None of the above
In strong components algorithm, the form of graph is used in which all the _________ of original graph G have been reversed in direction.
Select correct option:
Vertices
Edges Ans (not sure)
Both edges & vertices
None of the above
Question # 9 of 10 ( Start time: 10:28:31 PM ) Total Marks: 1
According to parenthesis lemma, vertex u is a descendent of v vertex if and only if;
Select correct option:
[d[u], f[u]] ⊆ [d[v], f[v]] Ans
[d[u], f[u]] ⊇ [d[v], f[v]]
Unrelated
Disjoint
According to parenthesis lemma, vertex u is a descendent of v vertex if and only if;
Select correct option:
[d[u], f[u]] ⊆ [d[v], f[v]] Ans
[d[u], f[u]] ⊇ [d[v], f[v]]
Unrelated
Disjoint
Question # 10 of 10 ( Start time: 10:29:23 PM ) Total Marks: 1
Strongly connected components are not affected by reversal of all edges in terms of vertices reachability.
Select correct option:
True Ans
False
Strongly connected components are not affected by reversal of all edges in terms of vertices reachability.
Select correct option:
True Ans
False
5th
Question # 1 of 10 ( Start time: 10:14:37 PM ) Total Marks: 1
There exist a unique path between any ________ vertices of a free tree.
Select correct option:
One
Two Ans
Three
All
There exist a unique path between any ________ vertices of a free tree.
Select correct option:
One
Two Ans
Three
All
Question # 2 of 10 ( Start time: 10:15:15 PM ) Total Marks: 1
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
Question # 3 of 10 ( Start time: 10:15:56 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. Ans
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.
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. Ans
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.
Question # 4 of 10 ( Start time: 10:16:38 PM ) Total Marks: 1
Digraphs are not used in communication and transportation networks.
Select correct option:
True
False Ans
Digraphs are not used in communication and transportation networks.
Select correct option:
True
False Ans
Question # 5 of 10 ( Start time: 10:17:31 PM ) Total Marks: 1
There are no ________ edges in undirected graph.
Select correct option:
Forward
Back
Cross
Both forward and back Ans
There are no ________ edges in undirected graph.
Select correct option:
Forward
Back
Cross
Both forward and back Ans
Question # 6 of 10 ( Start time: 10:17:53 PM ) Total Marks: 1
In Kruskal's algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
True
False Ans
In Kruskal's algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
True
False Ans
Question # 7 of 10 ( Start time: 10:18:12 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 Ans
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 Ans
Question # 8 of 10 ( Start time: 10:18:54 PM ) Total Marks: 1
The ________ given by DFS allow us to determine whether the graph contains any cycles.
Select correct option:
Order
Time stamps Ans
BFS traversing
Topological sort
The ________ given by DFS allow us to determine whether the graph contains any cycles.
Select correct option:
Order
Time stamps Ans
BFS traversing
Topological sort
Question # 9 of 10 ( Start time: 10:19:41 PM ) Total Marks: 1
Kruskal’s algorithm works by adding ________ in increasing order of weight (lightest edge first).
Select correct option:
Vertices
Edges Ans
Trees
Weights
Kruskal’s algorithm works by adding ________ in increasing order of weight (lightest edge first).
Select correct option:
Vertices
Edges Ans
Trees
Weights
Question # 10 of 10 ( Start time: 10:20:15 PM ) Total Marks: 1
Runtime complexity of Prim's algorithm is _______.
Select correct option:
V log V
E log V Ans
log V
None of the above
Runtime complexity of Prim's algorithm is _______.
Select correct option:
V log V
E log V Ans
log V
None of the above
6th
Question # 1 of 10 ( Start time: 09:24:49 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) Ans
V.E
V
E
You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ?
Select correct option:
(V+E) Ans
V.E
V
E
Question # 2 of 10 ( Start time: 09:25:25 PM ) Total Marks: 1
A free tree with n vertices have exactly n+1 edges.
Select correct option:
True
False Ans (n-1 is ans)
A free tree with n vertices have exactly n+1 edges.
Select correct option:
True
False Ans (n-1 is ans)
Question # 3 of 10 ( Start time: 09:26:18 PM ) Total Marks: 1
Adding any edge to a free tree creates a unique cycle.
Select correct option:
True Ans
False
Adding any edge to a free tree creates a unique cycle.
Select correct option:
True Ans
False
Question # 4 of 10 ( Start time: 09:26:51 PM ) Total Marks: 1
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
In ________ algorithm, at any time, the subset of edges A forms a single tree.
Select correct option:
Kruskal's
Prim's Ans
Both
None
Question # 5 of 10 ( Start time: 09:27:29 PM ) Total Marks: 1
By breaking any edge on a cycle created in free tree, the free _________ is restored.
Select correct option:
Edge
Tree Ans
Cycle
Vertex
By breaking any edge on a cycle created in free tree, the free _________ is restored.
Select correct option:
Edge
Tree Ans
Cycle
Vertex
Question # 6 of 10 ( Start time: 09:28:13 PM ) Total Marks: 1
In Kruskal's algorithm, the next ________ is not added to viable set A, if its adding induce a/an cycle.
Select correct option:
Vertex
Edge Ans
Cycle
Tree
In Kruskal's algorithm, the next ________ is not added to viable set A, if its adding induce a/an cycle.
Select correct option:
Vertex
Edge Ans
Cycle
Tree
Question # 7 of 10 ( Start time: 09:29:33 PM ) Total Marks: 1
In Generic approach determining of Greedy MST, we maintain a subset A of __________ .
Select correct option:
Edges Ans
Vertices
Cycles
Paths
In Generic approach determining of Greedy MST, we maintain a subset A of __________ .
Select correct option:
Edges Ans
Vertices
Cycles
Paths
Question # 8 of 10 ( Start time: 09:30:38 PM ) Total Marks: 1
In Prim's algorithm, at any time, the subset of edges A forms a single _________.
Select correct option:
Vertex
Forest
Tree Ans
Graph
In Prim's algorithm, at any time, the subset of edges A forms a single _________.
Select correct option:
Vertex
Forest
Tree Ans
Graph
Question # 9 of 10 ( Start time: 09:31:16 PM ) Total Marks: 1
The ________ given by DFS allow us to determine whether the graph contains any cycles.
Select correct option:
Order
Time stamps Ans
BFS traversing
Topological sort
The ________ given by DFS allow us to determine whether the graph contains any cycles.
Select correct option:
Order
Time stamps Ans
BFS traversing
Topological sort
Question # 10 of 10 ( Start time: 09:32:27 PM ) Total Marks: 1
According to parenthesis lemma, vertex u is unrelated to v vertex if and only if d[u],f[u]] and [d[v],f[v]] are disjoint.
Select correct option:
True Ans
False
According to parenthesis lemma, vertex u is unrelated to v vertex if and only if d[u],f[u]] and [d[v],f[v]] are disjoint.
Select correct option:
True Ans
False
7th
Question # 1 of 10 ( Start time: 09:06:49 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:
You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ?
Select correct option:
(V+E) Ans
v.e
v
e
Runtime complexity of Prim's algorithm is _______.
vlog e Ans
v log v
log v
None
Adding any edge to a free tree creates a unique cycle
True Ans
False
There exist a unique path between any ________ vertices of a free tree.
1
2 Ans
3
All
In digraph G=(V,E) ;G has cycle if and only if
The DFS forest has forward edge.
The DFS forest has forward edge. Ans
The DFS forest has both back and forward edge
BFS forest has forward edge
Back edge is:
(u, v) where v is an ancestor of u in the tree. Ans
(u,v) where u is an ancesstor of v in the tree.
(u, v) where v is an predcessor of u in the tree.
None
There is relationship between number of back edges and number of cycles in DFS
Cycles are half of back edges.
both are equal
Cycles are one fourth of back edges.
There is no relationship between back edges and number of cycles Ans
Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few edges
True
False Ans
8th
Question # 1 of 10 ( Start time: 08:34:15 PM ) Total Marks: 1
According to parenthesis lemma, vertex u is unrelated to v vertex if and only if d[u],f[u]] and [d[v],f[v]] are disjoint.
Select correct option:
True Ans
False
According to parenthesis lemma, vertex u is unrelated to v vertex if and only if d[u],f[u]] and [d[v],f[v]] are disjoint.
Select correct option:
True Ans
False
Question # 2 of 10 ( Start time: 08:35:47 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
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
Question # 3 of 10 ( Start time: 08:37:05 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) Ans
? (V E)
? (envy)
? (V^2)
You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.?
Select correct option:
? (V + E) Ans
? (V E)
? (envy)
? (V^2)
Question # 4 of 10 ( Start time: 08:38:13 PM ) Total Marks: 1
Kruskal’s algorithm works by adding vertices in increasing order of weight (lightest edge first).
Select correct option:
True Ans
False
Kruskal’s algorithm works by adding vertices in increasing order of weight (lightest edge first).
Select correct option:
True Ans
False
Question # 5 of 10 ( Start time: 08:38:38 PM ) Total Marks: 1
In Prim's algorithm, we will make use of priority _______.
Select correct option:
Stack
Queue Ans
Array
Graph
In Prim's algorithm, we will make use of priority _______.
Select correct option:
Stack
Queue Ans
Array
Graph
Question # 6 of 10 ( Start time: 08:39:03 PM ) Total Marks: 1
If a vertex v is a descendent of vertex u, then v's start-finish interval is contained within u's start-finish interval.
Select correct option:
True Ans
False
If a vertex v is a descendent of vertex u, then v's start-finish interval is contained within u's start-finish interval.
Select correct option:
True Ans
False
Question # 7 of 10 ( Start time: 08:39:53 PM ) Total Marks: 1
Computing the strongly connected components of a digraph is a generalization of the problem to determine whether a digraph is strongly connected or not.
Select correct option:
True Ans
False
Computing the strongly connected components of a digraph is a generalization of the problem to determine whether a digraph is strongly connected or not.
Select correct option:
True Ans
False
Question # 8 of 10 ( Start time: 08:41:01 PM ) Total Marks: 1
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle ANs
Strong component
Adding any edge to a free tree creates a unique ______ .
Select correct option:
Vertex
Edge
Cycle ANs
Strong component
Question # 9 of 10 ( Start time: 08:41:41 PM ) Total Marks: 1
Networks are complete in the sense that it is possible from any location in the network to reach any other location in the digraph.
Select correct option:
True Ans
False
Networks are complete in the sense that it is possible from any location in the network to reach any other location in the digraph.
Select correct option:
True Ans
False
Question # 10 of 10 ( Start time: 08:42:10 PM ) Total Marks: 1
By breaking any edge on a cycle created in free tree, the free _________ is restored.
Select correct option:
Edge
Tree Ans
Cycle
Vertex
By breaking any edge on a cycle created in free tree, the free _________ is restored.
Select correct option:
Edge
Tree Ans
Cycle
Vertex
Today
1. If a vertex is a descendent of
vertex u, then v's start-finish interval is contained within u's start-finish interval.
True
False
True
False
2. In Kruskal's algorithm, the
next edge is added to viable set A, if its adding does not induce a cycle.
True
False
True
False
3. What is true statement?
Breadth first search is shortest path algorithm that works on un-weighted graphs
Depth first search is shortest path algorithm that works on un-weighted graphs
Both of above are true
None of above are true
Breadth first search is shortest path algorithm that works on un-weighted graphs
Depth first search is shortest path algorithm that works on un-weighted graphs
Both of above are true
None of above are true
4. Kruskal's algorithm works by
adding vertices in increasing order of weight (lightest edge
first).
True
False
first).
True
False
5. As the Kruskal's algorithm
runs, the edges in viable set A induce a______ on the vertices.
Set
Graph
Tree
Forest
Set
Graph
Tree
Forest
6. If a subset of edges A is
viable for building MST, it can not contain a/an________.
Vertex
Edge
Cycle
Graph
Vertex
Edge
Cycle
Graph
7. By breaking any edge on a cycle created in free tree,
the free _________ is restored.
Cycle Tree
Cycle Tree
8. Breadth-first search is not a popular algorithm
technique used for traversing graphs. True
False
9. Adding any edge to a free tree creates a unique ______
.
options yad ni
10.
In greedy
algorithm, at each phase, you take the________ you can get right now, without
regard for future consequences. Worst best
good
none of above
End OF Quiz
