ALGORITHMICS/HUFFMAN CODE

EXO1:

We want to compress a text file of length n in which k different characters appear. The aim is to store it at low cost or to transmit it using as little data as possible.

Algorithm 1 Code-prefix : (T: array of length n using k different characters) Inputs: A text T of length n in which k different characters appear. Outputs: A binary tree representing a prefix code to encode the text. 1. Calculate the frequencies (F1,..., Fk) of the letters of the text; 2. Create for each j in {1,. . . k} a tree with only one root with the value Fj; We obtain a forest of k trees; 3. Sort the trees according to the value of their root; 4. as long as there are at least two trees in the forest do - Choose the two trees A1 and A2 whose roots carry the two smallest values; - Replace A1 and A2 by a new tree such that: the two children of its root are A1 and A2; its root carries as value the sum of the roots of A1 and A2; the edges linking the root to its children A1 and A2 are valued 0 and 1 respectively; - Update the sorted list of trees according to the value of their roots; end while 5. Return the tree;

question:(please detail the answers with proper explanation)

1-a)Show that it is possible to insert the new tree from step 4 in the sorted list according to the value of their root in O (log (k)). For that, you will give an algorithm performing this task and you will determine its complexity.

b-)Deduce the complexity of algorithm 1 using n and k