We want to paint our new fence, which is made up $N$ boards. The lengths of the $N$ boards are given in array $L=(L[1],L[2],...,L[N]).$ We have hired $K$ painters, where each painter takes $1$ hour to paint $1$ unit of board. For example, if one of the painters paints boards $3,4$ and $5,$ then

she completes at time $t_i=L[3]+L[4]+L[5].$ Our goal is to assign each painter to some subset of boards, to minimize the time when the fence has been completely painted. Since the $K$ painters can work in parallel, this corresponds to minimizing max$(t_1,...,t_K),$ where $t_i$ is the time taken

by painter $i$ to complete her job. The painting task must be accomplished under the following constraints:

$1.$ Each board must be completely painted by exactly one painter; i$.$e$.,$ no board can be painted partially by one painter and partially by another.

$2.$ Each painter paints a contiguous collection of boards. For example, a configuration where painter $1$ paints boards $1$ and $3$ but not $2$ is not a valid solution.

You are given as input the following: the number of painters $K,$ and an array $L$ with the board lengths. In the following problems, denote by $T[i,j]$ the minimum time to paint the first i boards using $j$ painters. We will, successively in the following subtasks, come up with a procedure to

minimize the painting time.

$($a$)$ Write a recurrence for $T[i,j]$ in terms of $T[*,j-1].$ Do not forget base cases!

$($b$)$ Write an algorithm MinTime that computes the minimal completion time. To this end, complete the following skeleton. Make sure your algorithm uses only the minimal

amount of extra storage.

MinT ime$(N,K)$

$T=$ arr new array of length $........$

$T[...]={?}_{(}{?}_{{?}_{?}}{?}_{{?}_{?}}{?}_{{?}_{?}}{?}_{?}$

for ${?}_{?}{?}_{{?}_{?}}{?}_{{?}_{?}})=1$ to $.....$ do

$T[.....]=\_\_\_\_\_\_\_\_\_$

for $\_\_\_=1$ to $........$ do

for $.....=....$ down to $1$ do

$T[.....]=$ CALC$(T,L,N,K,i,j)$

return

Next, write an algorithm CALC$(T,L,N,K,i,j)$ that calculates $T[i,j]$ according to your recursive formula from part $($a$).$ Let $C$ denote the maximum time needed for CALC. You will obtain:

$1.2$ points for correctly completing the solution

$2.2$ points if your algorithm satisfies C $=$ O$($n$^2)$

$3.$ an additional $2$ points if C $=$ O$($N$)$

c$)$ When filling the table T$[$i$,$j$]$ in the previous part, does it matter wheterh the outer loop iterates over i $($and the inner of j$)$ or vice$-$versa for correctness? What about the storage requirement? How much of the table do we need to keep stored in each order?