(Solved): Consider the following symbol frequencies for a five-symbol alphabet: \table[[Symbol,Frequency],[A,. ...
Consider the following symbol frequencies for a five-symbol alphabet: \table[[Symbol,Frequency],[A,.16],[B,.08],[C,.35],[D,.07],[E,.34]] What is the average encoding length of an optimal prefix-free code? [5pts] 3. In terms of
n, where
n=|\Sigma |denotes the alphabet size, what is the maximum number of bits that Huffman's greedy algorithm might use to encode a single symbol? Explain your answer. [5pts] Hint: Think of the different types of trees that could result. 4. Which of the following statements about Huffman's greedy algorithm are true? Assume that the symbol frequencies sum to 1 . (Choose all that apply) [5pts] a. A letter with frequency at least 0.4 will never be encoded with two or more bits. b. A letter with frequency at least 0.5 will never be encoded with two or more bits. c. If all symbol frequencies are less than 0.33 , all symbols will be encoded with at least two bits. d. If all symbol frequencies are less than 0.5 , all symbols will be encoded with at least two bits. Consider the following symbol frequencies for a five-symbol alphabet: \table[[Symbol,Frequency],[A,.16],[B,.08],[C,.35],[D,.07],[E,.34]] What is the average encoding length of an optimal prefix-free code? [5pts]
