Previously Asked GATE Questions for Greedy Algorithm

Question 1: Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f? GATE-2007

(A) 0, 10, 110, 1110, 11110, 11111
(B) 11, 10, 011, 010, 001, 000
(C) 11, 1, 01, 001, 0001, 0000
(D) 110, 100, 010, 000, 001, 111

Correct Answer: (A)
Explanation: We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities 
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 

                 1
               /   \
              /     \
             1/2    a(1/2)
            /  \
           /    \
          1/4  b(1/4) 
         /   \
        /     \
       1/8   c(1/8) 
      /  \
     /    \
   1/16  d(1/16)
  /  \
 e    f

Question 2: Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?

(A) 3
(B) 2.1875
(C) 2.25
(D) 1.9375

Correct Answer: (D)
Explanation: We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities 
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 

                 1
               /   \
              /     \
             1/2    a(1/2)
            /  \
           /    \
          1/4  b(1/4) 
         /   \
        /     \
       1/8   c(1/8) 
      /  \
     /    \
   1/16  d(1/16)
  /  \
 e    f
The average length = (1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 + 5*1/32)
                   = 1.9375 

Question 3: 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)

Correct Answer: (D)
Explanation:
A. False 
The idea behind Prim’s algorithm is to construct a spanning tree – means all vertices must be connected but here vertices are disconnected

B. False 
The idea behind Prim’s algorithm is to construct a spanning tree – means all vertices must be connected but here vertices are disconnected

C. False. 
Prim’s is a greedy algorithm and At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. In this option, since weight of AD<AB, so AD must be picked up first (which is not true as per the options).

D.TRUE.

Therefore, Answer is D

Question 4: Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by V_opt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by V_greedy. The value of V_opt − V_greedy is ______ .

(A) 16
(B) 8
(C) 44
(D) 60

Correct Answer: (A)
Explanation: First we will pick item_4 (Value weight ratio is highest). Second highest is item_1, but cannot be picked because of its weight. Now item_3 shall be picked. item_2 cannot be included because of its weight. Therefore, overall profit by V_greedy = 20+24 = 44 Hence, V_opt – V_greedy = 60-44 = 16 So, answer is 16.

Question 5: 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

Correct Answer: (B)
Explanation: a = 0.11 b = 0.40 c = 0.16 d = 0.09 e = 0.24 we will draw a huffman tree.
now huffman coding for character:

 a = 1111
      b = 0
      c = 110
      d = 1111
      e = 10
length for each character = no of bits * frequency of occurrence:
a = 4 * 0.11
  = 0.44
b = 1 * 0.4
  =  0.4
c = 3 * 0.16
  = 0.48
d = 4 * 0.09
  =  0.36 
e = 2 * 0.24
  = 0.48
Now add these lenght for average length:
 0.44 + 0.4 + 0.48 + 0.36 + 0.48 = 2.16

Question 6: Which of the following is true about Huffman Coding.

(A) Huffman coding may become lossy in some cases
(B) Huffman Codes may not be optimal lossless codes in some cases
(C) In Huffman coding, no code is prefix of any other code.
(D) All of the above

Correct Answer: (C)
Explanation: Huffman coding is a lossless data compression algorithm. The codes assigned to input characters are Prefix Codes, means the codes are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character. This is how Huffman Coding makes sure that there is no ambiguity when decoding.

Question 7: Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

(A) 7
(B) 8
(C) 9
(D) 10

Correct Answer: (D)

Question 8: Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of:

(A) O(n²)
(B) O(mn)
(C) O(m²)
(D) O(m log n)

Correct Answer: (D)

Question 9: In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

(A) Dijkstra’s algorithm starting from S
(B) Warshall’s algorithm
(C) Performing a DFS starting from S
(D) Performing a BFS starting from S

Correct Answer: (D)

Question 10: Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) ∈ V × V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

(A) Θ( |E|+|V| )
(B) Θ( |E|*|V| )
(C) Θ( |E| log(|V|) )
(D) Θ( |V| )

Correct Answer: (D)

In the dynamic landscape of algorithmic design, Greedy Algorithms stand out as powerful tools for solving optimization problems. Aspirants preparing for the GATE Exam 2024 are poised to encounter a range of questions that test their understanding of Greedy Algorithms. These notes aim to provide a concise and insightful overview, unraveling the principles and applications of Greedy Algorithms that are likely to be scrutinized in the upcoming GATE examination.