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
Huffman tree is constructed for the following data: { A, B, C, D, E} with frequency {0.17, 0.11, 0.24, 0.33 and 0.15} respectively. 100 00 01 101 is decoded as
A
BACE
B
CAD
C
BAD
D
CADD
AlgorithmsGreedy-approachISRO CS 2020Video-Explanation
Question 3 Explanation: 


Question 4
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 4 Explanation: 


Question 5

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 5 Explanation: 
Question 6
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 6 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 7
Which of the following algorithms is fastest to find shortest path from a source node to a destination node in an un-weighted connected graph?
A
Warshall’s algorithm
B
Floyd’s algorithm
C
Breadth First Traversal
D
Depth First Traversal
AlgorithmsGreedy-approachAPPSC-2016-DL-CS
Question 7 Explanation: 
warshall algorithm will take O(n^3) time.
Floyd’s algorithm will take O(n^3) time.
Breadth First traversal will take O(m+n) time.
Depth first traversal will work only if the graph is tree.
Hence among the given options Breadth first traversal is best.
Question 8
Match the following:
A
a-i, b-iii, c-iv, d-ii
B
a-i, b-iii, c-ii, d-iv
C
a-iii, b-i, c-iv, d-ii
D
a-iii, b-i, c-ii, d-iv
AlgorithmsGreedy-approachUGC NET CS 2016 Aug- paper-3
Question 8 Explanation: 
Prim’s algorithm→ O(ElogV)
Bellman-Ford algorithm→ O(V2E)
Floyd-Warshall algorithm→ O(V3)
Johnson’s algorithm→ O(VE lg V)
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