Following the idea in 2.1.3 of L06, write an algorithm to solve the segmented least square problem using dynamic programming. The output of your algorithm should be a record consisting two fields: one is the partition and the other is the penalty of the partition. Your algorithm format should follow the ones in lecture notes. 2.1.3 Design an algorithm following the DP methodology o Problem decomposition from an optimal solution Given a set P of points P1: (21,41), , Pr : (nyn), consider an optimal solution {S,..., Sk} • Decomposition: Sk and the rest {S1,.,Sk-1} We do not know Sk! But Sk can be only one of the following cases: case 1: Sk = {pn}. Decomposition:{S..., Sk-1} is an optimal solution of points P1.**.Pn-1 case 2: Sk = {Pn-1, Pn} case n: Sk = {P1 ...,Pn-1, Pn} Let opt(n) be the penalty of a minimal partition of P, i. e. input of opt function is n and output of opt is the penalty of minimal partition of P. case 1: opt(n) = opt(n-1) + C + error(Pn) o case 2: ?? case n: ??... Hence, opt(n) is a minimal value of the cases above: opt(n) = minisisn lopt(i - 1) + C + error({Pi, Pi+2, ..., Pn})) Now you can write the algorithm (using problem decomposition) for the idea above Iterative design: • M[O]: 0 -- accumulation of penalty starts from o • M[1] = min_{1<=i<=1}(opt(i-1) + C + error({p_İ, ...,P_1}) o M[n] = min_{1<=i<=n}(M[i-1] + C + error({p_İ, ..., P_n}) Algorithm 1: Input output side effect: plan end