The GATE Grind

GATE Algorithms: Greedy Techniques – Previous Year Questions

8 GATE previous year questions on Greedy Techniques (Algorithms, Computer Science) with answers and explanations, from every paper.

8 questions worth 14 marks in all (2 1-mark, 6 2-mark). Asked between 2007 and 2021, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q76 (2 marks, Multiple choice) – Letters a, b, c, d, e, f have probabilities1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which list is their Huffman code in that order?
  2. GATE 2007 CS Q77 (2 marks, Multiple choice) – Letters a, b, c, d, e, f have probabilities1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of the code in the correct answer…
  3. GATE 2021 CS (CS2) Q36 (2 marks, Multiple choice) – Assign a binary prefix code to each letter of abbccdddee. For letters with equal frequencies, a letter earlier in dictionary order must have code…
  4. GATE 2017 CS (CS2) Q60 (2 marks, Numerical answer) – Characters P,Q,R,S,T have probabilities 0.22,0.34,0.17,0.19,0.08. A 100-character message is Huffman encoded. Find its expected encoded length in…
  5. GATE 2014 CS (CS2) Q48 (2 marks, Numerical answer) – Sorted sequences P,Q,R,S,T have lengths 20,24,30,35,50. Merge them into one by merging two sequences at a time. Find worst-case comparisons for an…
  6. GATE 2017 CS (CS1) Q15 (1 mark, Multiple choice) – Consider the following table: Algorithms Design Paradigms --- --- (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall…
  7. GATE 2015 CS (CS1) Q13 (1 mark, Multiple choice) – Match the following: (P) Prim's algorithm for minimum spanning tree (Q) Floyd-Warshall algorithm for all pairs shortest paths (R) Mergesort (S)…
  8. GATE 2018 CS Q58 (2 marks, Numerical answer) – Consider the weights and values of items listed below. Note that there is only one unit of each item. Item number Weight (in Kgs) Value (in Rupees)…