1)A data file contains the characters of a, c, e, g, t, u and v. The following table lists the frequencies of the characters in the file.

character	a	c	e	g	t	u	v
frequency	13,000	12,000	9,000	45,000	16,000	4,200	25,000

1.1 Use the shortest fixed-length method to code the characters, and then use the Huffman algorithm to code them. Present the two different coding schemes.

1.2 Estimate the sizes of the files of the same data coded by the two different coding schemes.

2) K1 < K2 < K3 < K4 < K5 are five search keys. They are searched with probabilities 0.05, 0.4, 0.15, 0.3, 0.1 respectively.

2.1 Use the dynamic programming method discussed in class to create an optimal binary search tree for the five keys. Show the calculation details for cell (1,5) in the main table.

2.2 Design a greedy algorithm for creating optimal binary search trees. Represent the algorithm in pseudocode. Show how your algorithm creates a tree for the five keys.