Let a$1,...,$ an be a sequence of positive integers. A labeled tree for this sequence is a binary tree

T of n leaves named v$1,...,$ vn$,$ from left to right. We label vi by ai

$,$ for all i$,1<=$ i $<=$ n$.$ Let

Di be the length of the path from vi to the root of T$.$ The cost of T is given by

cost$($T$)=$ Xn

i$=1$

aiDi

$.$

The problem is: Given a sequence of n positive integers a$1,...,$ an$,$ construct a labeled tree

for this sequence that has the lowest cost. Your algorithm should run in O$($n

$3$

$)$ time. $($Hint:

Use Dynamic Programming.$)$

Your answer should include: $($i$)$ The main ideas $($in words$)$ behind the algorithm which makes

the correctness self$-$evident, $($ii$)$ pseudocode, and $($iii$)$ an analysis of the running time and

space