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.
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?
(1, 6), (6, 5), (5, 4), (4, 3), (3, 2), (2, 7) | |
(1, 6), (3, 4), (2, 7), (2, 3), (7, 4), (5, 4) | |
(1, 6), (3, 4), (2, 7), (4, 5), (1, 2), (5, 6) | |
(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).
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?
0-1 knapsack | |
Job scheduling | |
Minimum spanning tree | |
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
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’?
11 | |
9 | |
10 | |
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’?
Using the Huffman coding technique, which of the following is the valid code for character ‘c’?
11111 | |
1110 | |
11110 | |
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:
67/30 | |
70/30 | |
76/30 | |
78/30 | |
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:
2.40 | |
2.16 | |
2.26 | |
2.15 |
Question 7 Explanation: