$.$ Consider a sorted array A $=[$a$1,$ a$2,...,$ an$]$ of n distinct values: a$1<$ a$2<...<$ an$.$ If X represents the variable being searched for, you also have the probabilities Pi and Qi as discussed in class $($Pi $=$ P r$[$X $=$ ai $]$ for i $=1,2,...,$ n and Qi $=$ P r$[$ai $<$ X $<$ ai$+1]$ for i $=0,1,...,$ n and a$0=$ and an$+1=+$$.$ Suppose you have written code for a dynamic programming algorithm such as the one described in class to compute the optimal binary search tree and you have all the necessary values that were computed: W$($i$,$ j$),$ T$($i$,$ j$),$ C$($i$,$ j$)$ and R$($i$,$ j$).$ Now suppose another value, y is added to the sorted array to obtain a new sorted array A$0$ and that y lies between at and at$+1$ in the original array A$.$ For simplicity, we assume that $2$ t $$ n $1.$ That is$,$ A $0=[$a$1,$ a$2,...,$ at$,$ y$,$ at$+1,...,$ an$]=[$a $01,$ a$02,...,$ a$0$ t $,$ a$0$ t$+1=$ y$,$ a$0$ t$+2=$ at$+1,...,$ a$0$ n$+1=$ an$]$ Suppose further that we have values P $0$ i and Q$0$ i such that P $0$ t$+1=$ x$,$ and Q$0$ t$+1=$ z$1$ and Q$0$ t$+2=$ z$2.$ Answer the following:

$($a$)$ Provide expressions for all the P $0$ i and Q$0$ i not given above, in terms of the ones given above and the Pi and Qi $.$

$($b$)$ Describe a dynamic programming approach to compute the optimal binary search tree for A$0,$ P$0,$ Q$0.$ Your approach should make maximum use of all the values already computed to find the optimal binary search tree for A$,$ P$,$ Q$.$

$($c$)$ Under what circumstances will we have the situation where the newly inserted node, y$,$ is the root of the optimal binary search tree?