Divide and conquer

about divide and conqure

1. DIVIDE AND CONQUER PRESENTED BY M.RAMYA M.sc[CS&IT] NADAR SARASWATHI COLLEGE OF ARTS &SCIENCE, VADAPUDUPATTI , THENI.

2. GENERAL METHOD A function to compute on n inputs the divide and conquer strategy suggests splitting the inputs into k distinct subsets , 1 < k ≤ n , yielding k sub problems. If the sub problems are still relatively large , then the divide and conquer strategy can possibly be reapplied

3. CONTROL ABSTRACTION FOR DIVIDE AND CONQUER Algorithm DAndC(P) { if Small(P)then return S(P); else { divide P into smaller instances P1,P2,……,P k , k≥1; Apply DAndC to each of these sub problems; return Combine(DAndC(P1),DAndC(P2),…,DAndC(P k )); } }

4. If the size of P is n and the size of the k sub problems are n 1 , n 2 , ……, n k , respectively then the computing time of DAndC is described by the recurrence relation where T(n) is the time for DAndC on any input of size n and g(n) is the time to compute the answer directly for small inputs. n small otherwise

5. The complexity of many divide and conquer algorithms is given by recurrences of the form where a and b are known constants. We assume that T(1) is known and n is a power of b. One of the methods for solving any such recurrence relation is called the substitution method. n=1 n>1

6. BINARY SEARCH Let a i , 1 ≤ i ≤ n , be a list of elements that are sorted in nondecreasing order. Consider the problem determine where a given element x is present in the list. If x is present , we are to determine a value j such that a j = x. If x is not in the list , then j is to be set to zero.

7. RECURSIVE BINARY SEARCH Algorithm BinSrch(a , i , l , x) { if(l = i) then { if (x = a[i]) then return i; else return 0; } else { mid:=[(i+l)/2]; if (x=a[mid]) then return mid; else if (x < a[mid]) then return BinSrch(a , i , mid-1 , x ); else return BinSrch(a , mid+1 , l , x); } }

8. ITERATIVE BINARY SEARCH Algorithm BinSearch(a , n , x) { low:=1; high:=n; while (low ≤ high) do { mid:=[(low + high)/2]; if (x < a[mid]) then high:=mid-1; else if (x > a[mid]) then low:=mid+1; else return mid; } return 0; }

9. THREE EXAMPLES OF BINARY SEARCH ON 14 ELEMENTS Example: Let us consider 14 entries: -15,-6,0,7,9,23,54,82,101,112,125,131,142,151 Place them in a[1:14] and simulate the steps that bin search goes through as it searches for different values of x. Only the variables low, high and mid need to be traced as we simulate the algorithm. We try the following values for x: 151,-14,9 for two successful searches and one unsuccessful search. The traces of these three inputs shows below: X = 151           low         high       mid                         1              14           7                         8              14           11 12           14           13 14           14           14                                  Found

10. COND…. X = -14                   low         high       mid                                 1              14           7                                 1              6              3                                 1              2              1                                 2              2              2                                 2              1               Not Found X = 9                       low         high       mid                                 1              14           7                                 1              6              3                                 4              6              5                                                                  Found

11. BINARY DECISION TREE FOR BINARY SEARCH , n =14

12. BINARY SEARCH USING ONE COMPARSION PER CYCLE Algorithm BinSearch1(a , n , x) { low:=1;high:=n+1; while (low<(high-1)) do { mid:=[(low+high)/2]; if(x < a[mid]) then high:=mid; else low:=mid; } if (x=a[low]) then return low; else return 0; }

13. ADVANTAGES 1. In this method elements are eliminated by half each time .So it is very faster than the sequential search. 2. It requires less number of comparisons than sequential search to locate the search key element. DISADVANTAGES 1. An insertion and deletion of a record requires many records in the existing table be physically moved in order to maintain the records in sequential order. 2. The ratio between insertion/deletion and search time is very high.

14. FINDING THE MAXIMUM AND MINIMUM The divide and conquer technique. The problem is to find the maximum and minimum items in a set of n elements. More importantly , when the elements in a[1:n] are polynomials , vectors , very large numbers or strings of characters , the cost of an element comparison is much higher than the cost of the other operations. Hence the time is determined mainly by the total cost of the element comparisons.

15. StraightMaxMin 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 if (a[i] > max) then max:=a[i]; else if (a[i] < min) then min:=a[i];

16. STRAIGHTFORWARD MAXIMUM AND MINIMUM Algorithm StraightMaxMin(a , n , max , min) { max:=min:=a[1]; for i:=2 to n do { if (a[i] > max) then max:=a[i]; if (a[i] < min) then min:=a[i]; } }

17. If the T(n) represents the number , then the resulting recurrence relation is,

18. RECURSIVELY FINDING THE MAXIMUM AND MINIMUM

19. TREES OF RRECURSIVE CALLS OF MAXMIN