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?
![](https://solutionsadda.in/wp-content/uploads/2020/03/100.jpg)
![](https://solutionsadda.in/wp-content/uploads/2020/03/100.jpg)
(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’.
![](https://solutionsadda.in/wp-content/uploads/2020/01/Screenshot_35-300x157.png)
What is the weight of the minimum spanning tree for the graph ‘G’?
11 | |
9 | |
10 | |
8 |
Question 4 Explanation:
![](https://solutionsadda.in/wp-content/uploads/2020/01/algo_mst.jpg)
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’?
![](https://solutionsadda.in/wp-content/uploads/2020/01/Screenshot_55-300x34.png)
Using the Huffman coding technique, which of the following is the valid code for character ‘c’?
11111 | |
1110 | |
11110 | |
110 |
Question 5 Explanation:
![](https://solutionsadda.in/wp-content/uploads/2020/01/algo_huff.jpg)
![](https://solutionsadda.in/wp-content/uploads/2020/01/algo_huff_2.jpg)
![](https://solutionsadda.in/wp-content/uploads/2020/01/algo_huff_3.jpg)
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:
![](https://solutionsadda.in/wp-content/uploads/2019/08/Screenshot-from-2019-08-28-23-21-35.png)
![](https://solutionsadda.in/wp-content/uploads/2019/08/Screenshot-from-2019-08-28-23-22-25.png)
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:
![](https://solutionsadda.in/wp-content/uploads/2019/05/Screenshot_556.png)
![](https://solutionsadda.in/wp-content/uploads/2019/05/Screenshot_557.png)
![](https://solutionsadda.in/wp-content/uploads/2019/05/Screenshot_558.png)