When Deb gets mad, she sends her friend Ahab encoded messages using lines of pennies, each of which is either heads up (H) or tails up (T). Example:
THHHTHTT HTTTTHTHH
Deb also sends a decoding tree, which indicates how to read the message encoded by the pennies. A decod-ing tree starts with two branches, marked (H)eads and (T)ails. Each branch either leads to a letter in the message or another decoding tree. This type of tree is called a Huffman encoding tree, based on the name of its inventor.
Pennies are read from left to right, and each penny indicates which branch of the decoding tree to follow. Whenever a letter is reached, the next letter is decoded starting back at the top of the decoding tree. For example, the message above reads "BAD AHAB", where individual letters are placed in boxes below:
C1. Decode the following messages using the decoding tree shown above:
C2. The following English word from Deb is missing a penny somewhere in the middle. Mark the location and orientation (heads or tails) of the missing penny and decode the message.
Location of the new penny (counting from the left):
Orientation: H T
C3. Deb doesn't want to spend all of her allowance on messages. Design an encoding tree and write the cor-responding encoding for each letter below, such that the encoding requires as few pennies as possible, but still correctly encodes the messages. Assume that the message only contains the letters in the example (e.g., MISP in the first example and ABCDR in the second one). In a Huffman encoding, the encoding of a letter cannot begin with the encoding of another letter. So, for instance, if some letter is encoded as H, then anoth-er one cannot be encoded as HT. In fact, if some letter is encoded as H, then the encoding for any other letter must start with T.
The two examples below are independent. There may be more than one optimal encoding per example. You only need to show one of them.
Total number of coins:
When you are finished with this problem, click on the button below to check your answers.
Checking...
Solution (PDF)
