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.
AlgorithmsGreedy-approachGATE 1994
Question 2

Consider the undirected graph below:


Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

A
(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
B
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
C
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
D
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
AlgorithmsGreedy-approachGATE 2004-IT
Question 2 Explanation: 
(A) and (B) produce disconnected components with the given order in options which is never allowed by Prim's algorithm.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Question 3
Dijkstra’s algorithm follows ___________ method of algorithm design. The complexity of the algorithm to find the shortest path from a vertex to all other vertices in a graph is __________
A
Dynamic programming, O (n2)
B
Dynamic programming, O (log n)
C
Greedy, O (n2)
D
Greedy, O (log n)
E
None of the above
AlgorithmsGreedy-approachTNPSC-2017-Polytechnic-CS
Question 3 Explanation: 
Dijkstra's algorithm follows greedy method of algorithm design. The complexity of algorithm to find the shortest path from a vertex to all other vertices in a graph is O(ElogV).
Question 4
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)
AlgorithmsGreedy-approachTNPSC-2017-Polytechnic-CS
Question 4 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 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
AlgorithmsGreedy-approachCIL Part - B
Question 5 Explanation: 


Question 6

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
AlgorithmsGreedy-approachCIL Part - B
Question 6 Explanation: 
Question 7
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
AlgorithmsGreedy-approachCIL Part - B
Question 7 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 8
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
AlgorithmsGreedy-approachUGC NET CS 2015 June Paper-3
Question 8 Explanation: 

There are 8 questions to complete.

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

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