Divide and Conquer

Divide and Conquer

Divide and conquer approach is divided into smaller sub-problems and then each problem is solved independently. When we keep dividing the sub-problems into even smaller sub-problems, it reaches a stage where no more division is possible. The solution of all sub-problems is finally merged in order to obtain the solution of the original problem.

Divide and Conquer algorithm consists of a dispute using the following three steps.

1. Divide: the original problem divides into a set of sub problems.

2.Conquer: Solve every sub problem individually, recursively.

3. Combine: Put together the solutions of the sub problems to get the solution to the whole problem.

General Method

Divide and conquer finding the smallest sub problem in second step it makes algorithm to solve (conquer) that sub problem recursively and return solution recursively. In the last step it makes algorithm to combine the solution of sub problems or solved sub problems in the same manner it divided, to get the solution to the given big problem.

a. Finding the power of an element

b. Searching an element in a sorted array

c. Sorting an unordered array

d. Matrix multiplication

Control abstraction: -The meaning of abstractions is preserving information that is relevant in a given context

❖Two types of abstraction: -

● Control abstraction: the ability to procedural data where in the program procedural data is irrelevant.
● Data abstraction: Data abstraction is the reduction of a particular data to a simplified representation of the whole.

Binary Search: The binary search algorithm is a searching algorithm, which is also called a half-interval search or logarithmic search. It works by comparing the target value with the middle element existing in a sorted array. The process keeps on repeating until the target value is met.

Merge Sort: It is a sorting algorithm that sorts an array by making comparisons. It starts by dividing an array into sub-array and then recursively sorts each of them.

Merge Sort Algorithm

Merge sort keeps on dividing the list into equal halves until it can no more be divided. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.

Step 1 − if it is only one element in the list, consider it already sorted, so return.

Step 2 − divide the list recursively into two halves until it can no more be divided.

Step 3 − merge the smaller lists into new list in sorted order.

Algorithm

In the following algorithm, arr is the given array, beg is the starting element, and end is the last element of the array.

MERGE_SORT (arr, beg, end)

if beg < end

set mid = (beg + end)/2

MERGE_SORT (arr, beg, mid)

MERGE_SORT (arr, mid + 1, end)

MERGE (arr, beg, mid, end)

end of if END MERGE_SORT

Quicksort

1. Quicksort picks an element as pivot, and then it partitions the given array around the picked pivot element. In quick sort, a large array is divided into two arrays in which one holds values that are smaller than the specified value (Pivot), and another array holds the values that are greater than the pivot.

2. After that, left and right sub-arrays are also partitioned using the same approach. It will continue until the single element remains in the sub-array.

QUICKSORT (array A, int m, int n)

1 if (n > m)

2 then

3 i ← a random index from [m,n]

4 swap A [i] with A[m]

5 o ← PARTITION (A, m, n)

6 QUICKSORT (A, m, o - 1)

7 QUICKSORT (A, o + 1, n)

Partition Algorithm:

Partition algorithm rearranges the sub arrays in a place.

PARTITION (array A, int m, int n)

1 x ← A[m]

2 o ← m

3 for p ← m + 1 to n

4 do if (A[p] < x)

5 then o ← o + 1

6 swap A[o] with A[p]

7 swap A[m] with A[o]

8 return o

Strassen’s Matrix Multiplication

Strassen in 1969 gave an overview on how we can find the multiplication of two 2*2-dimension matrices. But by using the divide and conquer technique the overall complexity for the multiplication of two matrices has been reduced.

Following are the formulae that are to be used for matrix multiplication.

D1 = (a11 + a22) * (b11 + b22)

D2 = (a21 + a22) *b11

D3 = (b12 – b22) *a11

D4 = (b21 – b11) *a22

D5 = (a11 + a12) *b22

D6 = (a21 – a11) * (b11 + b12)

D7 = (a12 – a22) * (b21 + b22)

C00= d1 + d4 – d5 + d7

C01 = d3 + d5

C10 = d2 + d4

C11 = d1 + d3 – d2 – d6

Here, C00, C01, C10, and C11 are the elements of the 2*2 matrix.

Algorithm for Strassen’s matrix multiplication

Algorithm Strass (n, x, y, z)

begin

If n = threshold then compute

C = x * y is a conventional matrix.

Else

Partition an into four sub matrices a00, a01, a10, a11.

Partition b into four sub matrices b00, b01, b10, b11.

Strass (n/2, a00 + a11, b00 + b11, d1)

Strass (n/2, a10 + a11, b00, d2)

Strass (n/2, a00, b01 – b11, d3)

Strass (n/2, a11, b10 – b00, d4)

Strass (n/2, a00 + a01, b11, d5)

Strass (n/2, a10 – a00, b00 + b11, d6)

Strass (n/2, a01 – a11, b10 + b11, d7)

C = d1+d4-d5+d7 d3+d5

d2+d4 d1+d3-d2-d6

end if

return (C)

end.

Practice Questions on justification

1)State condition for Strassen's matrix multiplication?

2) How can we prove that Strassen matrix multiplication is advantageous over ordinary matrix multiplication?

3) Which technique is used in Strassen's matrix multiplication?

4)Is Strassen's matrix divide and conquer? Why?

5)State name of Comparisons Sorts

6) What is best-case time complexity of bubble sort and Justify

7) if heap sort contains minimum element at root called as which Heap and why?

8) How do you form min heap from array?

9) How many comparisons will be made to sort the array arr= {1, 5, 3, 8, 2} using bucket sort? Why?

10) arranging a pack of playing cards is example of which sort and why?

Milan Tomic

Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.