Huffman coding and probability trees Pinterest is a company that allows you to pin photos that you want to save or share with other users based on their interests. They need their search to be extremely fast. A common approach for search is to build a tree that index searches according to their probability. We're going to explore a simplified version of the approach. Suppose you are given the dictionary made of the following set of words W = {cat, dog, shelf, paper, runner, geometric, vase} with the following probabilities (1/20 x = dog 2/20 x = cat 3/20 x = shelf Pr(X = x) = { 1/20 x = paper 6/20 x = runner 3/20 x = geometric (4/20 X = vase and want to encode the various words as a series of bits. For example dog + 0, cat + 1, ...vase + 0001. That is you want to generate an encoding for your dictionary. Choose one of the following: 1. If you are familiar with Huffman coding use it to find the optimal tree and encoding. What is your average number of bits needed to encode W 2. If you are unfamiliar with Huffman coding provide a principled way to construct this mapping and estimate the average length of your code