Dynamic Programming

Algorithm B1:  For i = 1, 2, ..., n
                 For j = 1, 2, ..., n
                   T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Algorithm B2:  For s = 2, 3, ..., 2n
                 For i = 1, 2, ..., n
                   For j = 1, 2, ..., n
                     If (i + j == s)
                       T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Single correct

• ABoth algorithms $B_1$ and $B_2$ are correct
• BAlgorithm $B_1$ is correct, but algorithm $B_2$ is incorrect
• CAlgorithm $B_2$ is correct, but algorithm $B_1$ is incorrect
• DBoth algorithms $B_1$ and $B_2$ are incorrect

Numerical answer

One or more correct

• A$R_7 = 18$
• B$R_7 = 19$
• C$R_7$ is achieved by three different solutions.
• D$R_7$ cannot be achieved by a solution consisting of three pieces.

Answer key coming soon

Single correct

• A$F_1F_2$ and $F_3F_4$ only
• B$F_2F_3$ only
• C$F_3F_4$ only
• D$F_1F_2$ and $F_4F_5$ only

Numerical answer

Single correct

• AGreedy paradigm.
• BDivide-and-Conquer paradigm.
• CDynamic Programming paradigm.
• Dneither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Answer key coming soon

Numerical answer

Answer key coming soon

int MyX(int *E, unsigned int size)
{
    int Y = 0;
    int Z;
    int i, j, k;

    for(i = 0; i < size; i++)
        Y = Y + E[i];

    for(i = 0; i < size; i++)
        for(j = i; j < size; j++)
        {
            Z = 0;
            for(k = i; k <= j; k++)
                Z = Z + E[k];
            if (Z > Y)
                Y = Z;
        }
    return Y;
}

Single correct

• Amaximum possible sum of elements in any sub-array of array E.
• Bmaximum element in any sub-array of array E.
• Csum of the maximum elements in all possible sub-arrays of array E.
• Dthe sum of all the elements in the array E.

Numerical answer

Numerical answer

Single correct

• AThe algorithm uses dynamic programming paradigm
• BThe algorithm has a linear complexity and uses branch and bound paradigm
• CThe algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
• DThe algorithm uses divide and conquer paradigm.

Answer key coming soon

Single correct

• A248000
• B44000
• C19000
• D25000

Answer key coming soon