This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Set Partition Problem”.
1. What is meant by the power set of a set?
a) subset of all sets
b) set of all subsets
c) set of particular subsets
d) an empty set
View Answer
Explanation: Power set of a set is defined as the set of all subsets. Ex- if there is a set S={1,3} then power set of set S will be P={{},{1},{3}{1,3}}.
2. What is the set partition problem?
a) finding a subset of a set that has sum of elements equal to a given number
b) checking for the presence of a subset that has sum of elements equal to a given number
c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result
d) finding subsets with equal sum of elements
View Answer
Explanation: 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.
3. Which of the following is true about the time complexity of the recursive solution of set partition problem?
a) It has an exponential time complexity
b) It has a linear time complexity
c) It has a logarithmic time complexity
d) it has a time complexity of O(n2)
View Answer
Explanation: 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.
4. What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a) O(n)
b) O(sum)
c) O(n2)
d) O(sum*n)
View Answer
Explanation: 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.
5. Set partition problem is an example of NP complete problem.
a) true
b) false
View Answer
Explanation: Set partition problem takes exponential time when we implement a recursive solution. Set partition problem is known to be a part of NP complete problems.
6. Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.
a) true
b) false
View Answer
Explanation: 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.
7. Which of the following is not true about set partition problem?
a) the recursive solution has a time complexity of O(2n)
b) there is no known solution that takes polynomial time
c) the recursive solution is slower than dynamic programming solution
d) the dynamic programming solution has a time complexity of O(n log n)
View Answer
Explanation: Recursive solution of set partition problem is slower than dynamic problem solution in terms of time complexity. Dynamic programming solution has a time complexity of O(n*sum).
8. Which of the following should be the base case for the recursive solution of a set partition problem?
a)
If(sum%2!=0) return false; if(sum==0) return true;
b)
If(sum%2!=0) return false; if(sum==0) return true; if (n ==0 && sum!= 0) return false;
c)
if (n ==0 && sum!= 0)
return false;
d)
if(sum<0) return true; if (n ==0 && sum!= 0) return false;View Answer
Explanation: In this case, we need to make sure that, the sum does not become 0 and there should be elements left in our array for recursion to happen. Also if the sum of elements of the set is an odd number then that set cannot be partitioned into two subsets with an equal sum so under such a condition false should be returned.
9. What will be the output for the given code?
#include <stdio.h> #include <stdbool.h> bool func1(int arr[], int n, int sum) { if (sum == 0) return true; if (n == 0 && sum != 0) return false; if (arr[n-1] > sum) return func1(arr, n-1, sum); return func1(arr, n-1, sum) || func1(arr, n-1, sum-arr[n-1]); } bool func (int arr[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; if (sum%2 != 0) return false; return func1 (arr, n, sum/2); } int main() { int arr[] = {4,6, 12, 2}; int n = sizeof(arr)/sizeof(arr[0]); if (func(arr, n) == true) printf("true"); else printf("false"); return 0; }
a) true
b) false
c) 4 6 2
d) 12
View Answer
Explanation: The given code represents the recursive approach of solving the set partition problem. The code checks whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such a partition is possible then we print true otherwise false. In this case true should be printed.
10. What will be the output for the given code?
#include <stdio.h> bool func (int arr[], int n) { int sum = 0; int i, j; for (i = 0; i < n; i++) sum += arr[i]; if (sum%2 != 0) return false; bool partition[sum/2+1][n+1]; for (i = 0; i <= n; i++) partition[0][i] = true; for (i = 1; i <= sum/2; i++) partition[i][0] = false; for (i = 1; i <= sum/2; i++) { for (j = 1; j <= n; j++) { partition[i][j] = partition[i][j-1]; if (i >= arr[j-1]) partition[i][j] = partition[i][j] || partition[i - arr[j-1]][j-1]; } } return partition[sum/2][n]; } int main() { int arr[] = {3, 3, 4, 4, 7}; int n = sizeof(arr)/sizeof(arr[0]); if (func(arr, n) == true) printf("true"); else printf("false"); return 0; }
a) true
b) false
c) 0
d) error
View Answer
Explanation: The given code represents the dynamic programming approach of solving set partition problem. The code checks whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such a partition is possible then we print true otherwise false. In this case, false should be printed.
11. What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a) O(n log n)
b) O(n2)
c) O(2n)
d) O(sum*n)
View Answer
Explanation: 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).
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Check Design and Analysis of Algorithms Books
- Practice Data Structure MCQ
- Apply for Computer Science Internship
- Check Programming Books
