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

# CS 502 Fundamental of Algorithms Online quiz # 4 due date 26-02-2015 to 27-02-2015

+ 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: 4971

.

+ 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

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

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)

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

a)      Greedy Technique page 142

b)      Divide-and-Conquer Technique

c)      Dynamic Programming Technique

d)     The algorithm combines more than one of the above techniques i.e. Divide-and-Conquer and dynamic programing

1. There exists a unique path between any __________ vertices of a free tree.

a)      One

b)     Two page 142

c)      Three

d)     All

1. If a subset of edges A is viable for building MST, it cannot contain a/an ___________

a)      Vertex

b)      Edge

c)      Cycle page 143

d)     Graph

1. As the Kruskal’s runs, the edges in viable set A induce a _________ on the vertices.

a)      Set

b)      Graph

c)      Tree

d)     Forest

1. The ___________ given by DFS allow us to determine whether the graph contains any cycles.

a)      Order

b)     Time stamps page 130

c)      BFS traversing

d)     Topological sort

1. The time stamps given by DFS do not allow determining whether the graph contains any cycles.

a)      True

b)     False page130

1. By breaking any edge on a cycle created in free tree, the free _______ is restored.

a)      Edge

b)      Tree

c)      Cycle page 143

d)     Vertex

1. Forward edge is

a)      (u, v) where u is a proper descendent of v in the tree

b)     (u, v) where v is a proper descendent of u in the tree page 129

c)      (u, v) where v is a proper ancestor of u in the tree

d)     (u, v) where u is a proper ancestor of v in the tree

1. In Kruskal’s algorithm, the next _______ is not added to viable set A, if its adding induces a/an cycle.

a)      Vertex

b)     Edge page147

c)      Cycle

d)     Tree

1. In _________ algorithm, at any time, the subset of edges A forms a single tree

a)      Kruskal’s

b)     Prim’s page 149

c)      Both

d)     None

true

## Latest Activity

Pasha updated their profile
9 minutes ago
Mr A updated their profile
36 minutes ago
Fakhar-Ur-Rehman joined + M.Tariq Malik's group

### CS206 Introduction to Network Design & Analysis

52 minutes ago
1 hour ago
لاحاصل updated their profile
1 hour ago

### STAT404 Regression and Correlation

1 hour ago
2 hours ago
Sponge Bob updated their profile
2 hours ago
لاحاصل, Tayyaba Ahmad., Mr A and 2 more joined Virtual University of Pakistan
2 hours ago
Laila liked Mani Siddiqui BS VIII's discussion Happy BirthDay Dear Tariq Bhai
2 hours ago
Laila liked + ! ! ! ! ! ! ! ! ђคlєє๓ค !'s discussion happy birthday tariq sirr
2 hours ago
HAMDAN updated their profile
3 hours ago

1

2

3