Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the weights: 10, 12, 13, 16, 17, 17.

(a) Construct an optimal coding scheme for the weights given by using a tree.

(b) What is the total weight of the tree you found in part (a)?

share|improve this question
2  
This is an easy question about Huffman coding; can you at least take the first step? –  Brian M. Scott Dec 6 '12 at 22:30
1  
would you just have all of the numbers at the bottom of the tree and keep adding up the two smallest ones so you would have 10+12, 13+16, 17+17, and then 22+29, and then lastly 34+51 to get a total weight of 85? –  helpme Dec 7 '12 at 0:38
    
That’s the right start. Now just organize that into tree form and use the tree to specify the codes for the six weights, and you’re done. –  Brian M. Scott Dec 7 '12 at 0:41
    
i dont know how to specify the codes for the six weights –  helpme Dec 7 '12 at 1:50
    
On this site, it's considered good manners to click on the checkmark below an answer you find acceptable, since that gives a reputation boost to both you and the answerer. @Brian and I have provided good answers; why not be generous and check his? –  Rick Decker Dec 11 '12 at 2:14
show 1 more comment

2 Answers 2

I presume that you can construct the tree, given the hints you've been offered. Once that's done, at each non-leaf node, arbitrarily assign a $0$ and a $1$ to each branch, Then the code for each leaf node is just the sequence of these branch values, reading from the top to the bottom. For example, if the leaf nodes contain 10, 12, 13, 16, 17, 17, reading from left to right, then assigning $0$ to each left branch and $1$ to each right branch gives you the codes $$ \begin{align} 10 &: 000 \\ 12 &: 001 \\ 13 &: 010 \\ 16 &: 011 \\ 17 &: 10 \\ 17 &: 11 \\ \end{align} $$ along with 31 other equally good codes.

share|improve this answer
add comment

This is the tree that Rick Decker used in his answer. Each node of the tree that isn’t a leaf has two edges leading down from it; the one to the left is labelled with a red $0$ and the one to the right with a red $1$. Think of the tree as a road map; a string of red numbers can be used to describe how to get from the root ($85$) to one of the leaves. To get from the root to the leaf $13$, for instance, you must go left ($0$), then right ($1$), then left ($0$) again, so the route is $010$, and that’s the code assigned to the weight $13$ leaf.

Notice that the most heavily weighted leaves $-$ the two $17$’s $-$ are closest to the root and so have the shortest codes; this is what makes the Huffman encoding efficient.

enter image description here

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.