Algorithm Design & Analysis Questions

1. Using Huffman code, we can compress the bits used for saving the characters in a file:

Total bits used for saving the characters in table 1 is 264 bits using standard ASCII 8 bits for a character. Using Huffman code encoding in Table 2, the total bits used is 126 bits.

The problem:

• Input: list of characters such as table 1
• Output: total bits using Huffman code encoding (table 2)
• Task: Design an algorithm in C/C++ code to print the total bits using Huffman code encoding and write down the Algorithm analysis. The complexity of the algorithm must be in O(n) and proof it!
• PS: you dont need to sort the input since the input is already sorted!

P.S:

- Please answer in a proper format - Please answer in a typed or softcopy format - Please don't do it with pen or pencil, do it with software or tools - If you want to ask any question, ask it in the comment section, I will try to answer it

Thanks!

Table. 1. Characters count. Character Frequency E 1 F 1 H 1 M 1 R 1 T 1 Y 1 2 12 D G 2 2 Table 2. Character bit using Huffman code Character Bits Frequency Total Bits Space 3 4 12 A 3 4 12 S 3 4 12 D 4 2 8 G 4 2 8 1 4 3 L 4 2 8 N 4 3 12 O 4 2 8 Y 4 1 4 E 5 1 5 F 5 1 5 H 5 1 5 . 5 1 5 R 5 1 5 T 5 1 5 Total: 126 3 L 0 1 N Space 2 2. 3 3 4 S 4 4 Table. 1. Characters count. Character Frequency E 1 F 1 H 1 M 1 R 1 T 1 Y 1 2 12 D G 2 2 Table 2. Character bit using Huffman code Character Bits Frequency Total Bits Space 3 4 12 A 3 4 12 S 3 4 12 D 4 2 8 G 4 2 8 1 4 3 L 4 2 8 N 4 3 12 O 4 2 8 Y 4 1 4 E 5 1 5 F 5 1 5 H 5 1 5 . 5 1 5 R 5 1 5 T 5 1 5 Total: 126 3 L 0 1 N Space 2 2. 3 3 4 S 4 4