Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 3H (Coding & Cryptography)

Table of contents
- a 3H
  - Solution a
- b 3H
  - Solution b
- c 3H
  - Solution c

a

Solution

Apply Huffman coding. Combining weights

.02 + .03 = .05, .04 + .04 = .08, .05 + .08 = .13, .13 + .14 = .27, .27 + .28 = .55

gives, for example,

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

Any consistent interchange of siblings is equivalent.

b

Solution

For the binary code above, the lengths are

1, 2, 3, 5, 5, 5, 5

. Thus

\overset{ˉ}{ℓ} = .45 + 2 (.28) + 3 (.14) + 5 (.04 + .04 + .03 + .02) = 2.08.

This is optimal by Huffman coding.

c

Solution

The ternary merges are

(.02, .03, .04) \mapsto .09

, then

(.04, .09, .14) \mapsto .27

, then

(.27, .28, .45) \mapsto 1

. One code is

x_{1} : 0, x_{2} : 1, x_{3} : 20, x_{4} : 21, x_{5} : 220, x_{6} : 221, x_{7} : 222.

Its expected length is

.45 + .28 + 2 (.14 + .04) + 3 (.04 + .03 + .02) = 1.36.

 Ancestors (9)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version