1. In our discussion of Huffman codes, each code-word is a binary string, i.e., using only an alphabet of {0,1}. Suppose now we have an alphabet of three characters {0, 1,2}, so the code-words would be strings over that three-character alphabet. Describe an algorithm to build an optimal Huffman code over a three character alphabet, given a set of symbols and the frequencies of those symbols.

2. Building an optimal binary search tree for a set of names. A proposed greedy algorithm to build an optimal binary search tree for names is to place the shortest name, denoted N, at the root of the tree. Then, because it is a binary search tree, every name in the set that is alphabetically before N must be in the left subtree of the root; and every name in the set that is alphabetically after N must be in the right subtree of the root. Then to pick the root of the left subtree, find the shortest name in the left set; and to pick the root of the right subtree, find the shortest name in the right set. Continue in this way to build a whole binary search tree. Give an example where this greedy algorithm does not produce an optimal binary search tree.