We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

Looking For Something at vustudents.ning.com? Click Here to Search

www.bit.ly/vucodes

+ Link For Assignments, GDBs & Online Quizzes Solution

www.bit.ly/papersvu

+ Link For Past Papers, Solved MCQs, Short Notes & More


Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

How to Add New Discussion in Study Group ? Step By Step Guide Click Here.

CS502 Fundamentals of Algorithms Quizz # 4 ( 6 STUDENTzzz Quizzez attempted today)

+ How to Follow the New Added Discussions at Your Mail Address?

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?


See Your Saved Posts Timeline

Views: 5793

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

+ Click Here to Search (Looking For something at vustudents.ning.com?)

+ Click Here To Join (Our facebook study Group)

Attachments:

Replies to This Discussion

Back edge is 
(u,v) where v is an ancestor of u in the tree page # 128
What algorithm technique is used in the implementation of kruskal solution for the MST? 
Greedy Technique page #142
in designe G=(V,E) ;
G has cycle if and only if The DFS forest has back edge page # 131
Cross edge is : 
(u,v) where u and v are not ancestor or descendent of one another page #129
Forword edge is :
(u,v) where v is a proper decendent of u in the tree. Page # 129
A digraph is strongly connected if for every pair of vertex u, v Є V, u can reach v and vice versa. Page #135
You have an adjacent list for G, what is the time complexity to compute graph transpose G^T.? Θ(V + E ) PAGE # 138

Given an adjacency list for G, it is possible to compute G T in Θ(V + E) time.

What is the time complexity to extract a vertex from the priority queue in prim’s algorithm ? O Log (v) page #152

It takes O(log V) to extract a vertex from the priority queue.

There is relationship between number of back edges and number of cycles in DFS

There is no relationship between back edges and number of cycles


Which is true statement in the following

Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best Tree edge) when the graph has relatively few edges.



Overall time for Kruskal is

Θ(E log E) = Θ(E log V) if the graph is sparse. P-149

True





Dijkstra’s algorithm:



Has greedy approach to compute single source shortest paths to all other vertices page 154





What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?



O (log V)



Which 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.

In in-place sorting algorithm is one that uses arrays for storage :
An additional array

No additional array (Right Answer)

Both of above may be true according to algorithm

More than 3 arrays of one dimension.

 

The running time of quick sort depends heavily on the selection of

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

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)

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.

 

 

 

What algorithm technique is used in the implementation of Kruskal solution for the

MST?

Greedy Technique (Right Answer)

Divide-and-Conquer Technique

Dynamic Programming Technique

The algorithm combines more than one of the above techniques

 

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) (Right Answer)

 

Which is true statement in the following.

Kruskal algorithm is multiple source technique for finding MST.

Kruskal's algorithm is used to find minimum spanning tree of a graph, time complexity of this algorithm is O(EV)

Both of above

Kruskal's algorithm (choose best non-cycle edge) is better than Prim's  (choose best Tree edge) when the graph has relatively few edges ) (Right Answer)

 

The relationship between number of back edges and number of cycles in DFS is,

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 (Right Answer)

 

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  (Right Answer)

False

 

 

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)

 

Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?

Select correct option:

O(|V |^2)

O(|V | |E|) (Right Answer)

O(|V |^2|E|)

O(|V | + |E|)



What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

Select correct option:

Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)

Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2) Right Answer)

Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2)

Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)



What general property of the list indicates that the graph has an isolated vertex?

Select correct option:

There is Null pointer at the end of list.

The Isolated vertex is not handled in list. (not Sure)

Only one value is entered in the list.

There is at least one null list.


A dense undirected graph is:

Select correct option:

A graph in which E = O(V^2) (Right Answer)

A graph in which E = O(V)

A graph in which E = O(log V)

All items above may be used to characterize a dense undirected graph

 


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 (Right Answer)

The DFS forest has both back and forward edge

BFS forest has forward edge

 

Back edge is:

Select correct option:

(u, v) where v is an ancestor of u in the tree. (Right Answer)

(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 of above

 

Using ASCII standard the string "abacdaacacwe" will be encoded with __________ bits

Select correct option:

64

128 (Right Answer)

96

120


Cross edge is :

Select correct option:

(u, v) where u and v are not ancestor of one another

(u, v) where u is ancesstor of v and v is not descendent of u.

(u, v) where u and v are not ancestor or descendent of one another (Right Answer)

(u, v) where u and v are either ancestor or descendent of one another. 

Which statement is true?

Select correct option:

If a dynamic-programming problem satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.

If a greedy choice property satisfies the optimal-substructure property, then a locally optimal solution is globally optimal.

Both of above Right Answer)

