Divide and Conquer MCQ Quiz - Objective Question with Answer for Divide and Conquer - Download Free PDF

The correct answer is Heap Sort.

Key Points

• Divide and Conquer is a fundamental algorithmic technique where a problem is broken down into smaller sub-problems, each of which is solved independently, and then the solutions to the sub-problems are combined to form the solution to the original problem.
• Binary Search, Merge Sort, and Quick Sort are all classic examples of divide and conquer algorithms:
  • Binary Search: This algorithm works by dividing the search interval in half repeatedly until the target value is found or the interval is empty.
  • Merge Sort: This sorting algorithm divides the array into two halves, recursively sorts each half, and then merges the sorted halves to produce the final sorted array.
  • Quick Sort: This sorting algorithm selects a 'pivot' element and partitions the array into two sub-arrays according to whether elements are less than or greater than the pivot, then recursively sorts the sub-arrays.
• Heap Sort, however, is not a divide and conquer algorithm. It is an efficient, comparison-based sorting algorithm that builds a heap data structure from the input data and then repeatedly extracts the maximum element from the heap to build the sorted array.

Additional Information

• While Heap Sort is not a divide and conquer algorithm, it is still an efficient sorting algorithm with a time complexity of O(n log n) for both the average and worst cases.
• Divide and conquer algorithms are widely used due to their ability to break complex problems into simpler sub-problems, making them easier to manage and solve.
• Understanding the different types of algorithms and their characteristics is essential for choosing the right approach for a given problem.

The correct answer is None of the above.

Key Points

• The Divide and Conquer algorithm consists of three main steps:
  • Divide: Break the problem into smaller subproblems that are similar to the original problem but smaller in size.
  • Conquer: Solve the subproblems recursively. If the subproblems are small enough, solve them directly.
  • Combine: Combine the solutions of the subproblems to form the solution of the original problem.
• Each of the provided options (Combine, Conquer, and Divide) are indeed steps in the Divide and Conquer algorithm.

Additional Information

• The Divide and Conquer strategy is widely used in algorithms such as Merge Sort, Quick Sort, and Binary Search.
• It is a powerful tool for solving complex problems by breaking them down into simpler subproblems.
• This approach helps in reducing the time complexity for many computational problems.
• Using Divide and Conquer can lead to more efficient algorithms in terms of both time and space complexity.

• Quick Sort algorithm is based on divide and conquer approach in which a pivot is element is selected and array is partitioned based on that pivot element.
• Kruskal algorithm is a minimum spanning tree algorithm in which in every iteration, minimum weighted edge is found and then it is added to the construction of minimum spanning tree. Edges are added in increasing order of the edge weights. That’s why it is a greedy approach.
• Floyd Warshall algorithm is based on the principle of dynamic programming. It is used to solve the all pair shortest path problem.

• Quick Sort algorithm is based on divide and conquer approach in which a pivot is element is selected and array is partitioned based on that pivot element.
• Kruskal algorithm is a minimum spanning tree algorithm in which in every iteration, minimum weighted edge is found and then it is added to the construction of minimum spanning tree. Edges are added in increasing order of the edge weights. That’s why it is a greedy approach.
• Floyd Warshall algorithm is based on the principle of dynamic programming. It is used to solve the all pair shortest path problem.

The correct answer is option 2.

Concept:

QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

• Always pick the first element as a pivot.
• Always pick the last element as the pivot.
• Pick a random element as a pivot.
• Pick median as the pivot.

Here given, Assume that there is a divide and conquer quick sort algorithm and in the partition algorithm, the first element of the lists is taken as pivot-element.

Option 1: 40, 50, 10, 20, 30

False, Here the pivot element is 40. After running quick sort the sequence will be like 20, 50, 10, 40, 30. So the given sequence of the numbers X2,5 = 1 is not correct.

Option 2: 10, 20, 50, 30, 40

True, Here the pivot element is 10. After running quick sort the sequence will be like 10, 20, 50, 30, 40. So the given sequence of the numbers X2,5 = 1 is the correct sequence.

After the pivot is 20, it divides the sequence like 10, 20, 50, 30, 40. And X3,5 = 1

After the pivot is 50, it divides the sequence like 10, 20, 40, 30, 50.  And X4,5 = 1. So on.

