Week 4 Discussion Forum

What is Divide & Conqure

What is Divide & Conqure

by Mridul Halder(192-15-2908) -
Number of replies: 1

  1. Divide: Divide the given problem into sub-problems using recursion.
  2. Conquer: Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.

25 words

In reply to Mridul Halder(192-15-2908)

Re: What is Divide & Conqure

by Md. Sabbir Hossain 192-15-2809 -
-The following are some standard algorithms that follows Divide and Conquer algorithm.

1.Binary Search is a searching algorithm. In each step, the algorithm compares the input element x with the value of the middle element in array. If the values match, return the index of the middle. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of middle element, else recurs for the right side of the middle element.

2.Quicksort is a sorting algorithm. The algorithm picks a pivot element, rearranges the array elements in such a way that all elements smaller than the picked pivot element move to left side of pivot, and all greater elements move to right side. Finally, the algorithm recursively sorts the subarrays on left and right of pivot element.

3.Merge Sort is also a sorting algorithm. The algorithm divides the array in two halves, recursively sorts them and finally merges the two sorted halves.

160 words