$(30$ pts$)$ Dynamic programming implementations.

$($a$)$ Find an optimal parenthesization of a matrix$-$chain product whose sequence of dimensions is $($:$3,5,7,9,11$:$).$

$($b$)$ Determine an LCS of $($:$C,A,B,A,C,B,D$:$)$ and $($:$A,D,B,A,C,D$:$).$

$($c$)$ Determine the cost and structure of an optimal binary search tree for a set of $n=6$ keys with the following probabilities: $p_i=0\mathrm{.}05,0\mathrm{.}09,0\mathrm{.}10,0\mathrm{.}05,0\mathrm{.}12,0\mathrm{.}15,i=1,$dots,$6,$ respectively, and $q_i=0\mathrm{.}03,0\mathrm{.}06,0\mathrm{.}07,0\mathrm{.}11,0\mathrm{.}08,0\mathrm{.}05,0\mathrm{.}04,i=0,$dots,$6,$ respectively.