Problem
1. Given the binary tree corresponding to a binary prefix code, write an algorithm that determines the code words for all the characters. Determine the time complexity of your algorithm..
2. Write the dynamic programming algorithm for the 0-1 Knapsack problem.
3. Use a greedy approach to construct an optimal binary search tree by considering the most probable key, Key , for the root, and constructing the left and right sub trees for Key1 , Key2 , ... , Keyk-1 and Keyk+1 , Keyk+2, ... , Key recursively in the same way.
(a) Assuming the keys are already sorted, what is the worst-case time complexity of this approach? Justify your answer.
(b) Use an example to show that this greedy approach does not always find an optimal binary search tree.