Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
Finding the Maximum and Minimum
Let us consider another simple problem that can be solved by the divide and conquer technique. The problem is to find the maximum and minimum items in a set of n elements.Algorithm 4 is a straight forward algorithm to accomplish this.

Straight Max Min requires 2(n = 1) element comparisons in the best, average, and worst cases. An immediate improvement is possible by realizing that the comparison a[i] < min is necessary only when a[i] > max is false. Hence we can replace the contents of the for loop by

Now the best case occurs when the elements are in increasing order. The number of element comparisons is n – 1. The worst case occurs when the elements are in decreasing order. In this case the number of element comparisons is 2(n-1). The average number of element comparisons is less than 2(n – 1).On the average,a[i]is greater than max half the time,and so the average number of comparisons is 3n/2- 1.
A divide-and-conquer algorithm for this problem would proceed as follows: Let P = (n,a[i],…, a[j]) denote an arbitrary instance of the problem. Here n is the number of elements in the list a[i],…, a[j]and we are interested in finding the maximum and minimum of this list.Let Small(P)/be true when n <2.In this case,the maximum and minimum area[i] if n = 1. If n = 2, the problem can be solved by making one comparison.
If the list has more than two elements,P has to be divided into smaller instances.For example,we might divide P into the two instances P1 = ([n/2],a[1],…,a[[n/2]]) and P2 = (n -[n/2],a[[n/2\]+1],… ,a[n]). After having divided P into two smaller sub problems, we can solve them by recursively invoking the same divide-and-conquer algorithm.How can we combine the solutions for P1 and P2 to obtain a solution for P? If MAX(P) and MIN(P) are the maximum and minimum of the elements in P, then MAX(P) is the larger of MAX(P1) and MAX(P2). Also, MIN(P) is the smaller of MIN(P1)and MIN(P2)
Algorithm 5 results from applying the strategy just described. Max Min is a recursive algorithm that finds the maximum and minimum of the set of elements{a(i),a(i + 1),…, a(j)}.The situation of set sizes one (i = j) and two (i = j-1) are handled separately. For sets containing more than two elements,the mid point is determined(just as in binary search)and two new sub problems are generated.When the maxima and minima of these sub problems are determined,the two maxima are compared and the two minima are compared to achieve the solution for the entire set.

The procedure is initially invoked by the statement MaxMin(l,n,x,y) Suppose we simulate MaxMin on the following nine element.

A good way of keeping track of recursive calls is to build a tree by adding a node each time a new call is made. For this algorithm each node has four items of information:i,j, max,and rain. On the array a[] above,the tree of Figure 1 is produce.
