Divide and Conquer MCQ Quiz in தமிழ் - Objective Question with Answer for Divide and Conquer - இலவச PDF ஐப் பதிவிறக்கவும்

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

Suppose x and y are two η –  bit integers, and it is given that η is a power of 2. The first step of multiplying ‘x’ and ‘y’ , split each of them into their left and right halves, which are η/2 bits long.

x = \({x_L}_{}\) \({x_R}_{}\)=  \({2^{\eta /2}}^{}{x_L}_{}\) + \({x_R}_{}\)

\(y = {y_L}_{}{y_R}_{} = {2^{\eta /2}}^{}{y_L}_{} + {y_R}_{}{\rm{}}\)    

For instance, if x = 01001010 (the subscript 2 means “binary”) then  \({x_L}_{} = {0100_2}_{},{\rm{}}{x_R}_{} = {1010_2}_{}\)   and \(x = {0100_2}_{} \times {2^4}^{} + {1010_2}_{}\) 

the product of x and y can be written as,

xy  = (\({2^{\eta /2}}^{}{x_L}_{}\) + \({x_R}_{}\))(\({2^{\eta /2}}^{}\) \({y_L}_{}\) + \({y_R}_{}\)) = \({2^{}}{^\eta {}}\) \({x_L}_{}{y_L}_{}\)+  \({2^{\eta /2}}^{}\)(\({x_L}_{}{y_R}_{}\) + \({x_R}_{}{y_L}_{}\) ) + \({x_R}_{}{y_R}_{}\)

So xy is computed via the expression on the right side. The addition takes linear time, and also the multiplications by powers of 2. The significant operations are the four  η/2 – bit multiplications,

xLyL, xLyR, xRyL, xRyR. These can be solved by four recursive calls. Thus our method for multiplying η – bit numbers start by making recursive calls to multiply these four pairs of η/2 – bit numbers (four subproblems of half the size), and then evaluates the preceding expression in O(η) time. Writing T (η) for the overall running time on η – bit inputs, we get the recurrence relation      

T(η) = 4T(η/2) + η

The correct answer is option 4: Sorting algorithm

Key Points

• A Sorting Algorithm is used to arrange data in a particular order (either ascending or descending).
• Common sorting algorithms include Bubble Sort, Merge Sort, Quick Sort, Insertion Sort, etc.
• Sorting helps in optimizing the performance of other algorithms like searching and merging.

Additional Information

• Searching algorithm: Used to find specific elements in data (e.g., linear search, binary search).
• Merging algorithm: Combines two or more sorted lists into one sorted list.
• Inverting algorithm: Not commonly used for sorting or ordering data; it's more related to reversing data or operations.

Hence, the correct answer is: option 4: Sorting algorithm

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.

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.

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.

Finding closest pairs out of the set of the 2-D points can be solved using divide and conquer approach.

Largest Sum Contiguous subarray is from index 9 to 14

Maximum subsequence sum = [11, -1, 0, 2, -3, 15] = 24

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;

}