. Huffiman code is a way to encode information using variable-length binary strings to represent symbols dependig on the frequency of each individual letter. Specifically, letters that appear more frequently can be encoded into strings of shorter lengths, while rarer letters can be turned into longer binary strings, On average, Huffman code is a more efficient way to encode a message as the number of bits in the output string wil be shorter than if a fixed-length code was used. In addition, this encoding scheme is proven to be unambiguous in the sense that we can easily identify the boundaries between lettes a uqely decrypt an encoded message. That is, no letter'seodig can be the prefix of another letter's encodig (e.g., we cannot have both 00 and 001 as the encoding for two different letters). Huffiman encoding is managed through a full binary tree, called the Huffiman tree. Here, the leaf vertices are letters in the original message. For each internal vertices, the left outgoing edges (branches) are labeled with a 0, and right branches are labeled with a 1. The path from the root to the leaf gives us encoding of the orresponding letter in the leaf (a.) (2 points) An encrypted file contains the following sequence of binary digits Decode the message knoing it was encoded using the Huffiman code given by the tree below G N A I UF (b.) (3 points) Suppose a certain file contains only the following lettes with the coresponding frequencies BCDE FIG 73 930 44 130 28 16 In a fixed-length encoding scheme, each character is given a binary representation with the same number of bits. What is the minimm number of bits required to represent each letter of this file under fixed-length encoding scheme? Describe how to encode all seven letters in this file using the number of bits you gave earlier. What is the length of the encoded file under this encoding scheme? (c.) (5 points) The following is the algorithin for building Huffman tree (Rosen p.764) procedure Huffman(C: letters a, with frequencies tti ,-1, . . . ,R) 1. Fforest of n rooted trees, each consisting of the single vertex a, and weight 2 while F is not a tree 3. Replace the rooted trees T and T, of least weights from F with u(T) te(T') with a tree having a new root that has T as its left subtree and T as its right subtree Label the new edge to T with 0 and the new edge to T" with 1 Assign w(T) + (T') as the weight of the new tree 5. the Huffiman coding for the symbol a is the concatenation of the labels of the edges in the unique path from the root to the vertex Construct the Huff code that enables you to encrypt the same file in part (b) so that you can store it using the least umber of bits. Specify the binary representation for each letter and compute the length of the encoded file under Huffman coding