Divide and Conquer MCQ Quiz in मल्याळम - Objective Question with Answer for Divide and Conquer - സൗജന്യ PDF ഡൗൺലോഡ് ചെയ്യുക

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 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.

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;

}

Use a divide and conquer method to solve the above problem:

Divide the array into two parts & return maximum of:

1. sum_of[left]

2. sum_of[right]

3. max_sum_of_crossing_midpoint[left...right]

l = 1, h = 9, mid = l + h / 2 = 5

Part 1: arr[0] to arr[5] and

Part 2: arr[6] to arr[9]

find sum_of[0...5] and sum_of[6...9]

sum_of[0...5] = -9 and sum_of[6...9] = 14

find max_sum_of_crossing_midpoint[0...9]:

max_sum_left(from index 3 to index 5) = 9

 max_sum_right(from index 6 to 7) = 24

max_sum_left + max_sum_right= 9 + 24 = 33