A car factory has k assembly lines, each with n stations. A station is denoted by Si$,$j where i

indicates that the station is on the i$-$th assembly line $(0$ s$2,2->$ s$1,3->$ s$2,4->$ s$2,5,$ the time cost will be :

e$1+$ a$1,1+$ t$1,2+$ a$2,2+$ t$2,1+$a$1,3+$t$1,2+$a$2,4+$a$2,5+$x$2$

a$)$ Define $($in plain English$)$ subproblems to be solved. $(2$ pts$)$

b$)$ Recursively define the value of an optimal solution $($recurrence formula$)(8$ pts$)$

c$)$ Describe $($using pseudocode$)$ how the value of an optimal solution is obtained

using iteration. Make sure you include any initialization required. $(8$ pts$)$

d$)$ What is the complexity of your solution in part b$?(4$ pts$)$