1. This question concerns the dynamic programming algorithm for computing a binary tree, discussed in class...

  

Transcribed Image Text:

1. This question concerns the dynamic programming algorithm for computing a binary tree, discussed in class in and in the notes. Suppose we are given the following data, consisting of 8 key values and the frequency with which each key is accessed: i 1 2 3 4 5 6 7 8 Data Pi A B D E F G H 0.09 0.17 0.26 0.05 0.06 0.12 0.10 0.15 (a) For each i and j in the appropriate range, give the values of E[i, j] and root[i, j]. (b) Draw the optimal binary tree for the data given above. (c) What is the weighted lookup cost of the optimal binary tree? Explain briefly how you computed it. 1. This question concerns the dynamic programming algorithm for computing a binary tree, discussed in class in and in the notes. Suppose we are given the following data, consisting of 8 key values and the frequency with which each key is accessed: i 1 2 3 4 5 6 7 8 Data Pi A B D E F G H 0.09 0.17 0.26 0.05 0.06 0.12 0.10 0.15 (a) For each i and j in the appropriate range, give the values of E[i, j] and root[i, j]. (b) Draw the optimal binary tree for the data given above. (c) What is the weighted lookup cost of the optimal binary tree? Explain briefly how you computed it.

Answer rating: 100% (QA)

The image depicts a question which refers to a dynamic programming approach to create an optimal binary search tree BST given certain key frequencies In such a tree the cost of searching for a key is ... View the full answer