Option 3: 40, 20, 10, 30, 50

False, Here the pivot element is 40. After running quick sort the sequence will be like 30, 20, 10, 40, 50. So the given sequence of the numbers X2,5 = 1 is not correct.

Option 4: 30, 20, 10, 40, 50

False, Here the pivot element is 30. After running quick sort the sequence will be like 10, 20, 30, 40, 50. So the given sequence of the numbers X2,5 = 1 is not correct.

Hence the correct answer is 10, 20, 50, 30, 40.

Additional InformationQuicksort:

The worst-case time complexity quicksort algorithm is O(n2) if the array is sorted.
T(n) = T(n-1) + cn

That's why randomized quick sort come to make time complexity O(N log N)
Randomized quicksort:
Randomized quicksort says instead of picking the pivot to be the first element what if pick my pivot to be a random element from my array A[p...r].

• A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
• This means a sorting algorithm is called stable if two identical elements do not change the order during the process of sorting.
• Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. and some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Explanation:

Code:

#include
int main() {
int ary[10] = {250,1,9,7,3,4,5,21,15,19};
/if we take any 3 elemement from n distinct element in an array one of them would be neither maximum nor minimum.
int a = ary[0];
int b = ary[1];
int c = ary[2];
if((b > a && a >c) || (c > a && a > b)) 
printf("%d",a);
else if((a > b && b >c) || (c > b && b >a)) 
printf("%d",b);
else 
printf("%d",c);
}

Output: 9

9 is neither maximum nor minimum

Explanation:

Neither recursion nor iteration takes place in the above code, every statement in the above program takes a constant amount of time 

and hence order is θ (1)

Note All elements are distinct, select any three numbers and output 2^nd largest from them. If in the same question 'distinct' keyword is not given, we will have to get 3 distinct elements and this would take O(n) time in the worst case. From these 3 distinct elements the middle element is neither minimum nor maximum. In this case it is O(n). We hope clear your doubt.

The correct answer is option 2.

Concept:

QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

• Always pick the first element as a pivot.
• Always pick the last element as the pivot.
• Pick a random element as a pivot.
• Pick median as the pivot.

Here given, Assume that there is a divide and conquer quick sort algorithm and in the partition algorithm, the first element of the lists is taken as pivot-element.

Option 1: 40, 50, 10, 20, 30

False, Here the pivot element is 40. After running quick sort the sequence will be like 20, 50, 10, 40, 30. So the given sequence of the numbers X2,5 = 1 is not correct.

Option 2: 10, 20, 50, 30, 40

True, Here the pivot element is 10. After running quick sort the sequence will be like 10, 20, 50, 30, 40. So the given sequence of the numbers X2,5 = 1 is the correct sequence.

After the pivot is 20, it divides the sequence like 10, 20, 50, 30, 40. And X3,5 = 1

After the pivot is 50, it divides the sequence like 10, 20, 40, 30, 50.  And X4,5 = 1. So on.

Option 3: 40, 20, 10, 30, 50

False, Here the pivot element is 40. After running quick sort the sequence will be like 30, 20, 10, 40, 50. So the given sequence of the numbers X2,5 = 1 is not correct.

Option 4: 30, 20, 10, 40, 50

False, Here the pivot element is 30. After running quick sort the sequence will be like 10, 20, 30, 40, 50. So the given sequence of the numbers X2,5 = 1 is not correct.

Hence the correct answer is 10, 20, 50, 30, 40.

Additional InformationQuicksort:

The worst-case time complexity quicksort algorithm is O(n2) if the array is sorted.
T(n) = T(n-1) + cn

That's why randomized quick sort come to make time complexity O(N log N)
Randomized quicksort:
Randomized quicksort says instead of picking the pivot to be the first element what if pick my pivot to be a random element from my array A[p...r].

• Quick Sort algorithm is based on divide and conquer approach in which a pivot is element is selected and array is partitioned based on that pivot element.
• Kruskal algorithm is a minimum spanning tree algorithm in which in every iteration, minimum weighted edge is found and then it is added to the construction of minimum spanning tree. Edges are added in increasing order of the edge weights. That’s why it is a greedy approach.
• Floyd Warshall algorithm is based on the principle of dynamic programming. It is used to solve the all pair shortest path problem.

