# Was my Huffman coding solution wrong?

I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities:

A: 0.15
B: 0.2
C: 0.55
D: 0.1


I encoded them as follows:

A: 110
B: 10
C: 0
D: 111


But my lecturer told me that this results seems odd and gave me just a fraction of points for my solution. I argued that all my encodings have unique prefixes. I also said that all my encodings has same length as his (he compared my solution with his reference solution), thus they have same entropy.

Do I really don't understand Huffman codding? I found the theory behind this algorithm amazing so I would like to know.

• Find a different instructor. Apr 30, 2018 at 8:21
• @YuvalFilmus This was one of the last exam on this university. Even though I would like to study there for a master's degree, he is one of the reason why I applied to different universities. I suspect him that he hate me. Apr 30, 2018 at 8:32
• We can't help you with that. Your code is a Huffman code, though perhaps not the one produced by the particular implementation you were taught. Apr 30, 2018 at 8:33
• @YuvalFilmus Sorry, I know that. I'm just disappointed from that situation. And thank you very much for checking my answer! Apr 30, 2018 at 8:38
• If you are interested in how to deal with your instructor, you might want to check academia.SE. Apr 30, 2018 at 13:43

In your case, there is only one choice for the two leaves, but there are several choices for the order (two at each of the three iterations of the algorithm). Hence your distribution supports 8 different "Huffman codes". It might be that the one you chose is not the canonical one which is produced by the specific implementation you were taught in class. The 8 Huffman codes for your distribution are: $$\begin{array}{c|l|l|l|l|l|l|l|l} A & 110 & 111 & 100 & 101 & 010 & 011 & 000 & 001 \\\hline B & 10 & 10 & 11 & 11 & 00 & 00 & 01 & 01\\\hline C & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\\hline D & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000\\ \end{array}$$