Back to Course


0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 17 of 43
In Progress

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.

KodNest Capture31
Algorithm 4 : Straight forward maximum and minimum

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

KodNest Capture30

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.

KodNest Capture32
Algorithm 5 Recursively finding the maximum and minimum

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

KodNest Capture33

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.

KodNest Capture34
Figure 1 : Trees of recursive calls of Max Min

New Report