Largest Sum Contiguous subarray is from index 2 to 11

Maximum subsequence sum = S(2, 11) = 6, 3, -1, -2, 13, 4, -9, -1, 4, 12 = 29

Code in C++ to find the maximum contiguous sum of array

#include

using namespace std;

int kadane(int arr[], int n)

{

int max_so_far = 0;

int max_ending = 0;

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

{

max_ending = max_ending + arr[i];

max_ending = max(max_ending, 0);

max_so_far = max(max_so_far, max_ending);

}

return max_so_far;

}

int main()

{

int arr[] = { −5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0};

int n = sizeof(arr)/sizeof(arr[0]);

cout << "largest sum of contiguous sub-array is " << kadane(arr, n);

return 0;

}

Concept: 

• Strassen’s matrix multiplication uses the divide and conquers approach. Divide both the matrices in 4 sub-matrices of size N/2 × N/2.
• Perform 8 multiplications for matrices of size N/2 × N/2 and 4 additions. The addition of two matrices takes O(N2) time.

Hence recurrence relation is T(N) = 8T(N/2) + O(N2)

Calculation:

Data:

n = 100

Formula:

minimum number of comparisons = \(\frac{{3n}}{2} - 2\)

Calculation:

minimum number of comparisons = \(\frac{{3\; \times \;100}}{2} - 2 = 148\)

Important Points:

Divide and conquer is used to achieve minimum comparison

Tournament Method Technique

1. To find the smallest element in the array will take n−1 comparisons = 100 – 1 = 99.

2. To find the largest element -

After the first round of Tournament, there will be exactly n/2 numbers = 50 that will lose the round.

So, the biggest looser (the largest number) should be among these 50 looser.

To find the largest number will take \(\frac{n}{2} - 1\) comparisons = 49.

Total 99 + 49 = 148.

Concept:

Strassen’s matrix multiplication:

• It is a method used for matrix multiplication. It uses the Divide and Conquer approach to multiply the matrices.
• Time consumption is improved by using Strassen’s method as compared to the standard multiplication method.
• It is faster than the standard method. Strassen’s multiplication can be performed only on square matrices.

Insertion sort

Insertion sort is sorting algorithm which decreases the problem by 1. It uses the Decrease and Conque approach 

Gaussian elimination

It uses Transform and Conquer approach to solve a set of equations. 

Floyd Warshall 

Its algorithm is based on the principle of dynamic programming. It is used to solve the all pair shortest path problem.

Conclusion

Strassen matrix multiplication  → Divide and Conquer

Insertion sort  → Decrease and Conquer

Gaussian Elimination  →  Transform and Conquer

Floyd shortest path algorithm → Dynamic Programming

The correct answer is Heap Sort.

Key Points

• Divide and Conquer is a fundamental algorithmic technique where a problem is broken down into smaller sub-problems, each of which is solved independently, and then the solutions to the sub-problems are combined to form the solution to the original problem.
• Binary Search, Merge Sort, and Quick Sort are all classic examples of divide and conquer algorithms:
  • Binary Search: This algorithm works by dividing the search interval in half repeatedly until the target value is found or the interval is empty.
  • Merge Sort: This sorting algorithm divides the array into two halves, recursively sorts each half, and then merges the sorted halves to produce the final sorted array.
  • Quick Sort: This sorting algorithm selects a 'pivot' element and partitions the array into two sub-arrays according to whether elements are less than or greater than the pivot, then recursively sorts the sub-arrays.
• Heap Sort, however, is not a divide and conquer algorithm. It is an efficient, comparison-based sorting algorithm that builds a heap data structure from the input data and then repeatedly extracts the maximum element from the heap to build the sorted array.

Additional Information

• While Heap Sort is not a divide and conquer algorithm, it is still an efficient sorting algorithm with a time complexity of O(n log n) for both the average and worst cases.
• Divide and conquer algorithms are widely used due to their ability to break complex problems into simpler sub-problems, making them easier to manage and solve.
• Understanding the different types of algorithms and their characteristics is essential for choosing the right approach for a given problem.

Concept:

Quick Sort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array.

Important Points:

• Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
• Both Merge Sort and quicksort are based on the divide and conquer method.