Greedy-approach

Question 1

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:

                      V: Set of all vertices in the tree;        I:=φ;
    While             V ≠ φdo
    begin
                      select a vertex u; ∈ V such that
                      V:= V – {u};
                      if u is such that
                      then 1:= I ∪ {u}
                      end;
                      output(I); 

(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.

A
Theory Explanation.
Question 2
In which order the edges of the given graph are chosen while constructing the minimum spanning tree using prim’s algorithm?
A
(1, 6), (6, 5), (5, 4), (4, 3), (3, 2), (2, 7)
B
(1, 6), (3, 4), (2, 7), (2, 3), (7, 4), (5, 4)
C
(1, 6), (3, 4), (2, 7), (4, 5), (1, 2), (5, 6)
D
(1, 6), (6, 5), (5, 4), (4, 3), (3, 2), (4, 7)
Question 2 Explanation: 
The Prim's algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
B cant be the answer because after edge (1,6) is considered then (3,4) cant be taken because vertex 3 or 4 is not connected directly to the tree having edge (1,6).
C cant be the answer. Same reason as B.
D cant be the answer because after edge (3,2) is considered then next cheapest edge is (2,7) and not (4,7).
Question 3
Which of the following problem cannot be solved using greedy approach?
A
0-1 knapsack
B
Job scheduling
C
Minimum spanning tree
D
Huffman code
Question 3 Explanation: 
Greedy Problems:
1. Job scheduling
2. Minimum spanning tree
3. Huffman code
Dynamic Programming:
1. O/1 knapsack
2. Optimal Binary search tree
3. Matrix chain multiplication
Question 4

Consider the following Adjacency matrix corresonding to some weighted Graph ‘G’.



What is the weight of the minimum spanning tree for the graph ‘G’?
A
11
B
9
C
10
D
8
Question 4 Explanation: 
Question 5
Consider the characters and their frequency counts given in the following table.

Using the Huffman coding technique, which of the following is the valid code for character ‘c’?
A
11111
B
1110
C
11110
D
110
Question 5 Explanation: 


Question 6
Given the symbols A, B, C, D, E, F, G and H with the probabilities 1/30, 1/30, 1/30, 2/30, 3/30, 5/30, 5/30, and 12/30 respectively. The average Huffman code size in bits per symbol is:
A
67/30
B
70/30
C
76/30
D
78/30
E
None of the above
Question 6 Explanation: 

Question 7
A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of:
A
2.40
B
2.16
C
2.26
D
2.15
Question 7 Explanation: 



There are 7 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access