DIVIDE AND CONQUER(DAC) :1 DIVIDE AND CONQUER(DAC) DAC is a recursive procedure which divides a problem into sub-problems, whose solution is combined to get the solution for the original problem. The sub-problems are divided till they are small enough to be solved .


DIVIDE AND CONQUER(DAC) (Contd..) :2 DIVIDE AND CONQUER(DAC) (Contd..) CONTROL ABSTRACTION It refers to a general procedure whose flow of control is clear but whose primary operations are specified by procedures which are not defined or they are different for different problems.


DIVIDE AND CONQUER(DAC) (Contd..) :3 DIVIDE AND CONQUER(DAC) (Contd..) Control Abstraction for DAC is as follows : Procedure DANDC(p,q)// solves a problem with input A(p,q) // global n, A(1:n); integer m,p,q ; If SMALL(p,q) //Boolean function to determine input set is small // then return G(p,q) // G(p,q) is computed when no splitting is required// else m?DIVIDE(p,q) // p<=m

DIVIDE AND CONQUER(DAC) (Contd..) :4 DIVIDE AND CONQUER(DAC) (Contd..) Analysis of DANDC The computing time of DANDC is described by the recurrence relation T(n) = { g(n) if n is small = { 2T(n/2) + f(n) otherwise g(n) is the time to compute answer directly. f(n) is the time for divide and combine


converting recursive algorithm into iterative one :5 converting recursive algorithm into iterative one Procedure DANDC (p,q) // iterative version // // declare a stack of appropriate size // local s,t // s,t are used to store function values // Top ? 0 //initially function value is 0// L1: While not SMALL(p,q) do m ? DIVIDE (p,q) // determine how to split input // Store p,q,m,0,2 in stack // 2,3 are return addresses // q ? m // stored with function values // repeat // ret = 2 means you need to store in stack // t ? G(p,q) // ret = 3 means you can compute/combine // While top ? 0 do p,q,m,s, ret removed from stack if ret = 2


DIVIDE AND CONQUER(DAC) (Contd..) :6 DIVIDE AND CONQUER(DAC) (Contd..) then stack gets p,q,m,t,3 // process the second recursive call // p?m+1 goto L1 else t ? COMBINE(s,t) endif Repeat return (t) end DANDC/


DIVIDE AND CONQUER(DAC) (Contd..) :7 DIVIDE AND CONQUER(DAC) (Contd..) Example Suppose n = 12 then p =1, q = 12 Let m = [(12+1)/2] = 6 2 2 2 2 0 0 0 0 6 3 2 1 12 6 3 2 1 1 1 1


DIVIDE AND CONQUER(DAC) (Contd..) :8 DIVIDE AND CONQUER(DAC) (Contd..) Example p,q,m,0,2 are in stack small(1,6)? No small(1,3)? No small(1,1)? Yes q?6 q?3 q?2 Compute G(1,1) m?3 m?2 m?1 t ? G(1,1) 3 top ? 0 so p,q,m,s, t G(1,1) i.e 1,2,1,0,2 1 removed from stack 2 p,q,m,t, 3 are 1 stored


DIVIDE AND CONQUER(DAC) (Contd..) :9 DIVIDE AND CONQUER(DAC) (Contd..) Now Second recursive call starts so, p? m + 1 = 2 small (2,2)? Yes t ? g (2,2) top ? 0 so, p,q,m,s,ret i.e 1,2,1, G(1,1), 3 are removed from the stack ret ? 2 so t? COMBINE (G(1,1), G(2,2)) 1 cycle completed. G(1,1) G(2,2) are combined to give G(1,2). Then G(1,2) G(3,3) will be combined to give G(1,3). G(1,2) G(1,6) G(1,3) G(1,2) G41,6) G(1,6) G(7,12) G(1,2) G(3,3) G(4,5) G(6,6) G(1,3) G(4,6) G(1,1) G(2,2)


BINARY SEARCH :10 BINARY SEARCH Let ai 1?i?n be a list of n elements sorted in non-decreasing order. The problem is of determining whether a given element x is present in the list. If x is present j is returned such that aj = x, otherwise j = 0. If the given problem is I=(n,a1………,an,x), the subproblems to be solved are I1=(k-1,a1,……….ak-1, x). I2=(1,ak,x), and I3=(n-k,ak+1,….an, x) for some k. If x = ak, I1 and I3 need not be solved


BINARY SEARCH (Contd..) :11 BINARY SEARCH (Contd..) If x ak then I3 needs to be solved and j=0 for I1 and I2. If ak is the middle element, i.e k=[(n+1)/2] then the search algorithm is known as binary search.


BINARY SEARCH (Contd..) :12 BINARY SEARCH (Contd..) Procedure BINSCRCH(A,n,x,j) // determine j such that A(j)=x in A(1:n) // low?1; high?n while low A(mid);low?mid+1 else:j?mid;return endcase repeat j?0 end BINSRCH


BINARY SEARCH (Contd..) :13 BINARY SEARCH (Contd..) Example: n = 9 A(j:n) are -15,-6,0,7,9,23,54,82,101. x is 101, -14, 82 Case 1 Case 2 Case3 x=101 x=-14 x=82 low high mid low mid high low mid high 1 9 5 1 9 5 7 9 5 6 9 7 1 4 2 6 9 7 8 9 8 1 1 1 5 9 8 9 9 9 2 1 found at 9 not found found


BINARY SEARCH (Contd..) :14 BINARY SEARCH (Contd..) The Binary decision tree is a tree with value of mid index at the nodes. For n=14 it looks as below 1 – 14 mid 7


BINARY SEARCH (Contd..) :15 BINARY SEARCH (Contd..)


BINARY DECISION TREE :16 BINARY DECISION TREE Binary decision tree is a tree with value of mid index at the nodes If x is present the algorithm will end at one of circular nodes or internal nodes; otherwise at square nodes or external nodes. The worst case time for binary search with n elements (n in [2k-1,2k) for some integer k) is O(logn) for successful search and ?(logn) for unsuccessful search. O(logn) – lower limit and ?(logn) – Lower and upper limit


worst case time for binary search with n elements :17 worst case time for binary search with n elements Proof: In a binary decision tree on n elements (2k-1<=n<2k) all circular nodes are at levels 1,2,….k while all square nodes are at levels k and k+1. The number of element comparisons required to terminate at a circular node on level i is I; while those required to terminate at a square node at level i is only i-1. (? there is no need of comparing with the middle element i.e., values

The average time for binary search :18 The average time for binary search As i can be 1,2,….k and n<2k or k

The average time for binary search(Contd..) :19 The average time for binary search(Contd..) The number of comparisons on any path from root to a node is equal to the distance between the root and the node. Let I= the sum of the distances of all internal nodes from root. Let E= the sum of the distances of all external nodes from root. I is internal path length, and E is the external path length.


The average time for binary search(Contd..) :20 The average time for binary search(Contd..) For any binary tree with n internal nodes. E=I+2n (can be proved by induction)----(1) ( Let n=1 then I=0 E=I+2*1=2 Let E=I+2n is true for n, and consider n+1 nodes. With the increase of one node two external nodes are added).


The average time for binary search(Contd..) :21 The average time for binary search(Contd..) As every binary tree with n internal nodes has n+1 external nodes U(n) = E/(n+1) …………..(2) S(n)=1+I/n S(n) is equal to average path length + one comparison) =1+(E-2n)/n from (1) =1+(U(n)(n+1)-2n)/n from (2) =(n+U(n)(n+1)-2n)/n =(U(n)(n+1))/n-1=U(n)(1+1/n)-1 So S(n) and U(n) are directly related.


The average time for binary search(Contd..) :22 The average time for binary search(Contd..) But E is proportional to nlogn (using worst case time and definition of E) So U(n)=E ~ nlogn ~ log n n+1 n+1 ? S(n) ~ logn Average time = O(logn).


Complexity of Binary Search :23 Complexity of Binary Search Successful search – only one comparison Unsuccessful search +log n+ comparisons Successful Searches Unsuccessful Searches Best average worst best average worst ?(1) ?(log n) ?(log n) ?(log n) There is no better algorithm than binary search for searching in the worst case.


Variation of binary search useful in programming :24 Variation of binary search useful in programming Procedure BINSCRCH1 (A,n,x,j) Integer low, high, mid, j, n low ?1; high?n+1 while Low < high-1 do mid?+low+high+ 2 if x < A(mid) then high?mid else low?mid endif repeat if x=A(low) then j?low else j?0 endif end BINSCRCH1 Only one comparison between x and A(mid) in contrast to three in BINSCRCH. As x is A(low) is included in else part J?low or 0 There is no need of A(mid) separately.


Binary Search for Best Case (Contd..) :25 Binary Search for Best Case (Contd..) Example: Consider 10 15 20 25 30 ¦ ¦ ¦ ¦ ¦ 1 2 3 4 5 Let x=20 low?1 high?5+1=6 1< (6-1=5) so mid?+7/2+=3 x=20 < A (mid)= A(3) =20 no so else part low?3 3<5 yes so mid?+3+6+/2=4 20<25 yes so high?4 low =3< high-1=3 no while loop is exited 20=A(low)=A(3)=20 yes j?3 [1 6] [3 6] [3 4]


Finding the Maximum and Minimum :26 Finding the Maximum and Minimum 2. Procedure straightmaxmin(A,n,Max,min) Integer i,n max?min?A(1) A(i) max is false if A(i)>max then max?A(i) endif so two of statements if A(i)

Analysis of straightmaxmin :27 Analysis of straightmaxmin Best case It occurs when elements are in increasing order. So element comparisons are (n-1). Worst case It occurs when elements are in decreasing order. So element comparisons are ? 2(n-1)=2n-2<2n-2+1<2n-1. Average case occurs when A(i) will be greater than max half the time, so comparisons <2n -1 – (n/2) = 3n/2 - 1.


Divide and Conquer strategy for MAX and MIN :28 Divide and Conquer strategy for MAX and MIN I =(n,A(1),…..,A(n)), I1=(+n/2+, A(1),…..A+n/2+, I2=(n-+n/2+,A+n/2++1,….A(n)).


Divide and Conquer strategy for MAX and MIN :29 Divide and Conquer strategy for MAX and MIN Procedure MAXMIN (i,j,fmax,fmin) global A(1:n),n;integer i,j Case : i=j : fmax?fmin?A(i) : i=j-1 : if A(i)

Divide and Conquer strategy for MAX and MIN :30 Divide and Conquer strategy for MAX and MIN Let us construct a tree of recursive calls for the example: A: 22 13 -5 -8 15 60 17 31 47 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 1 2 3 4 5 6 7 8 9 A node is added when a new call is made. Each node has four items i,j,fmax,fmin. The circled numbers represent the order in which fmax, fmin are assigned a value.


tree of recursive calls for the MAX and MIN :31 tree of recursive calls for the MAX and MIN 9 1 9 60 -8 5 8 1 5 22 -8 6 9 60 17 3 4 6 7 1 3 22 -5 4 5 15 -8 6 7 60 17 8 9 47 31 1 2 1 2 22 13 3 3 -5 -5


Analysis of MAXMIN :32 Analysis of MAXMIN Let T(n) be the number of comparisons for n elements (excluding Index comparisons). T(n) = T+n/2+ + T+n/2++2 for n>2 (Two recursive calls + computation of fmax, fmin)   1    for n=2 --------- one comparison if A(i)

Analysis of MAXMIN (Contd..) :33 Analysis of MAXMIN (Contd..) T(n) = 2T(n/2)+2 = 2(2T(n/2)+2)+2 = 4T(n/4)+4+2 : = 2k-1T(n/2k-1)+2k-1+2k-2+-----4+2 = 2k-1T(2)+ ? 2i 1<=i<=k-1 = 2k-1x1+2k-2 = n/2+n-2 = 3n/2-2


Analysis of MAXMIN (Contd..) :34 Analysis of MAXMIN (Contd..) Result: ? 2i = 2k-2 1<=i<=k-1 Proof by induction : k=2 L.H.S. = 21 = 2 R.H.S. = 22-2 = 2 Suppose for k-1 it is true : ?2i = 2k-2 1<=i<=k-1 Consider 2+4 +… 2k-1+2k = 2k-2+2k = 2k+1-2. Hence proved.


Analysis of MAXMIN (Contd..) :35 Analysis of MAXMIN (Contd..) Straightmaxmin requires 2n-2 MAXMIN requires 3n/2 - 2 Difference is 2n-2 - 3n/2 + 2 = n/2 n/2 x 1/(2( n-1)) x 100 ~ 25% savings in comparisons ( no algorithm uses less than 3n/2-2 comparisons). But MAXMIN requires more storage as stack space for i, j, fmax, fmin and return address is needed. Even if recursion is removed a stack of size log n is still required.


Analysis of maxmin when index comparisons are included :36 Analysis of maxmin when index comparisons are included The two case statements in maxmin ( i>=j-1 and i=j-1 ) can be replaced by one as below Case : i>=j-1 : if A(i)j-1 as i = j = 1 for 1>1-1)


Analysis of maxmin when index comparisons are included :37 Analysis of maxmin when index comparisons are included Assuming n=2k for some positive integer k C(n) = 2C (n/2)+3 for n>2 (two recursive calls + I >= j-1 + computation of fmax, fmin) 2 for n=2 ( i>=j-1 + A(i)=j-1 )


Analysis of maxmin when index comparisons are included :38 Analysis of maxmin when index comparisons are included C(n) = 2C (n/2) + 3 (3.22 +3.21+3.30) = 2(2C(n/4)+3)+3) = 4C(n/4)+6+3 = 8C(n/8)+12+6+3 = …..=2k-1C(n/2k-1)+3(20+21+….+2k-2) = 2k-1C(n/2k-1)+3?k-20 2i = 2k-1C(2)+3 ?k-2 0 ?2i = 2k-1 C(2)+3(1+ ?k-212i) = 2k-1x 2+3(1+2k-1-2) = 2k+3(2k-1-1) = n+3n/2-3= 5n/2-3 Straightmaxmin requires 3(n-1) if for loop is included 3(n-1) > 5n/2 -3 So MAXMIN is still better with overhead of stack.