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 Key₁ , Key₂ , ... , Keyk-1 and Key_k+1 , Key_k+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.