Create a C program.

1. Be sure to understand ordinary (greedy) Huffman codes and the dynamic programming solution for the optimal matrix multiplication ordering problem first. 2. The code for filling in the cost matrix will be very similar to optimal matrix multiplication ordering. You are not required to include the cost matrix in your output. 3. Outputting the optimal order-preserving Huffman code tree is just like outputting the tree for the optimal matrix multiplication ordering. 4. Determining the bit string for each character requires navigating down the tree. Going left gives a 0, going right gives a 1. (DON'T USE Recursion)

The first number in the data is size of the file.

use data:

15 0.022222222 0.044444444 0.066666667 0.088888889 0.111111111 0.111111111 0.088888889 0.066666667 0.044444444 0.022222222 0.022222222 0.044444444 0.066666667 0.088888889 0.111111111

output:

probabilities sum to 1.000000 Code tree for exact: 14 12 14 cost 0.422222 13 12 13 cost 0.155556 12 6 14 cost 1.688889 11 9 11 cost 0.133333 10 9 10 cost 0.044444 9 8 11 cost 0.266667 8 6 11 cost 0.711111 7 6 7 cost 0.155556 6 0 14 cost 3.777778 5 4 5 cost 0.222222 4 0 5 cost 1.088889 3 0 3 cost 0.422222 2 0 2 cost 0.200000 1 0 1 cost 0.066667 0 Codes & prob*# of bits 0 00000 0.111111 1 00001 0.222222 2 0001 0.266667 3 001 0.266667 4 010 0.333333 5 011 0.333333 6 1000 0.355556 7 1001 0.266667 8 1010 0.177778 9 101100 0.133333 10 101101 0.133333 11 10111 0.222222 12 1100 0.266667 13 1101 0.355556 14 111 0.333333 Expected bits per symbol 3.777778

(Aside) Like optimal matrix multiplication, the order-preserving Huffman code problem mentioned in Notes 06 requires a solution with the leaves ordered (according to an alphabet). The cost function is based on minimizing the expected bits/symbol under this restriction: y+ i=left {c(left.k1+C(A+l,right)} min lefisk