a. For the recursion program given below function, func(), gets an integer array, arr[], of size n along with some number, num.

bool func(int arr[], int n, int num)

{

if (num == 0)

return true;

if (n == 0)

return false;

if (arr[n - 1]

bool b1 = func(arr, n - 1, num)

|| func(arr, n - 1, num - arr[n - 1]);

Return b1;

}

else

return func(arr, n - 1, num);

}

The above had a exponential time complexity issue! so decrease the complexity to pseudo-polynomial, you may apply a dynamic programming approach in the program given below. Do not change the codes only fill in as "//// Part (1)" and "//// Part (2)."to achieve the objective.

bool func(int arr[], int n, int num)

{

bool DP[n + 1][num + 1];

for (int i = 0; i

DP[i][0] = true;

for (int i = 1; i

DP[0][i] = false;

for (int i = 1; i

for (int j = 1; j

if (j

//// Part (1)

if (j >= arr[i - 1])

//// Part (2)

}

}

return DP[n][num];

}

2. Apply Prim's Algorithm to identify the minimum spanning tree for the graph given below. The start node is node 0. Select the edges chosen by the algorithm in Blackboard submission page. Each edge is denoted by an alphabet letter from (a) through (n).

\f4 (d) 4 1 (k) 11 (a)/2 (e) 14 (g) 10 Start 2 5 0 (b) 6 (h) 1 (i) 13 (m) 7 (c) 3 (f) 12 (11 5 3 7 (1) 8 6 (n1 9\f