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

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard 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(n1). 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 divideandconquer 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 divideandconquer 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 = j1) 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.