Dynamic Programming in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

Kadane's algorithm uses dynamic programming.

Kadane's algorithm is used to find the maximum sub-array sum for a given array.

Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.

We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.

The recursive implementation doesn't store any values and calculates every value from scratch. So, the space complexity is O(1).

From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.

The recurrence relation is given by (fibo(n) = fibo(n - 1) + fibo(n - 2)). So, the time complexity is given by:

(T(n) = T(n - 1) + T(n - 2))

Approximately,

T(n) = 2 * T(n - 1)

= 4 * T(n - 2)

= 8 * T(n - 3)

:

:

:

= 2^{k} * T(n - k)

This recurrence will stop when n - k = 0

i.e. n = k

Therefore, (T(n) = 2^{n} * O(0) = 2^{n})

Hence, it takes exponential time.

It can also be proved by drawing the recursion tree and counting the number of leaves.

Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a fibonacci sequence would be given by:

fibo(n) = fibo(n-1) + fibo(n-2).

Each of the above mentioned methods can be used to find the nth fibonacci term.

The line arr[i][j] = min completes the above code.

The empty string can be transformed into "abcd" by inserting "a", "b", "c" and "d" at appropriate positions. Thus, the edit distance is 4.

"monday" can be converted to "tuesday" by replacing "m" with "t", "o" with "u", "n" with "e" and inserting "s" at the appropriate position. So, the edit distance is 4.

Consider the strings "abcd" and "efghi". The string "efghi" can be converted to "abcd" by deleting "i" and converting "efgh" to "abcd". The cost of transformation is 5, which is equal to the length of the larger string.

The edit distance will be zero only when the two strings are equal.

All of the mentioned are the applications of the edit distance problem.

d(s,s) = 0, since each string can be transformed into itself without any change.

d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.

d(s1, s2) = d(s2, s1)

(d(s1, s3) <= d(s1, s2) + d(s2, s3))

Thus, the edit distance satisfies the axioms of a metric.

Both dynamic programming and recursion can be used to solve the edit distance problem.

The longest common subsequence problem has both, optimal substructure and overlapping subproblems. Hence, dynamic programming should be used the solve this problem.

The fractional knapsack problem is solved using a greedy algorithm.

The top-down approach uses the memoization technique which stores the previously calculated values. Due to this, the time complexity is decreased but the space complexity is increased.