Data Structure And Algorithm : Practice Questions and Answers

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.

Memoization is the technique in which previously calculated values are stored, so that, these values can be used to solve other subproblems.

A greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may NOT result into a globally optimal solution. Hence, a greedy algorithm CANNOT be used to solve all the dynamic programming problems.

Dynamic programming calculates the value of a subproblem only once, while other methods that don't take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. So, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don't take advantage of the overlapping subproblems property.

In divide and conquer, the problem is divided into smaller non-overlapping subproblems and an optimal solution for each of the subproblems is found. The optimal solutions are then combined to get a global optimal solution. For example, mergesort uses divide and conquer strategy.

Overlapping subproblems is the property in which value of a subproblem is used several times.