Optimal Binary Search Tree $($BST$)(($Section $8\mathrm{.}3)$

Consider the problem of finding the optimal BST for nodes $1$ through $8($with letters A$,$ B$,$ C$,$ D$,$ E$,$ F$,$ G$,$ H$),$ with

probabilities $p_1-p_8$ as shown below.

The above tables contain partial values of the $P,C,$ and $R$ arrays, respectively, after applying Dynamic

Programming to this problem.

a$)$ Complete the $C$ and $R$ arrays and then draw the optimal Binary Search Tree for letters A through $H.$ Show all

details of how you determined the optimal tree and the computations on the $C$ and $R$ arrays.

b$)$ What is the average height of the tree? Show all your work without skipping any details.