Design and Analysis of Algorithms MCQs | Page - 37

 recursive solution of subset sum problem is slower than dynamic problem solution in terms of time complexity.

 power set of a set is defined as the set of all subsets. ex- if there is a set s=

 in set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. if such subsets are present then we print true otherwise false.

 set partition problem has both recursive as well as dynamic programming solution. the recursive solution has an exponential time complexity as it will require to check for all subsets in the worst case.

 set partition problem has both recursive as well as dynamic programming solution. the dynamic programming solution has a time complexity of o(n*sum) as it as a nested loop with limits from 1 to n and 1 to sum respectively.

 the recursive solution to set partition problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. so dynamic programming solution is faster in terms of time complexity.

 the auxiliary space complexity of set partition problem is required in order to store the partition table. it takes up a space of n*sum, so its auxiliary space requirement becomes o(n*sum).

 longest palindromic subsequence is an example of 2d dynamic programming.

 both dynamic programming and recursion can be used to solve 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.