Dynamic Programming MCQ Quiz in தமிழ் - Objective Question with Answer for Dynamic Programming - இலவச PDF ஐப் பதிவிறக்கவும்

The correct answer is 2.

Key PointsDynamic approach: This approach is more calculated based on the previous situation and upcoming needs.

Greedy approach: This approach is based on the immediate benefit, the choice based on the current moment requirement.  

Using Dynamic programming:

1. 20 rupee coin = 3 = 60 Rs
2. 10 rupee coin = 1 = 10 Rs
3. 4 rupee coin = 2 = 8 Rs

Total coin = 3 + 1 + 2 = 6

Using greedy approach

1. 20 rupee coin = 3 = 60 Rs
2. 10 rupee coin = 1 = 10 Rs
3. 5 rupee coin = 1 = 5 Rs
4. 1 rupee coin = 3 = 3 Rs

Total coins = 8

|8 - 6| = 2

In the dynamic approach after the 2nd step, the requirement is for 8rs which can be fulfilled with 5+1+1+1, or by 4+4, or by 1+1+1....+1 (Eight 1 coins).

The dynamic approach uses the balanced approach to reduce the number of coins, so it chose the 4+4 two coins, as a result only two coins fulfill the requirement.

But, in the greedy approach, the main approach is to cover the maximum space with one coin. So it chose 5 as it covers max from 8. But now after that 3 remain which can not be filled with one 4 coins, but it can be filled with three 1 coin. This result that there are 4 coins consumed to fill the 8rs space in the greedy approach which is two more coins than in the dynamic approach.

The greedy approach only focused on fulfilling the current requirement as a result it chose 5, but the dynamic approach considers the further need. 

Concept:

Order of M₁ = w × x

Order of M₂ = x × y

Order of M₃ = y × z

For cost of (M₁M₂)M₃ = wxy + wyz. Detailed steps below.

• Cost of M₁M₂ = w × x × y
• This gives us a new matrix. Let the new matrix be M.
• Order of M is w × y
• Cost of MM₃ = w × y × z
• Total cost = M₁M₂ cost + MM₃ cost

Similarly, cost of M₁ (M₂M₃) = xyz + wxz

For (M₁M₂)M₃ to take less time than M₁(M₂M₃)

(wxy + wyz) < (xyz + wxz)

Dividing both the sides of above equation, we get

(1/x + 1/z) < (1/w + 1/y)

Concept –

The “8 queens” puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share,

• The same row
• The same column
• The same diagonal

For achieving this, Backtracking algorithm is most commonly used.

The algorithm goes like this:

1. Start in the leftmost column

2. If all queens are placed

    Return true

3. Try all rows in the current column.

     Do following for every tried row.

a) If the queen can be placed safely in this row, then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.

b) If placing the queen in [row, column] leads to a solution then return true.

c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows.

4. If all rows have been tried and nothing worked,

Return false to trigger backtracking.

The 8-queens puzzle is an example of the more general “n queens” problem of placing n non-attacking queens on an n×n chessboard.

Some Additional points –

• N-Queen problem using branch and bound.
• Solution for N-Queen problem does not exist for n=2 and n=3.

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. It's greedy because it always mark the closest vertex

Traveling Salesman Problem can be solved either using Dynamic Programming or approximation algorithm.

N Queen problem uses Backtracking to obtain the valid position

Concept:

If there is match, A[i, j] = A[i – 1, j  – 1] + 1

If not match: max(A[i – 1, j], A[i, j – 1])

CALCULATION

Let M =  length of X and N = length of Y

int dp[N+1][M+1]

Table of longest common subsequence:

The length of longest common subsequence of X and Y = A[N][M] = 4

Dynamic programming approach:

The dynamic programming approach considers the previous steps solution, saves them, and then uses them in the future so as to avoid solving the same problem again and again. It uses the bottom up approach. Steps that are take in dynamic programming approach are:

1) Characterize the structure of an optimal solution

2) Using the previous solved values

3) Construct the optimal solution for final result.

Important Point:

Top down approach can also be used and hence marks is given both 1 and 2

(a) The running time of dynamic programming algorithm is alway θ (ρ) where ρ is number of subproblems.

This statement is incorrect. Running time for dynamic algorithm is the number of subproblems multiplies with time for each subproblem. It means running time of dynamic programming algorithm is O(1).

(b) When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program.

Cyclic dependency is relation between two or more modules which depends on each other indirectly or directly, these are mutually recursive. So, given statement is correct.

(c) For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memorization.

This statement is incorrect. For a dynamic programming algorithm, computing all values using recursion and memorization takes less time than computing in bottom- up fashion.

(d) If a problem X can be reduced to a known NP-hard problem, then X must be NP-hard.

If a problem X can be reduced to a known NP hard problem, then X must be NP complete not NP hard. SO, given statement is incorrect.

A binomial coefficient ⁿC_k gives us the number of ways that k objects can be chose among n objects. WE have to find k element subset from n element set.

To calculate the value of binomial coefficient we call it recursively as :

ⁿC_k = ^n-1C_k-1 + ^n-1C_k for n> k> 0

ⁿC₀ = ⁿC_n = 1            (Base case)

It is computed by constructing a table.

Cost of the algorithm is the cost of filling the table.  Because k< = n, this sum is to be splitted into two parts.

T(n,k) = sum for upper triangle + sum for lower triangle

\(= \mathop \sum \limits_{i = 1}^k \mathop \sum \limits_{j = 1}^k 1 + \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 1}^k 1\)

\(= \mathop \sum \limits_{i = 1}^k \left( {i - 1} \right) + \mathop \sum \limits_{i = 1}^n k\)

= (k-1)k/2 + k (n-k) = nk

The fractional knapsack is based on the Greddy approach.

As the important time taking step is sorting, the time required to solve the problem is O(n log n).

Concept

Recursion tree of the given function fib(n) will contain n levels hence will contain almost O(2ⁿ) function points thus will have O(2ⁿ) time complexity, assuming each function point takes constant time.

Example: fib(5)

Avoid overlapping sub-problems to solve this problem in O(n) time. 

Use a buffer (array) to store the recently solved sub-problem and check every time we encounter a new problem.

Code using dynamic programming:

int fib[n];

fib[0] = 0; fib[0] = 1;

for(int i =2; i < n; i++)

fib[i] = fib[i-1] + fib[i-2];

Time complexity is O(n)