1. We saw in the lecture that every symbol of an alphabet of size k >1 can be encoded using at most [log k] many bits by assigning to every alphabet symbol an index i and then encoding
i in binary. Recall that in computer science logarithms are usually to base two.
(a) Develop an algorithm that given a natural number i computes the binary representation
of .
(b) Inspecting your algorithm, can you argue that the binary encoding of any i > 0 has
1 + Llog | many bits?