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.