Table of contents
1.
Introduction
2.
MCQs
3.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Greedy algorithms

Author yuvatimankar
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A greedy algorithm is a method for solving a problem by selecting the most feasible solution. It doesn’t matter whether the current best result will bring the optimal result. It uses a top-down approach.


Source: prepbytes

The greedy algorithm can be used in any problem if it has the following properties:

  • Greedy choice property: Greedy choice property says that the globally optimal solution can be obtained by making a greedy optimal solution.
  • Optimal substructure: In this property, if the overall optimal solution of the problem corresponds to an optimal solution of its subproblem, then this problem can be solved using the greedy approach. 

MCQs

Q1. Which of the following Algorithms is not a Greedy Algorithm?

a.Prim's algorithm

b.Dijkstra's algorithm

c.Huffman Coding

d.Kruskal's algorithm

e.Bellman ford shortest path algorithm

Ans: e

Q2. Five files F1,F2,F3,F4,F5 have 120,80,50,100,300 records respectively. What should be the order to store them to optimize act? Assume each record is obtained with a similar recurrence.

a.F3,F2,F5,F1,F4

b.F2,F3,F4,F1,F5

c.F1,F2,F3,F5,F4

d.F2,F4,F1,F2,F3

Ans: b

This question is based on Optimal storage, which uses a greedy approach to find the optimal time to retrieve records. There are ‘n’ records of length ‘L’ to be stored in computer tape. Related to each record, the ‘i’ record is of length Li. So to retrieve these records optimally, we need to store them in increasing order of length Li.Therefore, the correct order is F2,F3,F4,F1,F5.

Q3. The time complexity of Huffman Coding is :

a.O(n^2)

b.O(nlogn)

c.O(n)

d.O(n(logn)^2)

Ans: b

O(nlogn) in which ‘n’ is the number of unique characters. For n nodes, extractMin() is called 2*(n-1) times.extractMin takes O(logn) time as it calls minHeapify(). Therefore, the overall time complexity is O(nlogn). Know more about Huffman coding.


Q4. A text is made up of characters a,b,c,d,e each occurring with the probability of 0.12, 0.40, 0.16 , 0.08, 0.24 respectively. What will be the average length of the optimal Huffman coding Technique?

a.2.16

b.2.26

c.2.20

d.2.15

Ans: a

a= 0.12 b =0.40 c=0.16 d=0.08 e=0.24


Huffman tree:


Length for each character= no. of bits * frequency of occurrence.

a = 4* 0.12

   = 0.48

b = 1 * 0.4

   = 0.4

c = 3 * 0.16

   = 0.48

d = 4 * 0.08

   = 0.32

e = 2 * 0.24

   = 0.48

Average length = 0.48 + 0.4 + 0.48 + 0.32 + 0.48 = 2.16

Q5. A letters a,b,c,d,e with probability ½,¼,⅛,1/16, 1/32 respectively. The normal length of the Huffman code is :

a.2.25

b.2.30

c.1.9375

d.2.18

Ans: c

Average length = (1* 1/2 + 2 * 1/4 + 3 * 1/8 + 4 * 1/16 + 5 * 1/32 )

 = 1.9375

Q6. Where does the data in a tree always occur in Huffman coding? 

a.Left subtree

b.Right subtree

c.Roots

d.leaves

Ans: d

Data is always stored at the tree's leaves to compute the codeword effectively in Huffman coding.

Q7. From the diagram given below, the computed codeword for c is:


 

Source: sanfoundary

a.110

b.101

c.011

d.111

Ans: a

By tracing the node's path from root to leaf assignment left branch 0 and right branch 1, the codeword for c is 110.

Q8. The runtime of the Huffman encoding algorithm is:

a.O( Clog C)

b.O(C)

c.O( log C)

d.O( N log C)

Ans: a

Q9. Consider a job scheduling problem with four jobs Q1,Q2,Q3,Q4 and with corresponding deadlines: (d1,d2,d3,d4) = (4,2,4,2) . Which of the following is not feasible without violating any job schedule?

a.Q2,Q4,Q1,Q3

b.Q4,Q1,Q2,Q3

c.Q4,Q2,Q1,Q3

d.Q4,Q2,Q3,Q1

Ans: b

In Option 2, the job is done randomly, not according to the deadline given; therefore, it is not a feasible schedule.

Q10. What is the codeword for ‘a’ in the following diagram?

 

Source: Sanfoundary

 

a.100

b.111

c.010

d.011

Ans: d

By tracing the node's path from root to leaf, the codeword found for a is 011.

Key Takeaways

In this article, we have discussed some of the quality MCQs of the Greedy algorithm and also some of the previously asked questions in GATE.

Check out this problem - Frog Jump

If this article was helpful, share it as much as possible. You can visit Code studio and Greedy algorithm to learn more on such topics.

 

Live masterclass