MadeEasy Test Series: Algorithms - Greedy Algorithm

Question

Consider the following message:

The number of bits required for huffman encoding of the above message are __________?

My Strategy:- 

But the answer given is 52bits i used standard Algorithem 

Made Easy Solution :- 

Comments

Yes Made easy solution is correct because you have to choose two smallest element means

list is 5,5,7,9

in 1st phase -  5,5 need to be selected.

now list is 7,9,10

in 2nd phase - 7,9 need to be selected

now list is 10,16

in 3rd phase - 10,16 will give the 26.

---

I didn't understood the solution sir,Question asks for bits required to encode mssg right,then why cant we simply use the huffmann encoding to find the bit patterns and multiply with frequency to get answer.Why am i wrong?

---

your huffamn tree is wrong, below are the steps for creating tree-

Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)

2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

 now in your question -

reference- https://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

---

Yeah sir sorry i know the standard algorithm i made a hell of a silly mistake.Thanks though

Answer 1

Steps to build Huffman Tree
 

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)

2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with the frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

Character	Frequency
p	7
q	9
r	5
s	5

Extract two minimum frequency nodes . Add a new internal node with frequency 5 + 5 = 10.

    

character	frequency
p	7
q	9
rs	10

Extract two minimum frequency nodes . Add a new internal node with frequency 7 + 9 = 16.

character	frequency
pq	16
rs	10

Character	bits
p	10(2 bits)
q	11 ( 2 bits)
r	00 ( 2 bits )
s	01 ( 2 bits )

The number of bits required for Huffman encoding: $( 7 + 9 + 5 + 5 ) * 2 = 52 \  bits$

Comments

Oh No.Hell of a silly mistake i did thank you Sir

---

Plz, don't call me Sir

---

I have a doubt in this question...they have arranged the numbers in ascending order and then applied huffman algo, here they don't rearrange after calculating which should be done? Please correct me if I'm wrong and tell the right way to do this...accorfing to me 0.20 node should be at left of 0.22