3. Huffman Code (50 points) 1) (5p) Generate a binary Huffman tree from the letter frequencies in the tongue twister: She sells sea shells by the seashore. Do include the space character (6 of them) in your tree, no need to include the period, and treat all letters as lower case. Letter Frequency table. Make sure they add up to be 36. letter h space 1 b y e t o r freq 2) (15p) Prefix Code tree with Huffman Code. Please study the steps of creating a Huffman code tree as in Appendix. At each step, we identify the two entries with the smallest frequencies. Note when there are ties, choose any of them. Depends on which two entries we select and which will be use as left subtree/right subtree, the final coding tree will be different. 3) (5p) Prefix Code word table letter Huffman code in binary S space 1 b y t I 4) (5p) If you user acsii code to represent the input of 36 characters, we will need 36*8=288 bits. With the above Huffman codeword, what is the total number of bits to encode the input? 5) (10p) Data structures in the Huffman code as we discussed in class a. How are trees being used in the algorithm? What is the data stored in the tree node? b. How is PQ used in the algorithm? Be specific about what is the key, what is the value for the PQ. When will be inserted and removed from the P