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

# www.vustudents.ning.com

 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

 Quiz No. 4 Dated: Jul 25, 14 Dear Students! It is to inform that Quiz No. 4 will be conducted from Lecture No. 31 – Lecture No. 37. The Quiz will open for 48 Hours ONLY on 4th and 5th August 2014. You are required to carefully read and follow instructions before submitting quiz. All instructions will be provided with the quiz. Incase of any question, do not hesitate to email us at CS502@vu.edu.pk

+ 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?

Views: 2416

.

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

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

### Replies to This Discussion

Equivalence pg 136

good

koi aur bi share kare quiz plz

I 'll post my quiz soon.

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.

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 |^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

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 |^2|E|)

O(|V | + |E|)

wrong ans  post na kia krooooo plzzzzzzzzzzz last option h page 116

In Quick sort algorithm,constants hidden in T(n lg n) are

Large

Medium

Not known

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

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)

?(V)

?(V^2)

What is the time complexity to extract a vertex from the priority queue in Prim's

algorithm?

Select correct option:

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?

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)

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 |^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?

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

False

You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.?

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

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 :

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

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^3)

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

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

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^3)

In Quick sort algorithm,constants hidden in T(n lg n) are

Large

Medium

Not known

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

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)

?(V)

?(V^2)

What is the time complexity to extract a vertex from the priority queue in Prim's

algorithm?

Select correct option:

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?

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)

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.

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 |^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

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.

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.

Thanks

.