Consider the following string of characters:

UUDDLRLRBASUUUUDDLA

• If you were to encode this string using the same number of bits per character, how many bits would be required per character? (Notice that there are seven distinct characters in the string.)
  
  

• How many bits would be required to encode the entire string?
  
  

• Compute the frequency of each of the characters in the string:
  
  U D L R B A S
  
  

• Now, build the Huffman tree corresponding the the sequence of characters above. When creating a new node, place the smaller frequency child on the left. Break ties alphabetically. In other words, if two subtrees have the same frequency, select the one containing the letter that is earliest in the alphabet.

  
  
  
  
  
  
  
  
  
  
  
  

• How many bits were required for your encoding?
  
  

• What was the compression ratio? (uncompressed bit count / compressed bit count)?

Use the following Huffman tree to decode the binary sequences below.

• 10011000011000010101110100
  
  

• 011010
  
  

• 10110100111000110111
  
  

• 0101111110100111100111110001110
  
  

• There are 23 characters in the strings above, with 13 distinct characters. If we had used a fixed-length encoding, how many bits would be required to encode each string? What is the compression ratio for each string?