Data Structure And Algorithm : Practice Questions and Answers

All of the above mentioned methods can be used to solve the assembly line scheduling problem.

find_max(ans[itm - 1][w - wt[itm - 1]] + val[itm - 1], ans[itm - 1][w]) completes the above code.

The Knapsack problem cannot be solved using the greedy algorithm.

In the brute force algorithm all the subsets of the items are found and the value of each subset is calculated. The subset of items with the maximum value and a weight less than equal to the maximum allowed weight gives the answer. The time taken to calculate all the subsets is O(2^{n}).

In this case, questions are used instead of items. Each question has a score which is same as each item having a value. Also, each question takes a time t which is same as each item having a weight w. You have to maximize the score in time T which is same as maximizing the value using a bag of weight W.

The maximum value you can get is 160. This can be achieved by choosing the items 1 and 3 that have a total weight of 60.

Brute force, Recursion and Dynamic Programming can be used to solve the knapsack problem.

Knapsack problem is an example of 2D dynamic programming.

The line "mx_sm = val" should be inserted to complete the above code.

The dynamic programming implementation of the maximum sum rectangle problem uses Kadane's algorithm.

The time complexity of the brute force implementation of the maximum sum rectangle problem is O(n^{4}).

The complete matrix represents the maximum sum rectangle and it's sum is 14.

Since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. The sum of elements of the maximum sum rectangle is -1.

Since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12.

If a matrix contains all non-zero elements with at least one positive and at least on negative element, then the sum of elements of the maximum sum rectangle cannot be zero.

If the matrix size is 1×1 then the element itself is the maximum sum of that 1×1 matrix. If all elements are zero, then the sum of any submatrix of the given matrix is zero. If all elements are negative, then the maximum element in that matrix is the highest sum in that matrix which is again 1X1 submatrix of the given matrix. Hence all three statements are correct.

When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.

Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.

The space complexities are as follows:

Dynamic programming: O(n)

Recursion: O(1)

Binomial coefficients: O(1).

The time complexities are as follows:

Dynamic programming: O(n^{2})

Recursion: Exponential

Binomial coefficients: O(n).