Please show all work with full explenation of steps. Partial work/incorrect answers will not receive positive feedback.

Find the cost and the structure of an optimal binary search tree for a set of 7 keys with the following probabilities: p[..] = {0.16, 0.12, 0.14, 0.07, 0.15, 0.17, 0.19}. Use the algorithm from the class. BST(p, n)//Input: array p of n probabilities//Output: array c and root for i = 1 to n + 1 c[i, i - 1] = 0//empty tree for d = 0 to n - 1//d is the difference j - i for i = l to n - d j = i + d c[i, j] = infinity sum = 0 for r = i to j sum+ = pr x = c[i, r - 1] + c[r + 1, j] if c[i, j] > x then c[i, j] = x and root[i, j] = r c[i, j]+ = sum return c[..] and root[..] c[i, j] = {0 if j = i= 1, min_i lessthanorequalto r lessthanorequalto j {c[I, r - 1] + c[r + 1, j] + sigma_t = i^j p_t} if i lessthanorequalto j