Question $1$

$4$ pts

Suppose you have solved a dynamic programming algorithm and

come up with the following two variable recurrence:

OPT OPT$($i$-1,$ j$-1),$ OPT$($i$-1,$ j$)\}$

for $i=0,1,$dots,$n$ and $j=0,1,$dots,$m,$ with base cases OPT$(0,j)=0$ and

OPT$(i,0)=0.$ In this recurrence, A is some array representing the

input to the problem. In all of the code snippets, A will be a

global variable.

Each of the following pseudocode snippets represents an attempt

at a polynomial time algorithm for efficiently and correctly

computing the value OPT $(n,m).$ For each pseudocode snippet,

answer "true" if it correctly computes OPT$(i,j)$ in polynomial time

and "false" if it fails to do so$.$Let OPT $(\}1,0)=0\backslash$mathrm$\{$ and OPT $($e$,$j$)=0$ for al$1$ i$,$j For $1=1,2,,$ n$,$ n:Return OPT$($n$,$n$)$

$\backslash$

FindOPT$\_$b$($n$,$m$)=$ElseIf $($m $=0)$: Return e Return max$\{$ A$($n$)+$ FindOPT$\_$b$($n$-1,$n$-1),$ FindOPT$\_$b$($n$-1,$n$)\}$

FindOPT$\_$c$()$:For $\}1=1,2,\backslash$ldots$,$n$\backslash$mathrm$\{$ : Let OPT$((1,$j$)=\backslash$operatorname$\{$max$\}\{$A$($i$)+\backslash$operatorname$\{$OPT$\}(1-1,$j$-1),\backslash$operatorname$\{$OPT$\}($i$-1,$j$)\}$FindOPT$\_$d$()$:For $\}\backslash$textrm$\{$j$\}=1,2,\backslash$ldots$,\backslash$textrm$\{$n$\}\backslash$mathrm$\{$ : Let OPT$($i$,$j$)=\backslash$operatorname$\{$max$\}\{$A$($i$)+\backslash$operatorname$\{$OPT$\}($i$-1,$j$-1),\backslash$operatorname$\{$OPT$\}($i$-1,$j$)\}$