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

Dear student,
Quiz # 3 will be conducted on 29th and 30th of July 2015 i.e. on Wednesday and Thursday for CS502.

23-31 lectures will be covered in this quiz.

So be prepared for it!

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

.

+ 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

Question # 1 of 10 ( Start time: 10:35:08 PM )  Total Marks: 1

A dense undirected graph is:

Select correct option:

A graph in which E = O(V^2)         =  Correct Option

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

Question # 2 of 10 ( Start time: 10:35:36 PM )  Total Marks: 1

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

O(|V |^2|E|)

O(|V | + |E|)        =  Correct Option

Question # 3 of 10 ( Start time: 10:35:54 PM )  Total Marks: 1

Which is true statement.

Select correct option:

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.      =  Correct Option

None of above are true.

Question # 4 of 10 ( Start time: 10:37:30 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.   Pg 129       =  Correct Option

(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 # 5 of 10 ( Start time: 10:37:58 PM )  Total Marks: 1

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

Select correct option:

64

128

96   pg 101     12*8=96       =  Correct Option

120

Question # 6 of 10 ( Start time: 10:38:14 PM )  Total Marks: 1

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.      =  Correct Option

Only one value is entered in the list.

There is at least one null list.

Question # 7 of 10 ( Start time: 10:38:40 PM )  Total Marks: 1

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

Select correct option:

BFS

BFS and DFS both are valid  pg 119       =  Correct Option

Level order

DFS

Question # 8 of 10 ( Start time: 10:39:11 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   pg 131       =  Correct Option

The DFS forest has both back and forward edge

BFS forest has forward edge

Question # 9 of 10 ( Start time: 10:40:46 PM )  Total Marks: 1

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)  pg 116        =  Correct Option

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)

Question # 10 of 10 ( Start time: 10:41:26 PM )  Total Marks: 1

Back edge is:

Select correct option:

(u, v) where v is an ancestor of u in the tree.   Pg 128        =  Correct Option

(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: 10:45:02 PM )  Total Marks: 1

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.        =  Correct Option

Only one value is entered in the list.

There is at least one null list.

Question # 2 of 10 ( Start time: 10:45:23 PM )  Total Marks: 1

Which is true statement.

Select correct option:

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.        =  Correct Option

None of above are true.

Question # 3 of 10 ( Start time: 10:46:23 PM )  Total Marks: 1

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       =  Correct Option

None of above

Question # 5 of 10 ( Start time: 10:49:16 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.      =  Correct Option

(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 # 7 of 10 ( Start time: 10:49:59 PM )  Total Marks: 1

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

Select correct option:

BFS

BFS and DFS both are valid        =  Correct Option

Level order

DFS

Question # 8 of 10 ( Start time: 10:50:34 PM )  Total Marks: 1

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)      =  Correct Option

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)

Question # 9 of 10 ( Start time: 10:51:45 PM )  Total Marks: 1

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  pg 129       =  Correct Option

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

Question # 10 of 10 ( Start time: 10:52:39 PM )  Total Marks: 1

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

O(|V |^2|E|)

O(|V | + |E|)       =  Correct Option

Question # 1 of 10
Graphs cannot be represented by an adjacency matrix.
Select correct option:
True
False

Question # 2 of 10
In Huffman encoding, for a given message string, the frequency of occurrence (relative probability) of each __________in the message is done first.
Select correct option:
Word
Space
Digit
Character

Question # 3 of 10

A graph is said to be acyclic if it contains _____________
Select correct option:
at least one cycle
exactly one cycle
always more than one cycle
no cycles

Question # 4 of 10
In Huffman encoding, for a given message string, the frequency of occurrence (relative probability) of each character in the message is determined last.
Select correct option:
True
False

Question # 5 of 10
In solving Fractional Knapsack problem, we do not need sorting.
Select correct option:
True
False

Question # 6 of 10
In Activity Selection, we say that two activities are non-interfering if their start-finish interval _________ overlap.
Select correct option:
Do
Do not
Sometimes
Once

Question # 7 of 10
Each time we traverse graph by Breadth-first search algorithm, we count the distance from _________
Select correct option:
starting node
neighbors of the starting node
right most node
left most node

Question # 8 of 10
Counting Money problem is an example which can not be optimally solved by greedy algorithm.
Select correct option:
True
False

Question # 9 of 10
In Activity scheduling algorithm, the width of a rectangle ____________
Select correct option:
Is always ignored
Directs towards recursion
Should be maximized
Indicates the duration of an activity

Question # 10 of 10
In Huffman encoding, for the base case, n=1, the tree consists of a single leaf node, which is not optimal.
Select correct option:
True
False

In general in comparison with Fractional Knapsack problem, ______________
Select correct option:

In Huffman encoding, the ____________is the number of occurrence of a character divided by the total characters in the message.
Select correct option:

PROBABILITY

Huffman algorithm generates an optimum prefix code.
Select correct option:

TRUE

Breadth-first search is not a traversal strategy for graphs.
Select correct option:

FALSE

Those problems in which Greedy finds good, but not always best is called a greedy________.
Select correct option:

GREDY HURISTICS

Graphs cannot be traversed by brute-force technique.
Select correct option:

FALSE

In general, a graph G = (V,E) consists of a ___________ and E, a binary relation on V called edges.
Select correct option:

V HAVE FINITE NUMBER OF VERTICES

In a digraph, the number of edges coming in of a vertex is not called the in-degree of that vertex.
Select correct option:

FALSE

Greedy algorithm approach solves both 0/1 Knapsack and Fractional Knapsack problems.
Select correct option:

TRUE

In Fractional Knapsack problem, there is no limit of total weight.
Select correct option:

FALSE

1.Huffman algorithm generates an optimum prefix code.
Options:
a. True
b.false

2.A graph is not connected if every vertex can reach every other vertex.
Options:
a. True
b.false

3.If the string “lmncde” is coded with ASCII code, the message length would be _______ bits.

4.The activity schedule is a simple scheduling problem for which the _________approache provides an optimal solution.

5. In solving Fractional Knapsack problem, we do not need sorting.
Options:
a. True
b.false

6 .A graph is said to be acyclic if it contains
b. always more than one cycle
c. exactly one cycle
d. at least one cycle

7. In Huffman Encoding, the characters with smallest probabilities are placed at the ________ depth of the tree.
a. Minimum
b. maximum

8.The Binary Tree constructed by Huffman Encoding is not a full Binary Tree.

9. An approach is optimal for the fractional knapsack problem.
Brute force
Greedy algorithm
Dynamic Programming
Divide and Conquer

10. Greedy algorithm approach solves both 0/1 Knapsack and Fractional Knapsack problems.
Options:
a. True
b.false

6. no cycle

7. maximum

8. false

9. greedy algorithm

10. false

Please all students related this subject Share your online Quizzes here to help each other.thanks

Please share the question and their answers of this quiz if anyone has done.
Thanks.

Attachments:

this is my today qui

almost i choose correct option in thia quiz.

Quiz file

Attachments:

Reference #18.1ce95d6e.1438244442.1e586953  