In class, we introduced the RecursiveHuffman algorithm that given any alphabet A returns an optimal tree T (corresponding to an optimal pre-fix free code E). The same optimal tree T can also be computed using the following non-recursive algorithm:

Algorithm lterativeHuffman(A = {a,fs)); 1. Create a tree-node nz for every r E A with frequency f, = f. Let S = {%) be the set of nodes created. (Note that n. can also be viewed as a single-node tree.) 2. If |S- 1, return the only tree in S 3. Else |S|2 2, do the following: * find the two trees P and Q in S with the minimal frequencies fp and fo; e create a new tree R whose root is a common parent of P and Q, and set the frequency of R to fR= fp+ fQ; . update S = S-{P,Q) + {R): . continue to Step 2 Verify for yourself that the RecursiveHuffman and IterativeHuffman algorithms are essen tially the same. (Try run the two algorithms with the same alphabet and see how the trees "grow" identically!) Improve the run-time: A naive implementation of IterativeHuffman (as well as Re- cursiveHuffman) takes time O(N2), where N = lAl- In this task, assume that the input alphabet is given as an array (as opposed to a set) where letters are sorted according to their frequencies, that is, Show that Huffman Code can be computed in O(N) time a. Describe your O(N)-time algorithm in pseudo-code, and analyze its run-time Hint: Try to modify the IterativeHuffman algorithm. The new algorithm will take the same number of iterations, namely N - 1 iteartions, but in each iteartion, it takes only O(1) time, instead of O(N) time b. Prove that your algorithm is correct Hint: The following lemma will be instrumental to your proof (as well as algorithm esign Lemma: For any alphabet A, let R1,...Rv 1 be the trees constructed in each iteartion in IterativeHuffman(A). It holds that fR, S KfRy-, If you use the lemma, you need to prove it yourself. Algorithm lterativeHuffman(A = {a,fs)); 1. Create a tree-node nz for every r E A with frequency f, = f. Let S = {%) be the set of nodes created. (Note that n. can also be viewed as a single-node tree.) 2. If |S- 1, return the only tree in S 3. Else |S|2 2, do the following: * find the two trees P and Q in S with the minimal frequencies fp and fo; e create a new tree R whose root is a common parent of P and Q, and set the frequency of R to fR= fp+ fQ; . update S = S-{P,Q) + {R): . continue to Step 2 Verify for yourself that the RecursiveHuffman and IterativeHuffman algorithms are essen tially the same. (Try run the two algorithms with the same alphabet and see how the trees "grow" identically!) Improve the run-time: A naive implementation of IterativeHuffman (as well as Re- cursiveHuffman) takes time O(N2), where N = lAl- In this task, assume that the input alphabet is given as an array (as opposed to a set) where letters are sorted according to their frequencies, that is, Show that Huffman Code can be computed in O(N) time a. Describe your O(N)-time algorithm in pseudo-code, and analyze its run-time Hint: Try to modify the IterativeHuffman algorithm. The new algorithm will take the same number of iterations, namely N - 1 iteartions, but in each iteartion, it takes only O(1) time, instead of O(N) time b. Prove that your algorithm is correct Hint: The following lemma will be instrumental to your proof (as well as algorithm esign Lemma: For any alphabet A, let R1,...Rv 1 be the trees constructed in each iteartion in IterativeHuffman(A). It holds that fR, S KfRy-, If you use the lemma, you need to prove it yourself