Greedy looks simple: take the best choice now and never look back. Yet Huffman tree questions consume several minutes if you build them carelessly.
Attempt each MCQ before reading its explanation. Ten of the twelve are previous-year questions, drawn from GATE 2006, GATE 2007, GATE 2021, UGC NET, ISRO, Coal India, Bihar STET and TPSC papers. More than sixty greedy and Huffman questions sit in the Algorithms learn module.
What a greedy algorithm actually promises
A greedy algorithm makes the locally optimal choice at each step and commits. It reaches a global optimum only with the greedy-choice property and optimal substructure. Dynamic Programming Explained with a Worked 0/1 Knapsack shows how DP solves every subproblem before it commits to anything.
Q1. What is the key principle driving a greedy algorithm?
(a) Making the globally optimal choice at each stage
(b) Making the locally optimal choice at each stage
(c) Solving subproblems and combining their solutions
(d) Reducing the problem size at each stage
Answer: (b). Option (a) is the trap: greedy cannot see the global optimum. It commits to the best local option. Option (c) is divide and conquer or DP language; (d) is decrease and conquer.
Q2. Which of the following standard algorithms is not a Greedy algorithm?
(a) Dijkstra's shortest path algorithm
(b) Prim's algorithm
(c) Bellman-Ford shortest path algorithm
(d) Huffman Coding
Answer: (c). Dijkstra chooses the closest unvisited vertex, Prim the cheapest crossing edge, and Huffman the two least frequent nodes. Bellman-Ford relaxes every edge n - 1 times and revises estimates it has already made, which greedy forbids. Dijkstra is traced step by step in Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step.
Where greedy breaks down
Greedy fails when the locally best choice blocks a better complete solution. Fractional knapsack is greedy-solvable because an item can be split. The indivisible choice in 0-1 knapsack is what breaks the argument.
Q3. Coal India 2017: Which of the following problem cannot be solved using greedy approach?
(a) 0-1 knapsack
(b) Minimum spanning tree
(c) Huffman code
(d) Job scheduling
Answer: (a). Consider capacity 10 with A(weight 7, value 49, ratio 7), B(5, 30, 6), and C(5, 30, 6). Greedy by ratio takes A for value 49 and leaves capacity 3, where nothing fits. The optimum takes B and C, fills all 10 units, and gives value 30 + 30 = 60.
Q4. UGC NET Paper 2 December 2025: Which of the following are limitations of Greedy algorithms?
A. They always fail for NP hard problem.
B. They may not give the optimal solution for all problems.
C. They are faster than dynamic programming in most cases.
D. They make local choices without looking ahead.
(a) A, C Only
(b) B, C Only
(c) A, B, C, D
(d) B, D Only
Answer: (d). B and D are limitations. A is false because greedy can approximate NP-hard problems such as set cover and vertex cover. C is an advantage, not a limitation. Read what the stem asks.
Huffman coding in one idea
Huffman coding repeatedly merges the two least frequent nodes. Frequent symbols stay near the root with short codes; rare ones move deeper. The lossless result is prefix-free, so no codeword prefixes another.
Q5. ISRO 2025: Huffman coding algorithm works on the principle of
(a) Randomization of symbols
(b) Key based portioning of symbols
(c) Hashing of symbols
(d) Frequencies of input symbols
Answer: (d). Frequencies drive the construction. Symbols are not randomised, hashed, or key-partitioned. Frequency decides how long each codeword is, and no symbol information is thrown away, so the encoding stays lossless.
Q6. Bihar STET 2025: In Huffman coding, which characters are usually assigned shorter codes?
(a) Characters with higher frequency
(b) Characters with lower frequency
(c) Characters with longer ASCII values
(d) Characters with shorter ASCII values
Answer: (a). Total length sums frequency multiplied by code length. Minimising it puts short codes on frequent symbols. ASCII values never enter Huffman construction.
Building the tree: procedure and cost
Create one leaf per symbol in a min-priority queue. Extract the two smallest, merge them with their summed weight, reinsert, and repeat until one root remains.
Q7. UGC NET June 2025: The correct sequence of constructing Huffman tree is
A. Repeat until root formed
B. Create leaf nodes
C. Build priority queue
D. Combine lowest frequency nodes
(a) B, C, A, D
(b) D, B, A, C
(c) B, C, D, A
(d) C, A, B, D
Answer: (c). Create the leaves, build the queue that orders them, combine the two lowest-frequency nodes, then repeat until the root forms.
Q8. TPSC Senior Informatics Officer 2025: What is the time complexity of Huffman Coding?
(a) O(N)
(b) O(N log N)
(c) O(N (log N)^2)
(d) O(N^2)
Answer: (b). There are n - 1 merges with O(log n) heap operations, so the standard construction is O(n log n). Sorted frequencies permit a linear two-queue method, but these options assume a heap.
One tree, two GATE questions, worked end to end
For the next two questions, build the tree once. Merge e(1/32) + f(1/32) = 1/16; d(1/16) + ef(1/16) = 1/8; c(1/8) + def(1/8) = 1/4; b(1/4) + cdef(1/4) = 1/2; and a(1/2) + bcdef(1/2) = 1. Labelling every left branch 0 and right branch 1 gives a = 0, b = 10, c = 110, d = 1110, e = 11110, and f = 11111.
Q9. GATE 2007: 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
Answer: (d). Expected length is the sum of probability multiplied by depth:
1/2(1) + 1/4(2) + 1/8(3) + 1/16(4) + 1/32(5) + 1/32(5)
= 0.5 + 0.5 + 0.375 + 0.25 + 0.15625 + 0.15625
= 1.9375 bits.
A fixed-length code needs ceil(log2 6) = 3 bits per symbol, so Huffman saves just over one bit per symbol on this alphabet. The rest of this pattern is drilled in the greedy and Huffman previous-year set.
Q10. GATE 2007: 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?
(a) 0, 10, 110, 1110, 11110, 11111
(b) 11, 10, 011, 010, 001, 000
(c) 11, 10, 01, 001, 0001, 0000
(d) 110, 100, 010, 000, 001, 111
Answer: (a). Read the codes from the tree. The distractors produce Q9's other averages: (c), with lengths (2, 2, 2, 3, 4, 4), gives 2.1875; (b), with (2, 2, 3, 3, 3, 3), gives 2.25; and fixed-length (d) gives 3. Each probability except f equals all smaller probabilities combined, forcing this chain for both questions. See the exact solved GATE 2007 code-assignment question.
Decode and count: the harder GATE pattern
Prefix-free codes are decoded greedily as well. Read the bits left to right and cut as soon as what you hold matches a codeword, because no codeword can be the opening of another one.
Counting the encoded length has a shortcut worth knowing. Each merge you perform sits above every symbol in the two nodes it joins, so it adds one bit to each of them, and the frequencies underneath it total the merged weight. A merge of weight w therefore adds exactly w bits. Adding up the weights of all the merges gives the whole encoded length, which is quicker than multiplying frequency by depth symbol by symbol.
Q11. GATE 2006, Information Technology paper: The characters a to h have frequencies based on the first 8 Fibonacci numbers as follows:
a: 1, b: 1, c: 2, d: 3, e: 5, f: 8, g: 13, h: 21
A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the code 110111100111010?
(a) fdheg
(b) ecgdf
(c) dchfg
(d) fehdg
Answer: (a). Successive smallest-node merges produce the skewed tree, giving h = 0, g = 10, f = 110, e = 1110, d = 11110, c = 111110, a = 1111110, and b = 1111111. Match each complete prefix from left to right:
110 | 11110 | 0 | 1110 | 10 = f | d | h | e | g
The sequence is fdheg. Work it on the exact solved GATE 2006 decoding question.
Q12. GATE 2021 Set 2
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties:
For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.
Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?
(a) 21
(b) 23
(c) 25
(d) 30
Answer: (b). Frequencies are a:1, b:2, c:2, d:2, e:3. Respect the tie rule by pairing a with d, the dictionary-latest of the three frequency-2 letters:
Merge a(1) + d(2) = 3.
Merge b(2) + c(2) = 4.
Merge e(3) + ad(3) = 6.
Merge 4 + 6 = 10.
The minimum encoded length is the sum of merge totals: 3 + 4 + 6 + 10 = 23. Cross-checking by depths gives b = 2, c = 2, e = 2, a = 3, d = 3, so 1(3) + 2(2) + 2(2) + 2(3) + 3(2) = 3 + 4 + 4 + 6 + 6 = 23. Option (d) is the fixed-length baseline, 10 characters multiplied by 3 bits. Open the exact solved GATE 2021 question.
The short version and your next step
Greedy means taking the locally best choice and committing to it.
Correct greedy solutions need the greedy-choice property and optimal substructure.
Bellman-Ford and 0-1 knapsack are standard non-examples.
Huffman repeatedly merges the two smallest frequencies and takes O(n log n) with a heap.
Frequent symbols get short codes. Encoded length is the sum of merge totals, and decoding uses prefix matching.
Every GATE question above is solved step by step inside GATE Guidance by Sanchit Sir, alongside the rest of the greedy and Huffman practice; GATE CS preparation options lists the ways in. Now hide the answers and rebuild both worked trees, the GATE 2007 one from the halving probabilities and the GATE 2006 one from the Fibonacci frequencies.
