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.
- GATE 2007 CS Q76 – 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?
- GATE 2007 CS Q77 – 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…
- GATE 2021 CS (CS2) Q36 – Assign a binary prefix code to each letter of abbccdddee. For letters with equal frequencies, a letter earlier in dictionary order must have code…
- GATE 2017 CS (CS2) Q60 – 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…
- GATE 2014 CS (CS2) Q48 – 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…
- GATE 2017 CS (CS1) Q15 – Consider the following table: Algorithms Design Paradigms --- --- (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall…
- GATE 2015 CS (CS1) Q13 – Match the following: (P) Prim's algorithm for minimum spanning tree (Q) Floyd-Warshall algorithm for all pairs shortest paths (R) Mergesort (S)…
- GATE 2018 CS Q58 – 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)…