None of above

10  If you find yourself in maze the better traversel approach will bE


A dense undirected graph is:

Select correct option:

A graph in which E = O(V^2) (Right Answer)

A graph in which E = O(V)

A graph in which E = O(log V)

All items above may be used to characterize a dense undirected graph


Which is true statement.

Select correct option:

Breadth first search is shortest path algorithm that works on un-weighted graphs (Right Answer)

Depth first search is shortest path algorithm that works on un-weighted graphs.

Both of above are true.

None of above are true.


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. (Right Answer)

(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.


Back edge is:

Select correct option:

(u, v) where v is an ancestor of u in the tree. (Right Answer)

(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 of above

 

 

Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?

Select correct option:

O(|V |^2)

O(|V | |E|) (Right Answer)

O(|V |^2|E|)

O(|V | + |E|)

 

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 (Right Answer)

The DFS forest has both back and forward edge

BFS forest has forward edge

 

What general property of the list indicates that the graph has an isolated vertex?

Select correct option:

There is Null pointer at the end of list.

The Isolated vertex is not handled in list. (not Sure)

Only one value is entered in the list.

There is at least one null list.

 

If you find yourself in maze the better traversel approach will be :

BFS

BFS and DFS both are valid (Right Answer)

Level order

DFS

 

Cross edge is :

(u, v) where u and v are not ancestor of one another

(u, v) where u is ancesstor of v and v is not  descendent of u.

(u, v) where u and v are not ancestor or descendent of one another (Right Answer)

 (u, v) where u and v are either ancestor or descendent of one another.

 

What algorithm technique is used in the implementation of Kruskal solution for the MST?

Greedy Technique   (Right Answer)

Divide-and-Conquer Technique

Dynamic Programming Technique 

The algorithm combines more than one of the above techniques

 

Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few

True (Right Answer)

False

 

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)

 

A digraph is strongly connected under what condition?

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. (Right Answer)

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.

 

The relationship between number of back edges and number of cycles in DFS is,

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 (Right Answer)

 

What algorithm technique is used in the implementation of Kruskal solution for the MST?

Greedy Technique  (Right Answer)

Divide-and-Conquer Technique

Dynamic Programming Technique 

The algorithm combines more than one of the above techniques

 

 

In in-place sorting algorithm is one that uses arrays for storage :
An additional array

No additional array (Right Answer)

Both of above may be true according to algorithm

More than 3 arrays of one dimension.

 

The running time of quick sort depends heavily on the selection of

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

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)

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.

 

 

 

What algorithm technique is used in the implementation of Kruskal solution for the

MST?

Greedy Technique (Right Answer)

Divide-and-Conquer Technique

Dynamic Programming Technique

The algorithm combines more than one of the above techniques

 

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) (Right Answer)

 

Which is true statement in the following.

Kruskal algorithm is multiple source technique for finding MST.

Kruskal's algorithm is used to find minimum spanning tree of a graph, time complexity of this algorithm is O(EV)

Both of above

Kruskal's algorithm (choose best non-cycle edge) is better than Prim's  (choose best Tree edge) when the graph has relatively few edges ) (Right Answer)

 

The relationship between number of back edges and number of cycles in DFS is,

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 (Right Answer)

 

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  (Right Answer)

False

 

 

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)

 

Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?

Select correct option:

O(|V |^2)

O(|V | |E|) (Right Answer)

O(|V |^2|E|)

O(|V | + |E|)



What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

Select correct option:

Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)

Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2) Right Answer)

Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2)

Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)



What general property of the list indicates that the graph has an isolated vertex?

Select correct option:

There is Null pointer at the end of list.

The Isolated vertex is not handled in list. (not Sure)

Only one value is entered in the list.

There is at least one null list.


A dense undirected graph is:

Select correct option:

A graph in which E = O(V^2) (Right Answer)

A graph in which E = O(V)

A graph in which E = O(log V)

All items above may be used to characterize a dense undirected graph

 


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 (Right Answer)

The DFS forest has both back and forward edge

BFS forest has forward edge

 

Back edge is:

Select correct option:

(u, v) where v is an ancestor of u in the tree. (Right Answer)

(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 of above

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

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

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)

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

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

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

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

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

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

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

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: 

(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

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

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)

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

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

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

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 

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 

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 

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

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

Thanks...

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

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

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.

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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 

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)

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

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

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

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

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

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

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

Thanks

RSS

© 2020   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service

.