Algorithm Design and Analysis

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

Total bits used for saving the character in table 1 is 264 bits using standard ASCII 8 bits for 1 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 pseudocode/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!

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