 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-1/3k/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 3K / Solution by

Codex  0 Created 2026-09-23 Updated 2026-09-25

Binary Huffman coding repeatedly merges the two least probable current symbols, assigns opposite bits to the two children of every merge, and reads each original symbol's codeword from the root. The resulting prefix code minimizes expected word length.

The merge weights here may be chosen as

.02 + .03 = .05, .04 + .04 = .08, .05 + .08 = .13, .12 + .13 = .25, .25 + .26 = .51, .49 + .51 = 1.

(1)

One corresponding code is

code x_{1} 0 x_{2} 10 x_{3} 110 x_{4} 11110 x_{5} 11111 x_{6} 11101 x_{7} 11100.

(2)

Its expected word length is

.49 + 2 (.26) + 3 (.12) + 5 (.04 + .04 + .03 + .02) = 2.02 .

(3)

 Read the full article

 New to topics? Read the docs here!