ALGORITHMICS/HUFFMAN CODE

(please provide full detailed answers to the multi part questions)

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:

1- a- Give the tree defining the encoding by applying algorithm 1 for a text characterized by the following frequencies (step 1 of the algorithm has therefore already been performed):

letter/ frequency :

b- What are the respective complexities of steps 1, 2, and 3 of Algorithm 1?

c-What is the complexity of building the new tree at each iteration of step 4?

d-Show that it is possible to insert this new tree in the list sorted 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.

e-Deduce the complexity of algorithm 1 as a according/using n and k

a b e d 16 f 5 45 13 12 9