Proofs of Algorithm Correctness and Runtime Estimates · Application: Data Compression (Optional)

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Problem. Which of the following codes are not prefix-free over the alphabet \(\Sigma = \{a, b, c, d\}\)?

1 point

  1. \(\phi(a) = 0\), \(\phi(b) = 10\), \(\phi(c) = 110\), \(\phi(d) = 111\)

  2. \(\phi(a) = 1\), \(\phi(b) = 01\), \(\phi(c) = 001\), \(\phi(d) = 000\)

  3. \(\phi(a) = 01\), \(\phi(b) = 10\), \(\phi(c) = 010\), \(\phi(d) = 101\)

  4. \(\phi(a) = 00\), \(\phi(b) = 01\), \(\phi(c) = 10\), \(\phi(d) = 11\)